next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
SOS :: solveSOS(RingElement,RingElement,Matrix)

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

Synopsis

Description

This method allows to compute SOS 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)
Executing CSDP
Input file: /tmp/M2-21453-0/4.dat-s
Output file: /tmp/M2-21453-0/5
Status: SDP solved, primal-dual feasible
Start rational rounding

     +--------------+-----------------------+
o4 = | MomentMatrix | 3x3 matrix over RR_53 |
     +--------------+-----------------------+
     |  GramMatrix  |   3x3 matrix over QQ  |
     +--------------+-----------------------+
     |   Monomials  |   3x1 matrix over R   |
     +--------------+-----------------------+

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)
Executing CSDP
Input file: /tmp/M2-21453-0/8.dat-s
Output file: /tmp/M2-21453-0/9
Status: SDP solved, primal-dual feasible
Start rational rounding

     +--------------+-----------------------+
o5 = | MomentMatrix | 3x3 matrix over RR_53 |
     +--------------+-----------------------+
     |  GramMatrix  |   3x3 matrix over QQ  |
     +--------------+-----------------------+
     |   Monomials  |   3x1 matrix over R   |
     +--------------+-----------------------+

o5 : SDPResult

Parametrized SOS problems can also be solved in quotient rings.

i6 : S = R[t];
i7 : solveSOS(f-t,-t,mon,RoundTol=>12)
Executing CSDP
Input file: /tmp/M2-21453-0/12.dat-s
Output file: /tmp/M2-21453-0/13
Status: SDP solved, primal-dual feasible
Start rational rounding

     +--------------+-----------------------+
o7 = | MomentMatrix | 3x3 matrix over RR_53 |
     +--------------+-----------------------+
     |  GramMatrix  |   3x3 matrix over QQ  |
     +--------------+-----------------------+
     |   Monomials  |   3x1 matrix over R   |
     +--------------+-----------------------+
     |  Parameters  |   1x1 matrix over QQ  |
     +--------------+-----------------------+

o7 : SDPResult

Caveat

If an SOS decomposition is undertaken in the quotient ring with rational coefficients it can happen that rounding fails. In this case, an SOSPoly constructed from the 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);
Executing CSDP
Input file: /tmp/M2-21453-0/16.dat-s
Output file: /tmp/M2-21453-0/17
Status: SDP solved, primal-dual feasible
i12 : ring sosPoly s

o12 = RR  [x, y]
        53

o12 : PolynomialRing

In this case, one option is to construct a new quotient ring and work there. However, this will only work somewhat reliably in the case of a quotient modulo a principal ideal, as otherwise the Gröbner basis engine might fail on 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

See also