Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

0.00 Avg rating0 Votes
Article ID: iaor20173319
Volume: 42
Issue: 3
Start Page Number: 834
End Page Number: 853
Publication Date: Aug 2017
Journal: Mathematics of Operations Research
Authors: , , ,
Keywords: heuristics, programming: constraints
Abstract:

We provide a monotone nonincreasing sequence of upper bounds [Formula: see text] 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 [Formula: see text] have a rate of convergence in [Formula: see text]. 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 [Formula: see text] needs only O(nk ) elementary calculations.

Reviews

Required fields are marked *. Your email address will not be published.