The SOS hierarchy on the sphere converges at rate O(d^2/l^2) for homogeneous polynomials of degree 2n with n≤d, quadratically improving Reznick's O(d/l).
Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
math.OC 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
The sum-of-squares hierarchy on the sphere, and applications in quantum information theory
The SOS hierarchy on the sphere converges at rate O(d^2/l^2) for homogeneous polynomials of degree 2n with n≤d, quadratically improving Reznick's O(d/l).