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 ring element, a polynomial
- objFun, a ring element, a linear function of the parameters (optional)
- mon, a matrix, 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:
- an instance of the type SDPResult,

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

Ways to use this method: