Parrilo, Pablo A. (2003) Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming, 96 (2). pp. 293-320. ISSN 0025-5610. doi:10.1007/s10107-003-0387-5. https://resolver.caltech.edu/CaltechAUTHORS:20200324-151107160
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200324-151107160
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.
Item Type: | Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
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. | |||||||||
Subject Keywords: | Finite Number; Application Field; Algebraic Geometry; Programming Condition; Polynomial Equality | |||||||||
Issue or Number: | 2 | |||||||||
DOI: | 10.1007/s10107-003-0387-5 | |||||||||
Record Number: | CaltechAUTHORS:20200324-151107160 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20200324-151107160 | |||||||||
Official Citation: | Parrilo, P. Semidefinite programming relaxations for semialgebraic problems. Math. Program., Ser. B 96, 293–320 (2003). https://doi.org/10.1007/s10107-003-0387-5 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 102091 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Tony Diaz | |||||||||
Deposited On: | 24 Mar 2020 22:18 | |||||||||
Last Modified: | 16 Nov 2021 18:08 |
Repository Staff Only: item control page