Testing whether a polynomial is a sum of squares (sos) instead of whether it is nonnegative (psd) has become a popular relaxation approach, because testing for being a sum of squares is a semidefinite optimization problem. This relaxation performs well in practice. The problem of comparing psd polynomials to sums of squares has a long history, there are numerous explicit constructions of nonnegative polynomials that are not sos, and we have an asymptotic understanding of the relationship between nonnegative and sos polynomials. However, even in the smallest cases for which there exist psd polynomials that are not sos, we have not had a complete understanding of the difference between these sets.
In these cases, sums of squares must satisfy additional linear inequalities. We consider the dual cone to the cone of sums of squares and study its extreme rays. In the smallest cases where there exist nonnegative polynomials that are not sos (2 variables degree 6 and 3 variables degree 4) we classify all inequalities that are satisfied by sos polynomials but are not satisfied by nonnegative polynomials. The classification is in terms of 9 point inequalities in the case (2,6) and 8 point inequalities in the case (3,4). We also provide structural theorems for the extreme rays of the dual cone in the higher cases. (Some of this work is joint with Arend Bayer).
Copyright. All Rights Reserved.