Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization

DOI10.1007/S10107-020-01586-YMaRDI QIDQ2044964zbMATH OpenOpenAlexFDO

Authors Lucas Slot, Monique Laurent

Publication date 11 August 2021

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.11289

zbMATH Keywords

Lasserre hierarchyneedle polynomialpolynomial optimizationpush-forward measuresemidefinite programmingsum-of-squares polynomial

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polynomial optimization (90C23) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Abstract: We consider a hierarchy of upper approximations for the minimization of a polynomial $f$ over a compact set $Ksubseteqmathbb{R}^n$ proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on $K$ by the polynomial $f$ and involves univariate sums of squares of polynomials with growing degrees $2r$. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864--885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of $f$ at a rate in $O(lo{g}^{2}r/r^2)$ whenever $K$ satisfies a mild geometric condition, which holds, e.g., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in $Omega(1/r^2)$ for a class of polynomials on $K=[-1,1]$, obtained by exploiting a connection to orthogonal polynomials.

Recommendations

• Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
• Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere

Cites work

• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis
• An introduction to polynomial and semi-algebraic optimization
• Bounds for extreme zeros of some classical orthogonal polynomials
• Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
• Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
• Global optimization with polynomials and the problem of moments
• scientific article; zbMATH DE number 3477793 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
• Markov's inequality and \(C^{\infty}\) functions on sets with polynomial cusps
• Multivariate ``needle polynomials with application to norming sets and cubature formulas
• On the complexity of Putinar's Positivstellensatz
• On the complexity of Schmüdgen's Positivstellensatz
• Sharp bounds for the extreme zeros of classical orthogonal polynomials
• The K-moment problem for compact semi-algebraic sets
• The sum-of-squares hierarchy on the sphere and applications in quantum information theory
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube

Cited in

(21)

• The moment-SOS hierarchy and the Christoffel-Darboux kernel
• Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
• Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
• Quadrature-based polynomial optimization
• Connecting optimization with spectral analysis of tri-diagonal matrices
• An effective version of Schmüdgen's Positivstellensatz for the hypercube
• Polynomial optimization with real varieties
• Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
• An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• Optimization on the Euclidean unit sphere
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
• Minimizing rational functions: a hierarchy of approximations via pushforward measures
• Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
• Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing
• Sum-of-squares hierarchies for binary polynomial optimization
• Exponential Convergence of Sum-of-Squares Hierarchies for Trigonometric Polynomials
• The moment-SOS hierarchy: applications and related topics
• Finding global minima via kernel approximations
• Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
• Polynomial optimization, certificates of positivity, and Christoffel function

This page was built for publication: Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044964)