Bound-constrained polynomial optimization using only elementary calculations
E. Klerk (TU Delft - Discrete Mathematics and Optimization, Tilburg University)
Jean B. Lasserre (Université de Toulouse)
Monique Laurent (Tilburg University, Centrum Wiskunde & Informatica (CWI))
Zhao Sun (Symetrix B.V.)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.