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

A sum of squares package for Macaulay 2

MPT Framework

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:
  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