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 6
o13 = x s + y t + x - x y - x y + y - x z + 3x y z - y z - x z - y z + z
o13 : R
|
i14 : sol = solveSOS g; |
i15 : sol#Parameters
o15 = | 285/8 |
| 285/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
$$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.
The object solveSOS is a method function with options.