sosInIdeal -- sum of squares polynomial in ideal

Synopsis

Usage:

(sol,mult) = sosInIdeal(h,D)

sol = sosInIdeal(R,D)
Inputs:
- h, a matrix, row vector with polynomial entries
- D, an integer, bound on the degree of the SOS polynomial
- R, a quotient ring, a quotient of a polynomial ring
Optional inputs:
- RoundTol => ..., default value 3, tolerance for rational rounding
- Solver => ..., default value "CSDP", picking a semidefinite programming solver
- Verbosity => ..., default value 0, control the level of information printed
Outputs:
- sol, an instance of the type SDPResult,
- mult, a matrix, column vector with polynomial multipliers

Description

This methods finds sums-of-squares polynomials in ideals. It accepts two types of inputs that are useful for different purposes. The first invocation is to give a one row matrix with polynomial entries and a degree bound. The method then tries to find a sum of squares in the generated ideal. More precisely, given equations $h_1(x),...,h_m(x)$, the method looks for polynomial multipliers $h_i(x)$ such that $\sum_i l_i(x) h_i(x)$ is a sum of squares.

i1 : R = QQ[x,y,z];

i2 : h = matrix {{x^2-4*x+2*y^2, 2*z^2-y^2+2}};

             1      2
o2 : Matrix R  <-- R

i3 : (sol,mult) = sosInIdeal (h, 2);

i4 : sosPoly sol

      395    1      2    395    2
o4 = (---)(- -x + 1)  + (---)(z)
       2     2            2

o4 : SOSPoly

i5 : h * mult == sosPoly sol

o5 = true

The second invocation is on a quotient ring, also with a degree bound. This tries to decompose the zero of the quotient ring as a sum of squares.

i6 : S = R/ideal h;

i7 : sol = sosInIdeal (S, 2);

i8 : sosPoly sol

      1031833    1      2    1031833    2
o8 = (-------)(- -x + 1)  + (-------)(z)
        2048     2             2048

o8 : SOSPoly

i9 : sosPoly sol

      1031833    1      2    1031833    2
o9 = (-------)(- -x + 1)  + (-------)(z)
        2048     2             2048

o9 : SOSPoly

Caveat

This implementation only works with the solvers "CSDP" and "MOSEK".

Ways to use sosInIdeal :

sosInIdeal(Matrix,ZZ)
sosInIdeal(Ring,ZZ)

For the programmer

The object sosInIdeal is a method function with options.