Combining sums of squares and Groebner basis techniques

Pablo A. Parrilo (Institut fur Automatik, Zurich)

We show how the algebraic structure of polynomial optimization problems with equality constraints can be exploited within the sum of squares / semidefinite programming framework. Using Groebner basis techniques, all computations can be done in the coordinate ring, notably decreasing the computational burden. Additionally, for zero dimensional systems, we obtain a simple constructive proof of the existence of distinguished sum of squares representations for polynomials nonnegative over semialgebraic sets. Degree bounds are directly obtained, as the cardinality of the support of the summands equals the number of points in the variety.