# Symmetry & SOS Optimization Compatibility Issues?

**URL:** <https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, scientific-computing, algebra, compatibility\
**Created:** [April 28, 2023, 7:59pm UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057 "2023-04-28T19:59:25Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![ilovemath](https://avatars.discourse-cdn.com/v4/letter/i/a88e4f/32.png) [@ilovemath](https://discourse.julialang.org/u/ilovemath)\
**Post date:** [April 28, 2023, 7:59pm UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/1 "2023-04-28T19:59:26Z")

</div>

Hello all,

I am trying to implement rotational symmetry for an SOS problem. In particular, I followed the example problem here: [Dihedral symmetry of the Robinson form · SumOfSquares](https://jump.dev/SumOfSquares.jl/stable/generated/Symmetry/dihedral_symmetry_of_the_robinson_form/).

My goal is to use a cyclic group instead for a simple rotation symmetry, I don’t need to implement the rotation piece, and this resulted in the following code.

```julia
using DynamicPolynomials
using SumOfSquares
using Mosek
using MosekTools
using PermutationGroups
using GroupsCore
using SymbolicWedderburn

include("/Users/elizabethc/Documents/Code/JULIA_SOS_Couette/CyclicGroup.jl")
struct CyclicAction <: Symmetry.OnMonomials end
SymbolicWedderburn.coeff_type(::CyclicAction) = Float64

@polyvar a[1:6]
poly3 = sum(a.^2) 

function SymbolicWedderburn.action(::CyclicAction, el::CyclicGroupElement, mono::AbstractMonomial)
       var_a3, var_a4 = a[4], a[3]; var_a5, var_a6 = a[6], a[5]
       sign_aodd = 1 <= el.residual <=2 ? -1 : 1
       sign_aeven = 2 <= el.residual ? -1 : 1
       return mono([a[1], a[2], a[3], a[4], a[5], a[6]] => [a[1], a[2], sign_aodd*var_a3, sign_aeven*var_a4, sign_aodd*var_a5, sign_aeven*var_a6])
       end
G = CyclicGroup(4)
pattern3 = Symmetry.Pattern(G, CyclicAction())

model3 = SOSModel(Mosek.Optimizer)
@variable(model3, α3)
con_ref3 = @constraint(model3, poly3 >= α3, symmetry = pattern3)
optimize!(model3)
@show termination_status(model3)
@show objective_value(model3)

```

This yields an infeasible result using the optimization toolbox Mosek, and an empty constraint result using the optimization toolbox CSDP, which makes no sense since polynomial `poly` is sum-of-squares by definition But, if I check that the symmetry is being correctly implemented using the following for loop

```julia
for g in G
    @show SymbolicWedderburn.action(CyclicAction(), g, poly)
end

```

it shows that the polynomial is invariant under the claimed rotation, as it should be. We can check the proper symmetry is being imposed with `lin = sum(a)`.

To see if I understood some structure incorrectly, I went back to the dihedral Robinson from example from the JuMP/SumOfSquares documentation, and thought to implement the exact same method, but instead of the polynomial being the Robsinson form p(x,y), I generalized it so that we have the new polynomial P(x\_1, x\_2,y\_1,y\_2) = p(x\_1,y\_1) + p(x\_2,y\_2). The Wedderburn action should be the same but now adjusted to make sure that the rotations and reflections are happening to (x\_i,y\_i), a very easy adjustment, and easily checked again by the for loop. If I then attempt to run the optimization model, I receive the following error, with a corresponding stacktrace:

` ERROR: No permutation can make [[0.0 1.0; -1.0 0.0], [0.0 -1.0; -1.0 0.0]] and [[0.0 1.0; -1.0 0.0], [0.0 1.0; 1.0 0.0]] match`

If I change the polynomial to a sum-of-squares, it declares feasibility and then gives me an optimal value t=-7.740740..., which is completely incorrect it should be 0. I can’t make heads nor tails of these errors, and the only person I know in my group who has experience with this is hypothesizing that it is actually a symmetry package compatibility issue with SOS. Any insight on what the issue might be would be greatly appreciated.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [April 28, 2023, 10:04pm UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/2 "2023-04-28T22:04:04Z")

</div>

Welcome to the forum @ilovemath, this is a question for @blegat.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [May 9, 2023, 11:07am UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/3 "2023-05-09T11:07:55Z")

</div>

@ilovemath I’m behind the symmetry reduction; is there a minimal runnable example you could provide?  
Is the `CyclicGroup.jl` the same as

> <https://github.com/kalmarek/GroupsCore.jl/blob/main/test/cyclic.jl>

?

@blegat Is this really an action `OnMonomials`? does transposition `x → -x` really fit into this?  
Here:

> <https://github.com/kalmarek/SymbolicWedderburn.jl/blob/f382e59495e5e0b80a1cc532fddf7d789d2d2f67/test/action_dihedral.jl#L80>

I’ve rewritten the dihedral action as `BySignedPermutations` where  
`action(act, g, basis_elt)` returns `(new_basis_elt, ±1)`.

---

<div class="post-metadata">

**Author:** ![ilovemath](https://avatars.discourse-cdn.com/v4/letter/i/a88e4f/32.png) [@ilovemath](https://discourse.julialang.org/u/ilovemath)\
**Post date:** [May 23, 2023, 3:44am UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/4 "2023-05-23T03:44:10Z")

</div>

Thanks @abulak. Yes, that is the correct script. With this script, my existing example is close to minimal. Here is one that is even more minimal:

```julia
using DynamicPolynomials
using SumOfSquares
using Mosek
using MosekTools
using PermutationGroups
using GroupsCore
using SymbolicWedderburn
using LinearAlgebra

include("/Users/elizabethc/Documents/Code/JULIA_SOS_Couette/CyclicGroup.jl")
struct CyclicAction <: Symmetry.OnMonomials end
SymbolicWedderburn.coeff_type(::CyclicAction) = Float64

@polyvar a[1:2]
function SymbolicWedderburn.action(::CyclicAction, el::CyclicGroupElement, mono::AbstractMonomial)
                     var_a1, var_a2 = a[2], a[1]
                     sign_aodd = 1 <= el.residual <=2 ? -1 : 1
                     sign_aeven = 2 <= el.residual ? -1 : 1
                     return mono([a[1], a[2]] => [sign_aodd*var_a1, sign_aeven*var_a2])
end
G = CyclicGroup(4)
pattern = Symmetry.Pattern(G, CyclicAction())
poly = a[1]^2 + a[2]^2
model = SOSModel(Mosek.Optimizer)
@variable(model, t)
@objective(model, Max, t)
con_ref = @constraint(model, poly -t >=0, symmetry = pattern)
optimize!(model)

```

This code yields an infeasible result. Not a clue why. (It is late, there could be a typo, will double check in the morning.)

As to the dihedral example, I went through trying to understand the exact differences here for the Robinson example. With the adjustment to use BySignedPermutation as the generator for the pattern for the SOS optimization problem for the Robinson form example, it throws the same error as I mentioned in my post when I generalize to p(x\_1, y\_1) + p(x\_2, y\_2) (same notation as in og post). So enforcing the Symmetry.pattern either with DihedralAction or DihedralActionSP does not seem to matter, which I’m not entirely surprised by.

P.S. The first struct for DihedralAction will throw an error if OnMonomials is not written as Symmetry.OnMonomials. I’m not including the files in lines 7-9 so unless it is specified in there that the prefix is unnecessary this is a typo.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [May 28, 2023, 10:13am UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/5 "2023-05-28T10:13:44Z")

</div>

@ilovemath it seems to me that the provided `action` function does not define a [group action](https://en.wikipedia.org/wiki/Group_action).  
Could you make sure that the following tests pass?

```julia
G = CyclicGroup(4)
act = CyclicAction()
basis = monomials(a, 0:2)

using Test
@testset "Action axioms" begin
    SW = SymbolicWedderburn
    for b in basis
        # the group identity acts as the identity function
        @test SW.action(act, one(G), b) == b
    end
    for b in basis
        for g in G
            for h in G
                # the action is right-associative, i.e. b^(g*h) = (b^g)^h
                @test SW.action(act, g * h, b) ==
                      SW.action(act, h, SW.action(act, g, b))
            end
        end
    end
end

```

---

<div class="post-metadata">

**Author:** ![blegat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blegat/32/217090_2.png) [@blegat](https://discourse.julialang.org/u/blegat)\
**Post date:** [May 31, 2023, 3:44pm UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/6 "2023-05-31T15:44:41Z")

</div>

Hi @ilovemath, thanks for reporting this issue. We are adding automatic checks to make sure you get a nice error if your action is not a group homomorphism in [add checks for group action correctness by kalmarek · Pull Request #56 · kalmarek/SymbolicWedderburn.jl · GitHub](https://github.com/kalmarek/SymbolicWedderburn.jl/pull/56)

---

<div class="post-metadata">

**Author:** ![ilovemath](https://avatars.discourse-cdn.com/v4/letter/i/a88e4f/32.png) [@ilovemath](https://discourse.julialang.org/u/ilovemath)\
**Post date:** [June 5, 2023, 8:29pm UTC](https://discourse.julialang.org/t/symmetry-sos-optimization-compatibility-issues/98057/7 "2023-06-05T20:29:12Z")

</div>

Thanks all, this was helpful. The problem ended up being extremely minor and a bit dumb. For future interested parties, here is the correct version of the minimal example:

```julia
using DynamicPolynomials
using SumOfSquares
using Mosek
using MosekTools
using PermutationGroups
using GroupsCore
using SymbolicWedderburn
using LinearAlgebra

include("/Users/elizabethc/Documents/Code/JULIA_SOS_Couette/CyclicGroup.jl")
struct CyclicAction <: Symmetry.OnMonomials end
SymbolicWedderburn.coeff_type(::CyclicAction) = Float64

@polyvar a[1:2]
function SymbolicWedderburn.action(::CyclicAction, el::CyclicGroupElement, mono::AbstractMonomial)
                     if isodd(el.residual)
                         var_a1, var_a2 = a[2], a[1]
                     else
                         var_a1, var_a2 = a[1], a[2]
                     end
                     sign_aodd = 1 <= el.residual <=2 ? -1 : 1
                     sign_aeven = 2 <= el.residual ? -1 : 1
                     return mono([a[1], a[2]] => [sign_aodd*var_a1, sign_aeven*var_a2])
end
G = CyclicGroup(4)
pattern = Symmetry.Pattern(G, CyclicAction())
poly = a[1]^2 + a[2]^2
model = SOSModel(Mosek.Optimizer)
@variable(model, t)
@objective(model, Max, t)
con_ref = @constraint(model, poly -t >=0, symmetry = pattern)
optimize!(model)

```