Research portal

Bound-constrained polynomial optimization using only elementary calculations

Research output: Scientific - peer-reviewArticle

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
JournalMathematics of Operations Research
Early online date1 Mar 2017
DOIs
StateE-pub ahead of print - Mar 2017

    Research areas

  • polynomial optimization, bound-constrained optimization, Lasserre hierarchy

DOI

Login to Pure (for TiU staff only)