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.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 ReadCube access
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
Record Number:CaltechAUTHORS:20200324-151107160
Persistent URL:
Official Citation:Parrilo, P. Semidefinite programming relaxations for semialgebraic problems. Math. Program., Ser. B 96, 293–320 (2003).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:102091
Deposited By: Tony Diaz
Deposited On:24 Mar 2020 22:18
Last Modified:16 Nov 2021 18:08

Repository Staff Only: item control page