Semidefinite Programming Relaxations for Semialgebraic Problems

Authors

Pablo A. Parrilo

Year

2003

Journal Paper

Source

Mathematical Programming

Identifiers

DOI 10.1007/s10107-003-0387-5

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.

Summary¶

Introduces a hierarchy of semidefinite relaxations for semialgebraic feasibility and optimization problems using sum-of-squares polynomial decompositions. The paper connects SDP, real algebraic geometry, and constructive Positivstellensatz certificates, forming a foundation for modern SOS optimization.