CaltechAUTHORS
  A Caltech Library Service

Semidefinite programming relaxations for semialgebraic problems

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:
URLURL TypeDescription
https://doi.org/10.1007/s10107-003-0387-5DOIArticle
https://rdcu.be/b3dlHPublisherFree ReadCube access
ORCID:
AuthorORCID
Parrilo, Pablo A.0000-0003-1132-8477
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