Bound-constrained polynomial optimization using only elementary calculations

Etienne de Klerk, J.B. Lasserre, Monique Laurent, Zhao Sun

Research output: Contribution to journalArticleScientificpeer-review

15 Citations (Scopus)

Abstract

We provide a monotone nonincreasing sequence of upper bounds fHk(k≥1)fkH(k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in ℝn. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21:864–885] is that only elementary computations are required. For optimization over the hypercube [0, 1]n, we show that the new bounds fHkfkH have a rate of convergence in O(1/k−−√)O(1/k). Moreover, we show a stronger convergence rate in O(1/k) for quadratic polynomials and more generally for polynomials having a rational minimizer in the hypercube. In comparison, evaluation of all rational grid points with denominator k produces bounds with a rate of convergence in O(1/k2), but at the cost of O(kn) function evaluations, while the new bound fHkfkH needs only O(nk) elementary calculations.
Original languageEnglish
Pages (from-to)834-853
JournalMathematics of Operations Research
Volume42
Issue number3
Early online dateMar 2017
DOIs
Publication statusPublished - Aug 2017

Keywords

  • polynomial optimization
  • bound-constrained optimization
  • Lasserre hierarchy

Fingerprint

Dive into the research topics of 'Bound-constrained polynomial optimization using only elementary calculations'. Together they form a unique fingerprint.

Cite this