Macaulay2 » Documentation
Packages » SumsOfSquares :: solveSOS
next | previous | forward | backward | up | index | toc

solveSOS -- solve a sum-of-squares problem

Synopsis

Description

This method solves sums-of-squares 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;
 
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 sum of squares. 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;
 
i10 : sosPoly sol

       21   2    43 2    43      145 2    1027351    2
o10 = (--)(x  - ---)  + (--)(x + ---)  + (-------)(1)
        8       105      20      344      5779200

o10 : SOSPoly
 
i11 : sol#Parameters

o11 = | 29/8 |

               1       1
o11 : Matrix QQ  <-- QQ

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

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;
 
i15 : sol#Parameters

o15 = | 125/4 |
      | 125/4 |

               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

$$min_{p} \, 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 $x^2-3x$:

i16 : R = QQ[x][t];
 
i17 : f = x^2 - 3*x - t;
 
i18 : sol = solveSOS (f, -t, RoundTol=>12);
 
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 :

        
      

      

        
For the programmer

        
The object solveSOS is a method function with options.