Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube

Etienne de Klerk () and Monique Laurent ()
Additional contact information
Etienne de Klerk: Tilburg University, 5037 AB Tilburg, Netherlands; Delft University of Technology, 2600 AA Delft, Netherlands;
Monique Laurent: Tilburg University, 5037 AB Tilburg, Netherlands; Centrum Wiskunde & Informatica (CWI), 1098 XG Amsterdam, Netherlands

Mathematics of Operations Research, 2020, vol. 45, issue 1, 86–98

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.

Keywords: polynomial optimization; semidefinite optimization; Lasserre hierarchy; extremal roots of orthogonal polynomials; Jacobi polynomials (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2018.0983 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:86-98

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().