TY - UNPB

T1 - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

AU - de Klerk, Etienne

AU - Lasserre, J.B.

AU - Laurent, Monique

AU - Sun, Zhao

PY - 2015/7/15

Y1 - 2015/7/15

N2 - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk needs only O(nk) elementary calculations.

AB - We provide a monotone non increasing sequence of upper bounds fHk (k≥1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21, pp. 864--885, 2010] is that only elementary computations are required. For optimization over the hypercube, we show that the new bounds fHk have a rate of convergence in 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 fHk needs only O(nk) elementary calculations.

KW - polynomial optimization

KW - bound-constrained optimization

KW - Lasserre hierarchy

UR - http://arxiv.org/abs/1507.04404

M3 - Working paper

T3 - arXiv

BT - Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

PB - Cornell University Library

CY - Ithaca

ER -