Even reduction

using DynamicPolynomials
@polyvar x

(x,)

We would like to find the minimum value of the following polynomial:

poly = x^4 - 2x^2

using SumOfSquares

We define the custom action as follows:

struct OnSign <: Symmetry.OnMonomials end
using PermutationGroups
import SymbolicWedderburn
SymbolicWedderburn.coeff_type(::OnSign) = Float64
function SymbolicWedderburn.action(::OnSign, p::Permutation, mono::AbstractMonomial)
    if isone(p) || iseven(DynamicPolynomials.degree(mono))
        return 1 * mono
    else
        @assert p.perm == perm"(1,2)"
        return -1 * mono
    end
end
G = PermGroup([perm"(1,2)"])

Permutation group on 1 generator generated by
 (1,2)

We can exploit the symmetry as follows:

import CSDP
solver = CSDP.Optimizer
model = Model(solver)
@variable(model, t)
@objective(model, Max, t)
pattern = Symmetry.Pattern(G, OnSign())
con_ref = @constraint(model, poly - t in SOSCone(), symmetry = pattern)
optimize!(model)
value(t)

-1.0000000042451322

We indeed find -1, let's verify that symmetry was exploited:

gram_matrix(con_ref)

SparseGramMatrix{Float64, FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}, Float64, SymMatrix{Float64}}(GramMatrix{Float64, FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}, Float64, SymMatrix{Float64}}[GramMatrix{Float64, FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}, Float64, SymMatrix{Float64}}([0.9999999999997706 -1.0000000011333299; -1.0000000011333299 1.0000000042451878], FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}(DynamicPolynomials.Polynomial{true, Float64}[x², 1.0])), GramMatrix{Float64, FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}, Float64, SymMatrix{Float64}}([2.2671482296631143e-9;;], FixedPolynomialBasis{DynamicPolynomials.Polynomial{true, Float64}, Vector{DynamicPolynomials.Polynomial{true, Float64}}}(DynamicPolynomials.Polynomial{true, Float64}[x]))])

This page was generated using Literate.jl.