Near-optimal analysis of Lasserre’s univariate measure-based bounds for multivariate polynomial optimization

Lucas Slot, Monique Laurent

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

We consider a hierarchy of upper approximations for the minimization of a polynomial f over a compact set K⊆ R n proposed recently by Lasserre (arXiv:1907.097784, 2019). This hierarchy relies on using the push-forward measure of the Lebesgue measure on K by the polynomial f and involves univariate sums of squares of polynomials with growing degrees 2r. Hence it is weaker, but cheaper to compute, than an earlier hierarchy by Lasserre (SIAM Journal on Optimization 21(3), 864–885, 2011), which uses multivariate sums of squares. We show that this new hierarchy converges to the global minimum of f at a rate in O(log 2r/ r 2) whenever K satisfies a mild geometric condition, which holds, eg., for convex bodies and for compact semialgebraic sets with dense interior. As an application this rate of convergence also applies to the stronger hierarchy based on multivariate sums of squares, which improves and extends earlier convergence results to a wider class of compact sets. Furthermore, we show that our analysis is near-optimal by proving a lower bound on the convergence rate in Ω(1 / r 2) for a class of polynomials on K= [- 1 , 1] , obtained by exploiting a connection to orthogonal polynomials.
Original languageEnglish
JournalMathematical Programming
DOIs
Publication statusE-pub ahead of print - Oct 2020

Keywords

  • Lasserre hierarchy
  • sum-of-squares polynomial
  • semidefinite optimization
  • convergence analysis
  • orthogonal polynomials
  • needle polynomial

Fingerprint

Dive into the research topics of 'Near-optimal analysis of Lasserre’s univariate measure-based bounds for multivariate polynomial optimization'. Together they form a unique fingerprint.

Cite this