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.
using DynamicPolynomials
@ncpolyvar x y
p = (x * y + x^2)^2
import CSDP
using JuMP
optimizer_constructor = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)
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
.
using SumOfSquares
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())
optimize!(model)
We see that both the monomials xy
and yx
are considered separately, this is a difference with the commutative version.
certificate_basis(con_ref)
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].
gram_matrix(con_ref).Q
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.
sos_decomposition(con_ref)
(-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:
sos_decomposition(con_ref, 1e-6)
(-1.0000000000000002*x^2 - x*y)^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.
using DynamicPolynomials
@ncpolyvar x y
n = 10
p = (x + x^n * y^(2n) * x^n)^2
using SumOfSquares
model = Model(optimizer_constructor)
con_ref = @constraint(model, p in SOSCone())
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].
certificate_basis(con_ref)
MonomialBasis{Monomial{false},MonomialVector{false}}(Monomial{false}[x¹⁰y²⁰x¹⁰, x])
gram_matrix(con_ref).Q
2×2 SymMatrix{Float64}: 1.0 1.0 1.0 1.0
sos_decomposition(con_ref, 1e-6)
(-1.0000000000000002*x^10*y^20*x^10 - x)^2