Positivstellensatz

A Positivstellensatz is one of a family of theorems that represents polynomials which are positive on a semialgebraic set and gives algebraic certificates for infeasible systems of polynomial inequalities.

For example, let . The Krivine-Stengle Positivstellensatz states that is the empty set iff there are sum-of-squares polynomials such that

The identity is a certificate of infeasibility analogous to Hilbert's Nullstellensatz for systems of polynomial equations (Krivine 1964, Stengle 1974).

Two important refinements concern polynomials which are strictly positive on . Schmüdgen's Positivstellensatz states that if is a compact set, then every such polynomial has a representation , where the are sums of squares. Putinar's Positivstellensatz assumes that there are sum-of-squares polynomials and a number such that . It then gives the simpler representation , where the are sums of squares. These representations underlie sum-of-squares optimization and its certificates for polynomial optimization.