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

Description

SumsOfSquares is a package to solve sums-of-squares (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 sums-of-squares 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 sum-of-squares 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 sum-of-squares 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 = 10-x^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 = 10-x^2-y;

i9 : sol = solveSOS (f, 2);

i10 : sosPoly sol

       79       4 2    71    2     63    2
o10 = (--)(y - --)  + (--)(x)  + (---)(1)
        8      79       8         632

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.

Acknowledgement

Special thanks: Ilir Dema, Nidhi Kaihnsa, Anton Leykin.

References

[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

Certification

Version 2.1 of this package was accepted for publication in volume 10 of The Journal of Software for Algebra and Geometry on 6 January 2020, in the article Sums of squares in Macaulay2 (DOI: 10.2140/jsag.2020.10.17). That version can be obtained from the journal or from the Macaulay2 source code repository.

Version

This documentation describes version 2.2 of SumsOfSquares.

Source code

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

Exports

Types
- SDPResult -- result of a semidefinite programming computation
- SOSPoly -- A type to store sums-of-squares polynomials
Functions and commands
- checkSolver -- tests a semidefinite programming solver
- library -- library of interesting nonnegative forms
- lowerBound -- finds a lower bound for a polynomial
- recoverSolution -- factor a rank one positive semidefinite matrix
- solveSOS -- solve a sum-of-squares problem
- sosdecTernary -- sum of squares decomposition for ternary forms
- sosInIdeal -- sum of squares polynomial in ideal
- sosPoly -- make an SOS polynomial
Methods
- checkSolver(String) -- see checkSolver -- tests a semidefinite programming solver
- checkSolver(String,Function) -- see checkSolver -- tests a semidefinite programming solver
- checkSolver(String,String) -- see checkSolver -- tests a semidefinite programming solver
- clean(RR,SOSPoly) -- remove squares with very small coefficients from a sum of squares
- library(String,List) -- see library -- library of interesting nonnegative forms
- library(String,Ring) -- see library -- library of interesting nonnegative forms
- lowerBound(RingElement) -- see lowerBound -- finds a lower bound for a polynomial
- lowerBound(RingElement,Matrix,ZZ) -- see lowerBound -- finds a lower bound for a polynomial
- lowerBound(RingElement,ZZ) -- see lowerBound -- finds a lower bound for a polynomial
- recoverSolution(Matrix,Matrix) -- see recoverSolution -- factor a rank one positive semidefinite matrix
- recoverSolution(SDPResult) -- see recoverSolution -- factor a rank one positive semidefinite matrix
- net(SDPResult) -- see SDPResult -- result of a semidefinite programming computation
- status(SDPResult) -- see SDPResult -- result of a semidefinite programming computation
- solveSOS(RingElement) -- see solveSOS -- solve a sum-of-squares problem
- solveSOS(RingElement,RingElement) -- see solveSOS -- solve a sum-of-squares problem
- solveSOS(RingElement,Matrix) -- see solveSOS(RingElement,RingElement,Matrix) -- sum-of-squares problem in a quotient ring
- solveSOS(RingElement,RingElement,Matrix) -- sum-of-squares problem in a quotient ring
- solveSOS(RingElement,RingElement,ZZ) -- see solveSOS(RingElement,RingElement,Matrix) -- sum-of-squares problem in a quotient ring
- solveSOS(RingElement,ZZ) -- see solveSOS(RingElement,RingElement,Matrix) -- sum-of-squares problem in a quotient ring
- sosdecTernary(RingElement) -- see sosdecTernary -- sum of squares decomposition for ternary forms
- sosInIdeal(Matrix,ZZ) -- see sosInIdeal -- sum of squares polynomial in ideal
- sosInIdeal(Ring,ZZ) -- see sosInIdeal -- sum of squares polynomial in ideal
- coefficients(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- expression(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- generators(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- length(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- Matrix == SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- net(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- Number * SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- ring(SOSPoly) -- see SOSPoly -- A type to store sums-of-squares polynomials
- RingElement == SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly * SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly + SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly == Matrix -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly == RingElement -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly == SOSPoly -- see SOSPoly -- A type to store sums-of-squares polynomials
- SOSPoly ^ ZZ -- see SOSPoly -- A type to store sums-of-squares polynomials
- substitute(SOSPoly,Ring) -- see SOSPoly -- A type to store sums-of-squares polynomials
- sosPoly(List,List) -- see sosPoly -- make an SOS polynomial
- sosPoly(Matrix,Matrix) -- see sosPoly -- make an SOS polynomial
- sosPoly(Ring,List,List) -- see sosPoly -- make an SOS polynomial
- sosPoly(SDPResult) -- see sosPoly -- make an SOS polynomial
- value(SOSPoly) -- expansion of a weighted SOS decomposition
Symbols
- RoundTol -- tolerance for rational rounding
- GramMatrix -- see SDPResult -- result of a semidefinite programming computation
- MomentMatrix -- see SDPResult -- result of a semidefinite programming computation
- Status -- see SDPResult -- result of a semidefinite programming computation
- TraceObj -- whether to use trace as the objective function

For the programmer

The object SumsOfSquares is a package.