Symmetry reduction

Adapted from: SymbolicWedderburn example

import MutableArithmetics
const MA = MutableArithmetics
using MultivariatePolynomials
const MP = MultivariatePolynomials
using MultivariateBases
const MB = MultivariateBases

using DynamicPolynomials
@polyvar x[1:4]

(DynamicPolynomials.PolyVar{true}[x₁, x₂, x₃, x₄],)

We would like to find the minimum value of the polynomial

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

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

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.000000000521566

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

for g in gram_matrix(con_ref).sub_gram_matrices
    println(g.basis.polynomials)
end

DynamicPolynomials.Polynomial{true, Float64}[1.0, -0.5x₁ - 0.5x₂ - 0.5x₃ - 0.5x₄]
DynamicPolynomials.Polynomial{true, Float64}[-0.7071067811865472x₁ + 0.7071067811865475x₃]
DynamicPolynomials.Polynomial{true, Float64}[-0.7071067811865472x₂ + 0.7071067811865475x₄]
DynamicPolynomials.Polynomial{true, Float64}[-0.5x₁ + 0.5x₂ - 0.5x₃ + 0.5x₄]

This page was generated using Literate.jl.