next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SOS :: SOS

SOS -- A package for sums-of-squares problems

Description

SOS is a package to solve sum-of-squares (SOS) problems. The main tool behind this package is 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 sums-of-squares decompositions and this package makes some of them available in Macaulay2. These methods rely on semidefinite-programming solvers from mathematical optimization. The semidefinite programming package in Macaulay2 ships with the CSDP solver so that everything is set up. Check Solver for how to configure different 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+5*y^4-2*x^2*y^2+2*x^3*y;
i3 : sol = solveSOS f;
Executing CSDP
Input file: /tmp/M2-2709-0/4.dat-s
Output file: /tmp/M2-2709-0/5
Status: SDP solved, primal-dual feasible
Start rational rounding
The return value is an object of type SDPResult which, in the case of success, contains in particular the SOS 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

o4 = coeffs:
         43  231773
     {5, --, ------}
         20  344000
     gens:
         83 2    2  20 2         2
     {- ---x  + y , --x  + x*y, x }
        200         43

o4 : SOSPoly
The command sumSOS can be used to check that the found decomposition matches the original polynomial:
i5 : sumSOS(s)

       4     3      2 2     4
o5 = 2x  + 2x y - 2x y  + 5y

o5 : R

Sums of squares modulo equality constraints

The package supports SOS decompositions 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 = 10-x2-y is nonnegative on the circle defined by g = x2 + y2 - 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 = 10-x^2-y;
i9 : sol = solveSOS (f, 2);
Executing CSDP
Input file: /tmp/M2-2709-0/8.dat-s
Output file: /tmp/M2-2709-0/9
Status: SDP solved, primal-dual feasible
Start rational rounding
i10 : sosPoly sol

o10 = coeffs:
             83
      {7, 6, --}
             28
      gens:
            1
      {y - --, x, 1}
           14

o10 : SOSPoly
See TraceObj for how to reduce the number of summands to 2.

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 coefficients field

The SOS package interfaces tries to hide some of the difficulties that arise from using these numerical procedures. See coefficients 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

Authors

Version

This documentation describes version 2.0 of SOS.

Source code

The source code from which this documentation is derived is in the file SOS.m2. The auxiliary files accompanying it are in the directory SOS/.

Exports

  • Types
    • SDPResult -- result of an SDP computation
    • SOSPoly -- A type to store SOS decompositions of polynomials
  • Functions and commands
  • Methods
    • clean(RR,SOSPoly) -- Remove terms with very small coefficients from a sum-of-squares.
    • recoverSolution(SDPResult), see recoverSolution -- Factor a rank one PSD matrix
    • net(SDPResult), see SDPResult -- result of an SDP computation
    • coefficients(SOSPoly), see SOSPoly -- A type to store SOS decompositions of polynomials
    • generators(SOSPoly), see SOSPoly -- A type to store SOS decompositions of polynomials
    • length(SOSPoly), see SOSPoly -- A type to store SOS decompositions of polynomials
    • Matrix == SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • net(SOSPoly), see SOSPoly -- A type to store SOS decompositions of polynomials
    • Number * SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • ring(SOSPoly), see SOSPoly -- A type to store SOS decompositions of polynomials
    • RingElement == SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly * SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly + SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly == Matrix, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly == RingElement, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly == SOSPoly, see SOSPoly -- A type to store SOS decompositions of polynomials
    • SOSPoly ^ ZZ, see SOSPoly -- A type to store SOS decompositions of polynomials
    • substitute(SOSPoly,Ring), see SOSPoly -- A type to store SOS decompositions of polynomials
    • sosPoly(SDPResult), see sosPoly -- make an SOS polynomial
    • sumSOS(SOSPoly), see sumSOS -- expansion of a weighted SOS decomposition
  • Symbols
    • RoundTol -- tolerance for rational rounding
    • GramMatrix, see SDPResult -- result of an SDP computation
    • MomentMatrix, see SDPResult -- result of an SDP computation
    • TraceObj -- whether to use trace as the objective function