### Abstract

Language | English |
---|---|

Journal | Mathematics of Operations Research |

Publication status | Accepted/In press - 2018 |

### Fingerprint

### Cite this

}

**Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube.** / de Klerk, Etienne; Laurent, Monique.

Research output: Contribution to journal › Article › Scientific › peer-review

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 - 2018

Y1 - 2018

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.

M3 - Article

JO - Mathematics of Operations Research

T2 - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

ER -