Bound-Constrained Polynomial Optimization Using Only Elementary Calculations

• 成果类型: Article
• 署名作者: de Klerk, Etienne; Lasserre, Jean B.; Laurent, Monique; Sun, Zhao
• 署名单位: Tilburg University; Delft University of Technology; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centrum Wiskunde & Informatica (CWI)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0829
• 发表日期: 2017
• 页码: 834-853
• 关键词: global optimization; semidefinite; minimization; relaxations; simplex; moments

摘要

We provide a monotone nonincreasing sequence of upper bounds f(k)(H) (k >= 1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in R-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(k)(H) have a rate of convergence in O(1/root 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/k(2)), but at the cost of O(k(n)) function evaluations, while the new bound f(k)(H) needs only O(n(k)) elementary calculations.