# 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.*