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

solveSOS -- solve a sum-of-squares problem

Synopsis

Description

This method solves SOS problems. Given a rational (or real) polynomial f(x), it attempts to find a rational (or real) positive semidefinite matrix Q and a vector of monomials mon such that

f(x) = mon’ Q mon.

The algorithm first computes a floating point solution, and then tries to obtain an exact solution by rounding the numerical result. If the rounding fails, the numerical solution is returned.

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-33544-0/4.dat-s
Output file: /tmp/M2-33544-0/5
Status: SDP solved, primal-dual feasible
Start rational rounding
i4 : Q = sol#GramMatrix

o4 = | 2      1     -83/40 |
     | 1      43/20 0      |
     | -83/40 0     5      |

              3        3
o4 : Matrix QQ  <--- QQ
i5 : mon = sol#Monomials

o5 = | x2 |
     | xy |
     | y2 |

             3       1
o5 : Matrix R  <--- R
i6 : transpose(mon)*Q*mon - f

o6 = 0

             1       1
o6 : Matrix R  <--- R

SOS with parameters: If the coefficients of the polynomial are linearly parametrized, we can search for parameters which render a polynomial to be a SOS. In the following example, the variable t will be treated as a free parameter.

i7 : R = QQ[x][t];
i8 : f = (t-1)*x^4+1/2*t*x+1;
i9 : sol = solveSOS f;
Executing CSDP
Input file: /tmp/M2-33544-0/8.dat-s
Output file: /tmp/M2-33544-0/9
Status: SDP solved, primal-dual feasible
Start rational rounding
i10 : sosPoly sol

o10 = coeffs:
       21  43  1027351
      {--, --, -------}
        8  20  5779200
      gens:
        2    43      145
      {x  - ---, x + ---, 1}
            105      344

o10 : SOSPoly
i11 : sol#Parameters

o11 = | 29/8 |

               1        1
o11 : Matrix QQ  <--- QQ

It is possible to solve SOS problems with several parameters. In the following example we increase two of the coefficients of the Robinson polynomial until it becomes SOS

i12 : R = QQ[x,y,z][s,t]

o12 = R

o12 : PolynomialRing
i13 : g = library("Robinson", {x,y,z}) + s*x^6 + t*y^6

       6     6     6    4 2    2 4    6    4 2     2 2 2    4 2    2 4    2 4
o13 = x s + y t + x  - x y  - x y  + y  - x z  + 3x y z  - y z  - x z  - y z 
      -----------------------------------------------------------------------
         6
      + z

o13 : R
i14 : sol = solveSOS g;
Executing CSDP
Input file: /tmp/M2-33544-0/12.dat-s
Output file: /tmp/M2-33544-0/13
Status: SDP solved, primal-dual feasible
Start rational rounding
i15 : sol#Parameters

o15 = | 327/8 |
      | 327/8 |

               2        1
o15 : Matrix QQ  <--- QQ

SOS with parameter optimization: The method also allows to optimize a linear function of the parameters. More precisely, given a polynomial f(x;p) that depends affinely on some parameters p, we can solve the problem

minp   objFun(p)     s.t.     f(x; p)   is SOS

In the following example we minimize -t in order to find a lower bound for the polynomial x2-3x:

i16 : R = QQ[x][t];
i17 : f = x^2 - 3*x - t;
i18 : sol = solveSOS (f, -t, RoundTol=>12);
Executing CSDP
Input file: /tmp/M2-33544-0/16.dat-s
Output file: /tmp/M2-33544-0/17
Status: SDP solved, primal-dual feasible
Start rational rounding
i19 : sol#Parameters

o19 = | -9/4 |

               1        1
o19 : Matrix QQ  <--- QQ

By default the method tries to obtain rational values of the parameters. Since there is a trade-off between rounding and optimality, we specify the rounding precision as an optional input argument.


See also

Ways to use solveSOS :