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
