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

Lucas Slot, Monique Laurent

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the problem of computing the minimum value fmin,K of a polynomial f over a compact set K⊆Rn, which can be reformulated as finding a probability measure ν on K minimizing ∫Kfdν. 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 f(r) for fmin,K. When K is the hypercube [−1,1]n, equipped with the Chebyshev measure, the parameters f(r) are known to converge to fmin,K at a rate in O(1/r2). 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(logr/r) when K satisfies a minor geometrical condition, and in O(log2r/r2) when K is a convex body, equipped with the Lebesgue measure. This improves upon the currently best known error estimates in O(1/r√) and O(1/r) for these two respective cases.
Original languageEnglish
JournalMathematical Programming
Early online dateJan 2020
DOIs
Publication statusPublished - 25 Jan 2020

Keywords

  • polynomial optimization
  • sum-of-squares polynomial
  • Lasserre hierarchy
  • semidefinite programming
  • needle polynomial

Fingerprint Dive into the research topics of 'Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets'. Together they form a unique fingerprint.

  • Cite this