Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere

Etienne de Klerk, Monique Laurent

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

Abstract

We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure.
We show that the exact rate of convergence is Theta(1/r^2), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.
Original languageEnglish
JournalMathematical Programming
DOIs
Publication statusAccepted/In press - Jan 2020

Fingerprint

Convergence Analysis
Rate of Convergence
Polynomials
Upper bound
Polynomial
Related rates
Sum of squares
Expected Value
Minimization Problem
Probability density function
Probability distributions
Probability Distribution
Moment
Unit
Hierarchy

Cite this

de Klerk, Etienne ; Laurent, Monique. / Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. In: Mathematical Programming . 2020.
@article{172289bfdfda471a9c01a50f7a9548c2,
title = "Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere",
abstract = "We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure. We show that the exact rate of convergence is Theta(1/r^2), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.",
author = "{de Klerk}, Etienne and Monique Laurent",
year = "2020",
month = "1",
doi = "doi:10.1007/s10107-019-01465-1",
language = "English",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer",

}

de Klerk, E & Laurent, M 2020, 'Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere', Mathematical Programming . https://doi.org/doi:10.1007/s10107-019-01465-1

Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. / de Klerk, Etienne; Laurent, Monique.

In: Mathematical Programming , 01.2020.

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

TY - JOUR

T1 - Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere

AU - de Klerk, Etienne

AU - Laurent, Monique

PY - 2020/1

Y1 - 2020/1

N2 - We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure. We show that the exact rate of convergence is Theta(1/r^2), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.

AB - We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre [SIAM J. Optim. 21(3) (2011), pp. 864-885], for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respect to the surface measure. We show that the exact rate of convergence is Theta(1/r^2), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.

U2 - doi:10.1007/s10107-019-01465-1

DO - doi:10.1007/s10107-019-01465-1

M3 - Article

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -

de Klerk E, Laurent M. Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere. Mathematical Programming . 2020 Jan. https://doi.org/doi:10.1007/s10107-019-01465-1

Access to Document