Improved Convergence Rates for Lasserre-Type Hierarchies of Upper Bounds for Box-Constrained Polynomial Optimization
Authors:
- Etienne de KlerkEKEtienne de Klerk
- Roxana HessRHRoxana Hess
- Monique LaurentMLMonique Laurent
- 1 January 2017
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 27 (1) , 347-367
Abstract
We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It is known that, for the Lebesgue measure $d\mu(x) = dx$, one may show an error bound $O(1/\sqrt{r})$ if $h$ is a sum-of-squares density, and an $O(1/r)$ error bound if $h$ is the density of a beta distribution. In this paper, we show an error bound of $O(1/r^2)$, if $d\mu(x) = \left( \prod_{i=1}^n \sqrt{1-x_i^2} \right)^{-1}$ (the well-known measure in the study of orthogonal polynomials), and $h$ has a Schmüdgen-type representation with respect to $[-1,1]^n$, which is a more general condition than a sum of squares. The convergence rate analysis relies on the theory of polynomial kernels and, in particular, on Jackson kernels. We also show that the resulting upper bounds may be computed as generalized eigenvalue problems, as is also the case for sum-of-squares densities.
Keywords
All Related Versions
Funding Information
- Université Paul Sabatier
- Ecole Doctorale Systems
- Ecole des Docteurs de l'Universite Fedederale Toulouse Midi-Pyrenees
This publication has 12 references indexed in Scilit:
- A Feasible Active Set Method for Strictly Convex Quadratic Problems with Simple BoundsSIAM Journal on Optimization, 2015
- Handelman rank of zero-diagonal quadratic programs over a hypercube and its applicationsJournal of Global Optimization, 2012
- Rank of Handelman hierarchy for Max-CutOperations Research Letters, 2011
- A New Look at Nonnegativity on Closed Sets and Polynomial OptimizationSIAM Journal on Optimization, 2011
- The kernel polynomial methodReviews of Modern Physics, 2006
- A New Active Set Algorithm for Box Constrained OptimizationSIAM Journal on Optimization, 2006
- Positive Polynomials2001
- Global Optimization with Polynomials and the Problem of MomentsSIAM Journal on Optimization, 2001
- Polynomials that are positive on an intervalTransactions of the American Mathematical Society, 2000
- TheK-moment problem for compact semi-algebraic setsMathematische Annalen, 1991