NCSOStoolsdemo - Cyclic equivalence and sum of hermitian squares

%**************************************************************************

% Cyclic equivalence and sum of hermitian squares                         *

%**************************************************************************

% -------------------------------------------------------------------------

% First we construct some symbolic noncommuting variables

% -------------------------------------------------------------------------

>> NCvars x y

% -------------------------------------------------------------------------

% We can check whether two polynomials f and g are cyclically equivalent,

% i.e., whether f - g is a sum of commutators.

% -------------------------------------------------------------------------

>> NCisCycEq(x^2*y*x + y*x^3, 2*x*y*x^2)

ans = 1

% -------------------------------------------------------------------------

% We can construct a canonical cyclically equivalent representative of the

% polynomial

% -------------------------------------------------------------------------

>> NCcycEqRep(x^2*y*x + y*x^3 + x*y*x + x^2*y - 2*y*x^2)

ans = 2*x^3*y

% -------------------------------------------------------------------------

% We can check whether the polynomial is cyclically equivalent to a sum of

% hermitian squares.

% -------------------------------------------------------------------------

>> f = x^4 - 2*x^2*y + y^2 + x*y - y*x;

>> [IsCycEq,X,base,sohs,g] = NCcycSos(f)

***** NCSOStools: module NCcycSos started *****

Input polynomial has (max) degree 4 and min degree 2.

Detected 5 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 28 monomials in 2 variables of degree at most 4 and at least 2.

Preprocessing the input polynomial ...

Returned cyclically equivalent polynomial with (max) degree 4 and min degree 2.

Detected 3 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 28 monomials in 2 variables of degree at most 4 and at least 2.

Using alpha degree to construct the monomial vector.

Keeping 2 monomials in the monomial vector.

Computing cyclically equivalent products ... done.

Preparing linear constraints ...

Number of linear constraints: 3.

Starting SDP solver ...

...

Residual norm: 2.8174e-015

Computing SOHS decomposition ... done.

Found SOHS decomposition with 2 factors.

IsCycEq = 1

X =  1.0000   -1.0000

    -1.0000    1.0000

base = 'y'

       'x*x'

sohs =     -x^2+y

       6e-008*x^2

g = 1*x^4-x^2*y-y*x^2+y^2

% -------------------------------------------------------------------------

% NCcycSos has many optional parameters. For example we can set the

% smallest value that is considered to be nonzero in numerical

% calculations.

% -------------------------------------------------------------------------

>> params.precision = 1e-5;

>> [IsCycEq,X,base,sohs,g] = NCcycSos(f,params)

***** NCSOStools: module NCcycSos started *****

Input polynomial has (max) degree 4 and min degree 2.

Detected 5 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 28 monomials in 2 variables of degree at most 4 and at least 2.

Preprocessing the input polynomial ...

Returned cyclically equivalent polynomial with (max) degree 4 and min degree 2.

Detected 3 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 28 monomials in 2 variables of degree at most 4 and at least 2.

Using alpha degree to construct the monomial vector.

Keeping 2 monomials in the monomial vector.

Computing cyclically equivalent products ... done.

Preparing linear constraints ...

Number of linear constraints: 3.

Starting SDP solver ...

...

Residual norm: 2.8174e-015

Computing SOHS decomposition ... done.

Found SOHS decomposition with 1 factors.

IsCycEq = 1

X =  1.0000   -1.0000

    -1.0000    1.0000

base = 'y'

       'x*x'

sohs = -x^2+y

g = x^4-x^2*y-y*x^2+y^2

% -------------------------------------------------------------------------

% We can compute the maximal epsilon such that f-epsilon is cyclically

% equivalent to a sum of hermitian squares.

% -------------------------------------------------------------------------

>> f = x^4 - 4*x^2*y + 8*y + 4*y^2 - 4*x^2;

>> [opt,X,base,sohs,g] = NCcycMin(f)

***** NCSOStools: module NCcycMin started *****

Input polynomial has (max) degree 4 and min degree 1.

Detected 5 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 30 monomials in 2 variables of degree at most 4 and at least 1.

Preprocessing the input polynomial ...

Returned cyclically equivalent polynomial with (max) degree 4 and min degree 0.

Detected 6 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

Constructing monomial vector with 4 monomials.

Computing cyclically equivalent products ... done.

Preparing linear constraints ...

Number of linear constraints: 8.

Starting SDP solver ...

...

Residual norm: 1.8939e-010

Computing SOHS decomposition ... done.

Found SOHS decomposition with 4 factors.

opt = -4.0000

X =  4.0000    4.0000   -0.0000   -2.0000

     4.0000    4.0000   -0.0000   -2.0000

    -0.0000   -0.0000    0.0000    0.0000

    -2.0000   -2.0000    0.0000    1.0000

base = ''

       'y'

       'x'

       'x*x'

sohs =                 2-x^2+2*y

       5.99e-006*x^2+5.55e-006*y

                    1.025e-005*x

                   4.91e-006*x^2

g = 4-4*x^2+1*x^4-2*x^2*y+8*y-2*y*x^2+4*y^2

% -------------------------------------------------------------------------

% NCcycMin has many optional parameters. For example we can set the

% smallest value that is considered to be nonzero in numerical

% calculations.

% -------------------------------------------------------------------------

>> params.precision = 1e-4;

>> [opt,X,base,sohs,g] = NCcycMin(f,params)

***** NCSOStools: module NCcycMin started *****

Input polynomial has (max) degree 4 and min degree 1.

Detected 5 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

There are 30 monomials in 2 variables of degree at most 4 and at least 1.

Preprocessing the input polynomial ...

Returned cyclically equivalent polynomial with (max) degree 4 and min degree 0.

Detected 6 monomials in 2 variables.

There are 31 monomials in 2 variables of degree at most 4.

Constructing monomial vector with 4 monomials.

Computing cyclically equivalent products ... done.

Preparing linear constraints ...

Number of linear constraints: 8.

Starting SDP solver ...

...

Residual norm: 1.8939e-010

Computing SOHS decomposition ... done.

Found SOHS decomposition with 1 factors.

opt = -4.0000

X =  4.0000    4.0000   -0.0000   -2.0000

     4.0000    4.0000   -0.0000   -2.0000

    -0.0000   -0.0000    0.0000    0.0000

    -2.0000   -2.0000    0.0000    1.0000

base = ''

       'y'

       'x'

       'x*x'

sohs = 2-x^2+2*y

g = 4-4*x^2+x^4-2*x^2*y+8*y-2*y*x^2+4*y^2

% -------------------------------------------------------------------------

% We can check if the second directional derivative of a polynomial is

% cyclically equivalent to a sum of hermitian squares.

% -------------------------------------------------------------------------

>> f = 1 + 2*x^2 + x*y + 2*y^2;

>> [iscConvex,g,sohs,h] = NCisCycConvex(f,10e-5)

iscConvex = 1

g = 4*h1^2+2*h1*h2+4*h2^2

sohs = 0.5*h1+2*h2

          1.937*h1

h = 4.0000323*h1^2+h1*h2+h2*h1+4*h2^2