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

N1 - Funding Information:
We thank two anonymous referees for their useful remarks. This work has been supported by European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie Grant Agreement 813211 (POEMA).
Publisher Copyright:
© 2020, The Author(s).

PY - 2022/6

Y1 - 2022/6

N2 - We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r is an element of N 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 rate of convergence is O (1/r(2)) and we give a class of polynomials of any positive degree for which this rate is tight. In addition, we 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):864-885, 2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r is an element of N 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 rate of convergence is O (1/r(2)) and we give a class of polynomials of any positive degree for which this rate is tight. In addition, we explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.

KW - polynomial optimization on sphere

KW - Lasserre hierarchy

KW - semidefinite programming

KW - generalized eigenvalue problem

U2 - 10.1007/s10107-019-01465-1

DO - 10.1007/s10107-019-01465-1

M3 - Article

SN - 0025-5610

VL - 193

SP - 665

EP - 685

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -