Cyclic symmetry for Sums of Hermitian Squares

We start by defining the Cyclic group.

using GroupsCore
import PermutationGroups

struct CyclicElem <: GroupElement
    n::Int
    id::Int
end
Base.:(==)(a::CyclicElem, b::CyclicElem) = a.n == b.n && a.id == b.id
Base.inv(el::CyclicElem) = CyclicElem(el.n, (el.n - el.id) % el.n)

function Base.:*(a::CyclicElem, b::CyclicElem)
    return CyclicElem(a.n, (a.id + b.id) % a.n)
end
Base.:^(el::CyclicElem, k::Integer) = CyclicElem(el.n, (el.id * k) % el.n)

Base.conj(a::CyclicElem, b::CyclicElem) = inv(b) * a * b
Base.:^(a::CyclicElem, b::CyclicElem) = conj(a, b)

function PermutationGroups.order(::Type{T}, el::CyclicElem) where {T}
    return convert(T, div(el.n, gcd(el.n, el.id)))
end

struct CyclicGroup <: Group
    n::Int
end
Base.parent(el::CyclicElem) = CyclicGroup(el.n)
Base.eltype(::CyclicGroup) = CyclicElem
Base.isfinite(::CyclicGroup) = true
Base.one(c::Union{CyclicGroup, CyclicElem}) = CyclicElem(c.n, 0)
PermutationGroups.gens(c::CyclicGroup) = [CyclicElem(c.n, 1)]
PermutationGroups.order(::Type{T}, c::CyclicGroup) where {T} = convert(T, c.n)
function Base.iterate(c::CyclicGroup, prev::CyclicElem=CyclicElem(c.n, -1))
    id = prev.id + 1
    if id >= c.n
        return nothing
    else
        next = CyclicElem(c.n, id)
        return next, next
    end
end

Now we define that the cyclic group acts on monomial by permuting variables cyclically. So for instance, CyclicElem(3, 1) would transform x_1^3*x_2*x_3^4 into x_1^4*x_2^3*x_3.

import MultivariatePolynomials as MP
import MultivariateBases as MB

using SumOfSquares

struct Action{V<:MP.AbstractVariable} <: Symmetry.OnMonomials
    variables::Vector{V}
end
Symmetry.SymbolicWedderburn.coeff_type(::Action) = Float64
function Symmetry.SymbolicWedderburn.action(a::Action, el::CyclicElem, mono::MP.AbstractMonomial)
    return prod(MP.powers(mono), init=MP.constant_monomial(mono)) do (var, exp)
        index = findfirst(isequal(var), a.variables)
        new_index = mod1(index + el.id, el.n)
        return a.variables[new_index]^exp
    end
end

using DynamicPolynomials
@polyvar x[1:3]
action = Action(x)
g = CyclicElem(3, 1)
Symmetry.SymbolicWedderburn.action(action, g, x[1]^3 * x[2] * x[3]^4)

\[ x_{1}^{4}x_{2}^{3}x_{3} \]

The following polynomial poly is invariant under the action of the group G.

N = 3
G = CyclicGroup(N)
poly = sum(x[i] * x[mod1(i + 1, N)] for i in 1:N) + sum(x.^2)
Symmetry.SymbolicWedderburn.action(action, g, poly)

\[ x_{3}^{2} + x_{2}x_{3} + x_{2}^{2} + x_{1}x_{3} + x_{1}x_{2} + x_{1}^{2} \]

Let's now find the minimum of p by exploiting this symmetry.

import Hypatia
solver = Hypatia.Optimizer
model = Model(solver)
@variable(model, t)
@objective(model, Max, t)
pattern = Symmetry.Pattern(G, action)
con_ref = @constraint(model, poly - t in SOSCone(), symmetry = pattern)
optimize!(model)
solution_summary(model)
solution_summary(; result = 1, verbose = false)
├ solver_name          : Hypatia
├ Termination
│ ├ termination_status : ALMOST_OPTIMAL
│ ├ result_count       : 1
│ └ raw_status         : NearOptimal
├ Solution (result = 1)
│ ├ primal_status        : NEARLY_FEASIBLE_POINT
│ ├ dual_status          : NEARLY_FEASIBLE_POINT
│ ├ objective_value      : -4.43375e-09
│ └ dual_objective_value : 1.33012e-08
└ Work counters
  ├ solve_time (sec)   : 3.40891e-03
  └ barrier_iterations : 15

Let's look at the symmetry adapted basis used.

gram_matrix(con_ref)
BlockDiagonalGramMatrix with 2 blocks:
[1] Block with row/column basis:
     MultivariateBases.SimpleBasis{DynamicPolynomials.Polynomial{Float64}}(DynamicPolynomials.Polynomial{Float64}[1.0 + 0.0 + 0.0 + 0.0, 0.0 - 0.5773502691896257x₃ - 0.5773502691896257x₂ - 0.5773502691896257x₁])
    And entries in a 2×2 SymMatrix{Float64}:
     4.433746725876596e-9  0.0
     0.0                   2.0000000000000004
[2] Block with row/column basis:
     MultivariateBases.SimpleBasis{DynamicPolynomials.Polynomial{Float64}}(DynamicPolynomials.Polynomial{Float64}[0.0 - 0.816496580927726x₃ + 0.4082482904638631x₂ + 0.4082482904638631x₁, 0.0 + 0.0 - 0.7071067811865477x₂ + 0.7071067811865477x₁])
    And entries in a 2×2 SymMatrix{Float64}:
     0.2500000007155502  0.0
     0.0                 0.24999999928445002

Let's look into more details at the last two elements of the basis.

basis = [(x[1] + x[2] - 2x[3])/√6, (x[1] - x[2])/√2]
2-element Vector{DynamicPolynomials.Polynomial{Float64}}:
 -0.8164965809277261x₃ + 0.4082482904638631x₂ + 0.4082482904638631x₁
 -0.7071067811865475x₂ + 0.7071067811865475x₁

These polynomials span an invariant subspace corresponding to a group character of degree 2 and multiplicity 1. The real formulation above uses a 2-by-2 Gram block for this subspace. We can verify its invariance under the group generator g by computing the image of each basis polynomial:

image = [Symmetry.SymbolicWedderburn.action(action, g, p) for p in basis]
2-element Vector{DynamicPolynomials.Polynomial{Float64}}:
 0.4082482904638631x₃ + 0.4082482904638631x₂ - 0.8164965809277261x₁
 -0.7071067811865475x₃ + 0.7071067811865475x₂

We can see that they are both still in the same 2-dimensional subspace.

a = -1/2
b = √3/2
[a -b; b a] * basis
2-element Vector{DynamicPolynomials.Polynomial{Float64}}:
 0.4082482904638631x₃ + 0.4082482904638629x₂ - 0.816496580927726x₁
 -0.7071067811865476x₃ + 0.7071067811865475x₂ + 5.551115123125783e-17x₁

In fact, these last two basis comes from the real decomposition of a complex one.

model = Model(solver)
@variable(model, t)
@objective(model, Max, t)
pattern = Symmetry.Pattern(G, action)
cone = SumOfSquares.NonnegPolyInnerCone{MOI.HermitianPositiveSemidefiniteConeTriangle}()
con_ref = @constraint(model, poly - t in cone, symmetry = pattern)
optimize!(model)
solution_summary(model)

gram_matrix(con_ref)
BlockDiagonalGramMatrix with 3 blocks:
[1] Block with row/column basis:
     MultivariateBases.SimpleBasis{DynamicPolynomials.Polynomial{ComplexF64}}(DynamicPolynomials.Polynomial{ComplexF64}[(1.0 - 0.0im) + (0.0 + 0.0im) + (0.0 + 0.0im) + (0.0 + 0.0im), (0.0 + 0.0im) + (-0.5773502691896257 - 0.0im)x₃ + (-0.5773502691896257 - 0.0im)x₂ + (-0.5773502691896257 - 0.0im)x₁])
    And entries in a 2×2 VectorizedHermitianMatrix{ComplexF64, Float64, ComplexF64}:
     5.917144645343195e-11 + 0.0im                 0.0 + 0.0im
                       0.0 + 0.0im  2.0000000000000004 + 0.0im
[2] Block with row/column basis:
     MultivariateBases.SimpleBasis{DynamicPolynomials.Polynomial{ComplexF64}}(DynamicPolynomials.Polynomial{ComplexF64}[(0.0 + 0.0im) + (-0.577350269189626 - 0.0im)x₃ + (0.28867513459481314 - 0.49999999999999994im)x₂ + (0.2886751345948128 + 0.5000000000000001im)x₁])
    And entries in a 1×1 VectorizedHermitianMatrix{ComplexF64, Float64, ComplexF64}:
     0.4999999999565962 + 0.0im
[3] Block with row/column basis:
     MultivariateBases.SimpleBasis{DynamicPolynomials.Polynomial{ComplexF64}}(DynamicPolynomials.Polynomial{ComplexF64}[(0.0 + 0.0im) + (-0.577350269189626 - 0.0im)x₃ + (0.2886751345948128 + 0.5000000000000001im)x₂ + (0.28867513459481314 - 0.49999999999999994im)x₁])
    And entries in a 1×1 VectorizedHermitianMatrix{ComplexF64, Float64, ComplexF64}:
     0.500000000043403 + 0.0im

We can see that the real invariant subspace was in fact coming from two complex conjugate complex invariant subspaces:

complex_basis = basis[1] + im * basis[2]
image = Symmetry.SymbolicWedderburn.action(action, g, complex_basis)

\[ (0.4082482904638631 - 0.7071067811865475im)x_{3} + (0.4082482904638631 + 0.7071067811865475im)x_{2} + (-0.8164965809277261 + 0.0im)x_{1} \]

And there is a direct correspondance between the representation of the real and complex versions:

(a + b * im) * complex_basis

\[ (0.4082482904638631 - 0.7071067811865476im)x_{3} + (0.4082482904638629 + 0.7071067811865475im)x_{2} + (-0.816496580927726 + 5.551115123125783e-17im)x_{1} \]


This page was generated using Literate.jl.