Symmetry reduction

Adapted from: SymbolicWedderburn example

import MutableArithmetics as MA
using MultivariatePolynomials
using MultivariateBases

using DynamicPolynomials
@polyvar x[1:4]

(DynamicPolynomials.Variable{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}}[x₁, x₂, x₃, x₄],)

We would like to find the minimum value of the polynomial

poly = sum(x) + sum(x.^2)

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

As we can decouple the problem for each x[i] for which x[i] + x[i]^2 has minimum value 0.25, we would expect to get -1 as answer. Can this decoupling be exploited by SumOfSquares as well ? For this, we need to use a certificate that can exploit the permutation symmetry of the polynomial.

using SumOfSquares

We define the symmetry group as a permutation group in the variables. In order to do that, we define the action of a permutation on a monomial as the monomial obtained after permuting the variables.

using PermutationGroups
G = PermGroup([perm"(1,2,3,4)"])

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

We can use this certificate as follows:

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

-1.0000000005215735

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

gram_matrix(con_ref).blocks

4-element Vector{GramMatrix{Float64, FixedPolynomialBasis{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Float64}, Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Float64}}}, Float64, SymMatrix{Float64}}}:
 GramMatrix with row/column basis:
 FixedPolynomialBasis([1.0, -0.5*x[4] - 0.5*x[3] - 0.5*x[2] - 0.5*x[1]])
And entries in a 2×2 SymMatrix{Float64}:
  1.0000000005215735  -1.0000000000000018
 -1.0000000000000018   0.9999999999999988
 GramMatrix with row/column basis:
 FixedPolynomialBasis([-0.7071067811865472*x[4] + 0.7071067811865475*x[2]])
And entries in a 1×1 SymMatrix{Float64}:
 0.9999999999999998
 GramMatrix with row/column basis:
 FixedPolynomialBasis([-0.7071067811865472*x[3] + 0.7071067811865475*x[1]])
And entries in a 1×1 SymMatrix{Float64}:
 0.9999999999999998
 GramMatrix with row/column basis:
 FixedPolynomialBasis([-0.5*x[4] + 0.5*x[3] - 0.5*x[2] + 0.5*x[1]])
And entries in a 1×1 SymMatrix{Float64}:
 0.9999999999999998

This page was generated using Literate.jl.