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.