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

# solveSOS(RingElement,RingElement,Matrix) -- sum-of-squares problem in a quotient ring

## Synopsis

• Function: solveSOS
• Usage:
solveSOS(f,mon)
solveSOS(f,objFun,mon)
solveSOS(f,D)
solveSOS(f,objFun,D)
• Inputs:
• f, , a polynomial
• objFun, , a linear function of the parameters (optional)
• mon, , a vector of monomials (alternatively a degree bound D)
• 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 allows to compute sums-of-square decompositions in quotient rings. A vector of monomials must be provided in this case.

 i1 : R = QQ[x,y]/ideal(x^2 + y^2 - 1); i2 : f = 10-x^2-y; i3 : mon = matrix {{1}, {x}, {y}}; 3 1 o3 : Matrix R <-- R i4 : solveSOS (f, mon) o4 = MomentMatrix 3x3 matrix over RR_53 GramMatrix 3x3 matrix over QQ Monomials 3x1 matrix over R Status SDP solved, primal-dual feasible o4 : SDPResult

If a degree bound $D$ is given, the method will use the vector of monomials of degree at most $D/2$.

 i5 : solveSOS (f, 2) o5 = MomentMatrix 3x3 matrix over RR_53 GramMatrix 3x3 matrix over QQ Monomials 3x1 matrix over R Status SDP solved, primal-dual feasible o5 : SDPResult

Parametrized sums-of-squares problems can also be solved in quotient rings.

 i6 : S = R[t]; i7 : solveSOS(f-t,-t,mon,RoundTol=>12) o7 = MomentMatrix 3x3 matrix over RR_53 GramMatrix 3x3 matrix over QQ Monomials 3x1 matrix over R Parameters 1x1 matrix over QQ Status SDP solved, primal-dual feasible o7 : SDPResult

Caveat

The rational rounding may also fail in quotient ring computations. In this case, the object SOSPoly constructed from the object SDPResult can live in a newly created ring, instead of the quotient that one started with.

 i8 : R = QQ[x,y]/ideal(x^2 + y^2 - 1); i9 : f = 10-x^2-y; i10 : mon = matrix {{1}, {x}, {y}}; 3 1 o10 : Matrix R <-- R i11 : s = solveSOS (f, mon, RoundTol=>infinity); i12 : ring sosPoly s o12 = RR [x..y] 53 o12 : PolynomialRing

The above ring is not a quotient ring. One can construct a new quotient ring and work there. However, this will only work reliably for principal ideals, as otherwise the Gröbner basis engine might fail due to inexact computations.

 i13 : R' = ring sosPoly s; i14 : S = R'/(sub (ideal (x^2 + y^2 - 1), R')) -- warning: experimental computation over inexact field begun -- results not reliable (one warning given per session) o14 = S o14 : QuotientRing i15 : sub (f, S) == sub (sosPoly s, S) o15 = false