Worst-case examples for Lasserre’s measure–based hierarchy for polynomial optimization on the hypercube

Etienne De Klerk, Monique Laurent

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Abstract

We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre, and a related hierarchy by de Klerk, Hess, and Laurent. For polynomial optimization over the hypercube, we show a refined convergence analysis for the first hierarchy. We also show lower bounds on the convergence rate for both hierarchies on a class of examples. These lower bounds match the upper bounds and thus establish the true rate of convergence on these examples. Interestingly, these convergence rates are determined by the distribution of extremal zeroes of certain families of orthogonal polynomials.

Original languageEnglish
Pages (from-to)86-98
Number of pages13
JournalMathematics of Operations Research
Volume45
Issue number1
DOIs
Publication statusPublished - 2020

Keywords

  • Extremal roots of orthogonal polynomials
  • Jacobi polynomials
  • Lasserre hierarchy
  • Polynomial optimization
  • Semidefinite optimization

Fingerprint Dive into the research topics of 'Worst-case examples for Lasserre’s measure–based hierarchy for polynomial optimization on the hypercube'. Together they form a unique fingerprint.

Cite this