Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

## SOS.m2

### 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.

### 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:
1. Download the packages `SOS`, `simpleSDP`, `LDL`, and `BlkDiag` to your working directory
2. Unzip the SOS package
3. 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

```

 © 1999-2010 by ETH Zurich | Helfried Peyrl | April  5, 2010