Published May 2003
| public
Journal Article
Semidefinite programming relaxations for semialgebraic problems
- Creators
-
Parrilo, Pablo A.
Abstract
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.
Additional Information
© 2003 Springer-Verlag. Issue Date: May 2003. I would like to acknowledge the useful comments of my advisor John Doyle, Stephen Boyd, and Bernd Sturmfels. In particular, Bernd suggested the example in Section 7.3. I also thank the reviewers, particularly Reviewer #2, for their useful and constructive comments.Additional details
- Eprint ID
- 102091
- Resolver ID
- CaltechAUTHORS:20200324-151107160
- Created
-
2020-03-24Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field