Article ID: | iaor20041759 |
Country: | Germany |
Volume: | 96 |
Issue: | 2 |
Start Page Number: | 293 |
End Page Number: | 320 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Parrilo P.A. |
Keywords: | semidefinite programming |
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields.