Bound-constrained polynomial optimization using only elementary calculations

2015/07/15 by Etienne de Klerk, de Klerk, Etienne, Jean B. Lasserre +5
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1507.04404

Abstract

We provide a monotone non increasing sequence of upper bounds f^H_k (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 f^H_k 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/k²), but at the cost of O(kⁿ) function evaluations, while the new bound f^H_k needs only O(n^k) elementary calculations.

Related

• Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
• Worst-case examples for Lasserre's measure--based hierarchy for\n polynomial optimization on the hypercube
• Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
• Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
• An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization