## Semidefinite programming relaxations for semialgebraic problems

### Pablo A. Parrilo

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.