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

Research output: Contribution to journalArticleScientificpeer-review

16 Downloads (Pure)

Abstract

We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. 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
JournalMathematics of Operations Research
Early online date2019
DOIs
Publication statusE-pub ahead of print - 2019

Fingerprint

Hypercube
Polynomials
Polynomial
Optimization
Convergence Rate
Rate of Convergence
Lower bound
Upper bound
Convergence Analysis
Orthogonal Polynomials
Optimization Problem
Hierarchy
Zero
Rate of convergence
Lower bounds
Convergence rate

Keywords

  • polynomial optimization
  • semidefinite optimization
  • Lasserre hierarchy
  • extremal roots of orthogonal polynomials
  • Jacobi polynomials

Cite this

@article{a939e3b3036142c9826307408ef8c306,
title = "Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube",
abstract = "We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. 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.",
keywords = "polynomial optimization, semidefinite optimization, Lasserre hierarchy, extremal roots of orthogonal polynomials, Jacobi polynomials",
author = "{de Klerk}, Etienne and Monique Laurent",
year = "2019",
doi = "https://doi.org/10.1287/moor.2018.0983",
language = "English",
journal = "Mathematics of Operations Research",
issn = "0364-765X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

TY - JOUR

T1 - Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube

AU - de Klerk, Etienne

AU - Laurent, Monique

PY - 2019

Y1 - 2019

N2 - We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. 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.

AB - We study the convergence rate of a hierarchy of upper bounds for polynomial optimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], and a related hierarchy by De Klerk, Hess and Laurent [SIAM J. Optim. 27(1), (2017) pp. 347-367]. 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.

KW - polynomial optimization

KW - semidefinite optimization

KW - Lasserre hierarchy

KW - extremal roots of orthogonal polynomials

KW - Jacobi polynomials

U2 - https://doi.org/10.1287/moor.2018.0983

DO - https://doi.org/10.1287/moor.2018.0983

M3 - Article

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

ER -