The Helfried Peyrl Homepage

SOS.m2

A sum of squares package for Macaulay 2

Description

SOS is a Macaulay2 package for computing sum of squares (SOS) decompositions of polynomials with rational coefficients. The algorithm uses an interior point method to solve the underlying semidefinite program and tries to compute an exact decomposition from the numerical solution.

Presentation

Note: since an efficient SDP solver is an art in itself and beyond the scope of this project, the package simpleSDP just implements a very simple method which is not expected to work well on big problems.

Packages

SOS, computation of rational sum of squares decompositions; depends on the following three packages:
simpleSDP, a simple interior point solver
LDL, LDL' factorization for rational matrices
BlkDiag, for creating block-diagonal matrices

Installation

To use the SOS package you need a working installation of Macaulay 2 with version number at least 0.9.94.

Steps to install:

Download the packages SOS, simpleSDP, LDL, and BlkDiag to your working directory
Unzip the SOS package
Do one of the following:
- Launch Macaulay2 in your download directory and use the installPackage command to install the packages, e.g.,
```
 
i1 : installPackage "LDL" 
--installing package LDL in ../.Macaulay2/encap/LDL-1.5/ 
... 
```
  Since SOS is depending on the packages simpleSDP, LDL, and BlkDiag, it should be installed at last.
- If you do not want to install the packages permanently, include the download directory to Macaulay 2's path list.

Examples

Computing a SOS decomposition
The following example demonstrates how to use the function getSOS of the SOS package to compute a SOS decomposition of a polynomial.

i1 : loadPackage"SOS";

i2 : S = QQ[x,y];

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

i4 : (g,d) = getSOS f

.
.   
.

         2  2    2  1  2         2           7
o4 = ((- -*x  + y , -*x  + x*y, x ), (5, 2, --))
         5          2                       10

We can check with the sumSOS command whether the found decomposition matches the original polynomial


i5 : sumSOS(g,d)

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

o5 : QQ [x, y]

SOS with parameters
If the coefficients of the polynomial are linearly parameterized, we can also search for parameters which render a polynomial to be a SOS. In the following example, the variable a will be treated as a free parameter.
```
i6 : S = QQ[x,a];

i7 : f = (a-1)*x^4+1/2*a*x+1;

i8 : (g,d,aval) = getSOS (f,{a})

.
.
.


         2  2   1         2    5            21  211
o9 = ({- -*x  + -*x + 1, x  + --*x, x}, {1, --, ---}, | 2 |)
         5      2             21            25  420

o9 : Sequence
```
The last output argument contains the vector of parameters, i.e, a=2.
SOS with parameter optimization
Semidefinite programming also allows to optimize a linear functional of the decision variables. As an example we compute a lower bound of a polynomial by minimizing its constant term. Since there is a tradeoff between rounding and optimality, we specify the required rounding precision as an optional input argument.
```
i10 : S = QQ[x,t]

o10 = S

o10 : PolynomialRing

i11 : f = x^4 - 2*x + t;

i12 : (g,d,tVal) = getSOS (f,{t},t,rndTol=>3)

.
.
.

          1  2   4          10  2       2    5   9   19
o12 = ({- -*x  - -*x + 1, - --*x  + x, x }, {-, --, ---}, | 5/4 |)
          2      5           9               4  20  144
```