next | previous | forward | backward | up | index | toc

# solveSOS -- solve a sum-of-squares problem

## Synopsis

• Usage:
solveSOS(f)
solveSOS(f,objFun)
• Inputs:
• f, , a polynomial
• objFun, , a linear function of the parameters (optional)
• Optional inputs:
• RoundTol => ..., default value 3, tolerance for rational rounding
• Solver => ..., default value null, picking a semidefinite programming solver
• TraceObj => ..., default value false, whether to use trace as the objective function
• Verbosity => ..., default value 0, control the level of information printed
• Outputs:

## 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.