Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
Preprint
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 $\int_{K}f(x)h(x)dx$ is minimized. We show that the rate of convergence is $O(1/\sqrt{r})$, 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 polytopes and the Euclidean ball). 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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplexMathematical Programming, 2014
- A Refined Error Analysis for Fixed-Degree Polynomial Optimization over the SimplexJournal of the Operations Research Society of China, 2014
- Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the HypercubeSIAM Journal on Optimization, 2010
- On the complexity of optimization over the standard simplexEuropean Journal of Operational Research, 2008
- On the complexity of Putinar's PositivstellensatzJournal of Complexity, 2007
- A PTAS for the minimization of polynomials of fixed degree over the simplexTheoretical Computer Science, 2006
- Scattered Data Approximation2004
- Solving semidefinite-quadratic-linear programs using SDPT3Mathematical Programming, 2003
- On the Complexity of Computing the Volume of a PolyhedronSIAM Journal on Computing, 1988
- Handbook of Mathematical Functions With Formulas, Graphs and Mathematical Tables (National Bureau of Standards Applied Mathematics Series No. 55)Journal of Applied Mechanics, 1965