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.
|Place of Publication||Ithaca|
|Publisher||Cornell University Library|
|Number of pages||23|
|Publication status||Published - 15 Jul 2015|
- polynomial optimization
- bound-constrained optimization
- Lasserre hierarchy
de Klerk, E., Lasserre, J. B., Laurent, M., & Sun, Z. (2015). Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. (arXiv; Vol. 1507.04404). Ithaca: Cornell University Library.