Noncommutative variables

Example 2.11

We consider the Example 2.11 of [BKP16] in which the polynomial with noncommutative variables $(x * y + x^2)^2 = x^4 + x^3y + xyx^2 + xyxy$ is tested to be sum-of-squares.

[BKP16] Sabine Burgdorf, Igor Klep, and Janez Povh. Optimization of polynomials in non-commuting variables. Berlin: Springer, 2016.

In [1]:
using DynamicPolynomials
@ncpolyvar x y
p = (x * y + x^2)^2
Out[1]:
$$ x^{4} + x^{3}y + xyx^{2} + xyxy $$
In [2]:
import CSDP
using JuMP
optimizer_constructor = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)
Out[2]:
MathOptInterface.OptimizerWithAttributes(CSDP.Optimizer, Pair{MathOptInterface.AbstractOptimizerAttribute,Any}[MathOptInterface.Silent() => true])

The Newton polytope method has not been adapted to the noncommutative case yet, so we force the choice of certificate to MaxDegree instead of Newton.

In [3]:
using SumOfSquares
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())
Out[3]:
$ (1)x^{4} + (1)x^{3}y + (1)xyx^{2} + (1)xyxy \text{ is SOS} $
In [4]:
optimize!(model)

We see that both the monomials xy and yx are considered separately, this is a difference with the commutative version.

In [5]:
certificate_basis(con_ref)
Out[5]:
MonomialBasis{Monomial{false},MonomialVector{false}}(Monomial{false}[x², xy])

We see that the solution correctly uses the monomial xy instead of yx. We also identify that only the monomials x^2 and xy would be needed. This would be dectected by the Newton chip method of [Section 2.3, BKP16].

In [6]:
gram_matrix(con_ref).Q
Out[6]:
2×2 SymMatrix{Float64}:
 1.0  1.0
 1.0  1.0

When asking for the SOS decomposition, the numerically small entries makes the solution less readable.

In [7]:
sos_decomposition(con_ref)
Out[7]:
(-1.0000000000000002*x^2 - x*y)^2 + (-6.265166515512128e-9*x^2 + 6.265166515512127e-9*x*y)^2

They are however easily discarded by using a nonzero tolerance:

In [8]:
sos_decomposition(con_ref, 1e-6)
Out[8]:
(-1.0000000000000002*x^2 - x*y)^2

Example 2.2

We consider now the Example 2.2 of [BKP16] in which the polynomial with noncommutative variables $(x + x^{10}y^{20}x^{10})^2$ is tested to be sum-of-squares.

In [9]:
using DynamicPolynomials
@ncpolyvar x y
n = 10
p = (x + x^n * y^(2n) * x^n)^2
Out[9]:
$$ x^{10}y^{20}x^{20}y^{20}x^{10} + x^{11}y^{20}x^{10} + x^{10}y^{20}x^{11} + x^{2} $$
In [10]:
using SumOfSquares
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())
Out[10]:
$ (1)x^{10}y^{20}x^{20}y^{20}x^{10} + (1)x^{11}y^{20}x^{10} + (1)x^{10}y^{20}x^{11} + (1)x^{2} \text{ is SOS} $
In [11]:
optimize!(model)

Only two monomials were considered for the basis of the gram matrix thanks to the Augmented Newton chip method detailed in [Section 2.4, BKP16].

In [12]:
certificate_basis(con_ref)
Out[12]:
MonomialBasis{Monomial{false},MonomialVector{false}}(Monomial{false}[x¹⁰y²⁰x¹⁰, x])
In [13]:
gram_matrix(con_ref).Q
Out[13]:
2×2 SymMatrix{Float64}:
 1.0  1.0
 1.0  1.0
In [14]:
sos_decomposition(con_ref, 1e-6)
Out[14]:
(-1.0000000000000002*x^10*y^20*x^10 - x)^2
In [ ]: