Skip to Main content Skip to Navigation
Journal articles

Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

Abstract : We provide a monotone nonincreasing sequence of upper bounds fHk(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 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Jean Bernard Lasserre <>
Submitted on : Thursday, February 1, 2018 - 10:44:14 AM
Last modification on : Thursday, June 10, 2021 - 3:07:12 AM

Links full text



Etienne de Klerk, Jean Lasserre, Monique Laurent, Zhao Sun. Bound-Constrained Polynomial Optimization Using Only Elementary Calculations. Mathematics of Operations Research, INFORMS, 2017, 42 (3), pp.834 - 853. ⟨10.1287/moor.2016.0829⟩. ⟨hal-01698348⟩



Record views