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

2019/04/18 by de Klerk, Etienne, Laurent, Monique
#90C22 #90C26 #90C30 #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1904.08828

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²), and explore the implications for the related rate of convergence for the generalized problem of moments on the sphere.

Related

• Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
• Convergence analysis for Lasserre's measure--based hierarchy of upper bounds for polynomial optimization
• Worst-case examples for Lasserre's measure--based hierarchy for\n polynomial optimization on the hypercube
• Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere
• Bound-constrained polynomial optimization using only elementary calculations