Back to Search
Start Over
Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere
- Source :
- Mathematical Programming, 193(2), 665-685. Springer, Mathematical Programming, 193, 665-685
- Publication Year :
- 2020
- Publisher :
- Springer Science and Business Media LLC, 2020.
-
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.<br />14 pages, 2 figures
- Subjects :
- Surface (mathematics)
Polynomial
General Mathematics
0211 other engineering and technologies
010103 numerical & computational mathematics
02 engineering and technology
Expected value
01 natural sciences
Upper and lower bounds
Combinatorics
Convergence (routing)
FOS: Mathematics
0101 mathematics
Mathematics - Optimization and Control
Lasserre hierarchy
90C22, 90C26, 90C30
Mathematics
generalized eigenvalue problem
021103 operations research
Hierarchy (mathematics)
semidefinite programming
Rate of convergence
Optimization and Control (math.OC)
Probability distribution
polynomial optimization on sphere
Software
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 193
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....636d2a25dadc4d787049f12a9372849d