TY - JOUR

T1 - Bound-constrained polynomial optimization using only elementary calculations

AU - De Klerk, Etienne

AU - Lasserre, Jean B.

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2017/3/15

Y1 - 2017/3/15

N2 - We provide a monotone nonincreasing sequence of upper bounds f H k (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 f H k fkH 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 f H k fkH needs only O(nk) elementary calculations.

AB - We provide a monotone nonincreasing sequence of upper bounds f H k (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 f H k fkH 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 f H k fkH needs only O(nk) elementary calculations.

KW - Bound-constrained optimization

KW - Lasserre hierarchy

KW - Polynomial optimization

UR - http://www.scopus.com/inward/record.url?scp=85026864518&partnerID=8YFLogxK

UR - http://resolver.tudelft.nl/uuid:71c944e9-6f27-4dbc-b7d7-328365b1578d

U2 - 10.1287/moor.2016.0829

DO - 10.1287/moor.2016.0829

M3 - Article

AN - SCOPUS:85026864518

VL - 42

SP - 834

EP - 853

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 3

ER -