An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization

DOI10.1007/s40305-013-0017-8zbMath1277.90157OpenAlexW2017436952MaRDI QIDQ384182

Jia-Wang Nie

Publication date: 27 November 2013

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-013-0017-8

zbMATH Keywords

semidefinite programmingpolynomialssum of squaresapproximation boundLasserre's relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

An effective version of Schmüdgen's Positivstellensatz for the hypercube ⋮ Inhomogeneous polynomial optimization over a convex set: An approximation approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of Putinar's Positivstellensatz
• Quadratic programming with one negative eigenvalue is NP-hard
• Semidefinite programming relaxations for semialgebraic problems
• Estimating \(L^\infty\) norms by \(L^{2k}\) norms for functions on orbits.
• Minimizing polynomials via sum of squares over the gradient ideal
• Global Optimization with Polynomials and the Problem of Moments
• Handbook of semidefinite programming. Theory, algorithms, and applications