Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
From MaRDI portal
Publication:517310
Abstract: We consider the problem of minimizing a continuous function f over a compact set K. We analyze a hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864--885], obtained by searching for an optimal probability density function h on K which is a sum of squares of polynomials, so that the expectation is minimized. We show that the rate of convergence is no worse than , where 2r is the degree bound on the density function. This analysis applies to the case when f is Lipschitz continuous and K is a full-dimensional compact set satisfying some boundary condition (which is satisfied, e.g., for convex bodies). The r-th upper bound in the hierarchy may be computed using semidefinite programming if f is a polynomial of degree d, and if all moments of order up to 2r+d of the Lebesgue measure on K are known, which holds for example if K is a simplex, hypercube, or a Euclidean ball.
Recommendations
- Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets
- Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
- Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
- Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
- Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing
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 refined error analysis for fixed-degree polynomial optimization over the simplex
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
- An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
- Certifying convergence of Lasserre's hierarchy via flat truncation
- Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube
- Global optimization with polynomials and the problem of moments
- GloptiPoly 3: moments, optimization and semidefinite programming
- scientific article; zbMATH DE number 3863589 (Why is no real title available?)
- scientific article; zbMATH DE number 1249699 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- Invariant Integration Formulas for the n-Simplex by Combinatorial Methods
- On the Complexity of Computing the Volume of a Polyhedron
- On the complexity of optimization over the standard simplex
- On the complexity of Putinar's Positivstellensatz
- On the complexity of Schmüdgen's Positivstellensatz
- Scattered Data Approximation
- Solving a class of multivariate integration problems via Laplace techniques
- Sums of squares, moment matrices and optimization over polynomials
- The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
- Triangulations. Structures for algorithms and applications
Cited in
(23)- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
- Detecting optimality and extracting solutions in polynomial optimization with the truncated GNS construction
- 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
- Distributionally robust optimization with polynomial densities: theory, models and algorithms
- Quadrature-based polynomial optimization
- Connecting optimization with spectral analysis of tri-diagonal matrices
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization
- A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis
- Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
- 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
- Comparison of Lasserre's measure-based bounds for polynomial optimization to bounds obtained by simulated annealing
- Bound-constrained polynomial optimization using only elementary calculations
- A note on the upper bound in SA AMG convergence analysis
- Algebraic Perspectives on Signomial Optimization
- An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
- Harmonic Hierarchies for Polynomial Optimization
- Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
- Convergence rate for linear minimizer-estimators in the moment-sum-of-squares hierarchy
- A hierarchy of eigencomputations for polynomial optimization on the sphere
This page was built for publication: Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517310)
