Description
SumsOfSquares is a package to solve sumsofsquares (SOS) problems via
semidefinite programming (SDP).
Introduction
Writing a polynomial as a sum of squares proves its nonnegativity for all arguments, but not all nonnegative polynomials are sum of squares. While nonnegativity of a polynomial is hard to check, there are efficient methods to find sumsofsquares decompositions, and this package makes some of them available in Macaulay2. These methods rely on semidefinite programming, an area from mathematical optimization. Several solvers (or tools) for semidefinite programming are available. The package
SemidefiniteProgramming allows us to use some of these solvers in Macaulay2. The solver
CSDP is included in Macaulay2 and can be used without any configuration. See
Solver for how to use other solvers.
Usage examples
The most basic application is to (try to) decompose a polynomial as a sum of squares using the function
solveSOS.
i1 : R = QQ[x,y];

i2 : f = 2*x^4 + 2*x^3*y  2*x^2*y^2 + 5*y^4;

i3 : sol = solveSOS f;

The return value is an object of type
SDPResult which, in the case of success, contains the sumofsquares decomposition. It can be extracted with
sosPoly. This returns an object of type
SOSPoly, which supports many operations that polynomials support.
i4 : s = sosPoly sol
83 2 2 2 43 20 2 2 231773 2 2
o4 = (5)( x + y ) + ()(x + x*y) + ()(x )
200 20 43 344000
o4 : SOSPoly

The command
value(SOSPoly) can be used to check that the decomposition found matches the original polynomial.
i5 : value(s)
4 3 2 2 4
o5 = 2x + 2x y  2x y + 5y
o5 : R

Sums of squares modulo equality constraints
The package supports sumofsquares
problems in quotient rings. This can be useful to prove nonnegativity of a polynomial on a variety. The following example is taken from [P05]. Consider the problem of proving that the polynomial
f = 10x^{2}y is nonnegative on the circle defined by
g = x^{2} + y^{2}  1. To do this we check if
f is a sum of squares in the quotient ring modulo
g. For such a computation, a degree bound must be given by the user.
i6 : R = QQ[x,y];

i7 : S = R/ideal(x^2 + y^2  1);

i8 : f = 10x^2y;

i9 : sol = solveSOS (f, 2);

i10 : sosPoly sol
1 2 2 83 2
o10 = (7)(y  ) + (6)(x) + ()(1)
14 28
o10 : SOSPoly

The previous computation gives decomposition with three sums of squares. See
TraceObj for how to obtain a decomposition with only two squares.
Other cool stuff

The package implements Hilbert's algorithm to decompose a nonnegative ternary form into a sum of squares of rational functions: sosdecTernary.

Sums of squares problems can be solved parametrically: solveSOS.

Optimization over varieties can run using lowerBound.
On the role of the coefficient field
The
SumsOfSquares package interfaces tries to hide some of the difficulties that arise from using these numerical procedures. See
coefficient field for more information.
Literature

[BPT12] Semidefinite Optimization and Convex Algebraic Geometry SIAM Textbook, edited by G. Blekherman, P. Parrilo, and R. Thomas, (2012).

[P05] Exploiting Algebraic Structure in Sum of Squares Programs P. Parrilo in Positive polynomials in control (2005).

[PP] Computing sum of squares decompositions with rational coefficients H. Peyrl and P. Parrilo in Theoretical Computer Science 409 (2008) p. 269–281.