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
polynomial-time checkable 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.