Optimization Online


Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets

Lucas Slot (Lucas.Slot***at***cwi.nl)
Monique Laurent (monique***at***cwi.nl)

Abstract: We consider the problem of computing the minimum value of a polynomial f over a compact set K⊆R^n, which can be reformulated as finding a probability measure ν on K minimizing the expected value of f over K. Lasserre showed that it suffices to consider such measures of the form ν=qμ, where q is a sum-of-squares polynomial and μ is a given Borel measure supported on K. By bounding the degree of q by 2r one gets a converging hierarchy of upper bounds for the original minimization problem. When K is the hypercube [−1,1]^n, equipped with the Chebyshev measure, these bounds are known to converge to the minimum value of f at a rate in O(1/r^2). We extend this error estimate to a wider class of convex bodies, while also allowing for a broader class of reference measures, including the Lebesgue measure. Our analysis applies to simplices, balls and convex bodies that locally look like a ball. In addition, we show an error estimate in O(log(r)/r) when K satisfies a minor geometrical condition, and in O((log(r)/r)^2) when K is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in O(1/sqrt(r)) and O(1/r) for these two respective cases.

Keywords: polynomial optimization sum-of-squares polynomial Lasserre hierarchy semidefinite programming needle polynomial

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Global Optimization

Citation: arXiv:1905.08142

Download: [PDF]

Entry Submitted: 05/21/2019
Entry Accepted: 05/21/2019
Entry Last Modified: 05/21/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society