# Symmetry reduction in Sumsofsquares

I have a simple minimization with symmetry, but Julia gives an error while using symmetry reduction.
I want to find the minimum of x_1^4+x_2^4+x_3^4-4x_1x_2x_3+x_1+x_2+x_3.

Here is my script:

``````using SumOfSquares
using PermutationGroups
using DynamicPolynomials
using MosekTools

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

@polyvar x[1:3]
f= sum(x.^4)+sum(x)-4*x[1]*x[2]*x[3]

m=Model(Mosek.Optimizer)
PolyJuMP.setdefault!(m, PolyJuMP.NonNegPoly, SOSCone)

@variable m lb
pattern = Symmetry.Pattern(G, Symmetry.VariablePermutation())
@constraint m f-lb>=0 symmetry=pattern
@objective m Max lb
optimize!(m)
``````

I get the following error:

``````No permutation can make [[-0.5 0.8660254037844388; -0.8660254037844385 -0.5], [1.0 0.0; 0.0 -1.0]] and [[-0.5 -0.8660254037844388; 0.8660254037844385 -0.5], [-0.5 0.8660254037844388; 0.8660254037844385 0.5]] match
``````

This polynomial has the symmetry of cyclic group of order 2, cyclic group of order 3, and symmetry group of order 3. So no matter which group I pick for symmetry reduction, at the end I need to get the same answer. However, this is not the case.
Without symmetry, the answer is -2.11.
If I choose `G= PermGroup([perm"(1,2)"])`, then every thing works.
If I choose `G= PermGroup([perm"(1,2,3)"])`, then I get -95.47!!!
And If I choose `G= PermGroup([perm"(1,2,3)",perm"(1,2)"])`, I get that error.

Here is a minimal example similar to SumOfSquares documentation:

``````import MutableArithmetics as MA
using MultivariatePolynomials
using MultivariateBases
using DynamicPolynomials
@polyvar x[1:3]
poly = sum(x) + sum(x.^4)
using PermutationGroups
G = PermGroup([perm"(1,2,3)",perm"(1,2)"])
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)
``````

This does not work, but if you change `poly = sum(x) + sum(x.^4)` to `poly = sum(x) + sum(x.^2)` it will work

Thanks for letting us know of the issue, can you open an issue in SumOfSquares.jl ? Weâ€™re making a large refactoring so weâ€™ll check whether this is still failing after the refactoring

I am not sure how I can do that. What should I do?

If you have a GitHub account: https://github.com/jump-dev/SumOfSquares.jl/issues/new, otherwise, I can do it.

Indeed this seems to be the problem with SumOfSquares.jl formulation, as `SymbolicWedderburn.jl` correctly reduces the optimization problem:

``````import PermutationGroups as PG
import AbstractPermutations as AP

using SymbolicWedderburn
import SymbolicWedderburn.SA as SA

using Pkg
Pkg.activate("examples")

include("examples/action_polynomials.jl")
include("examples/sos_problem.jl")
include("examples/solver.jl")

using DynamicPolynomials
@polyvar x[1:3]
poly = sum(x) + sum(x .^ 4)
# poly = sum(x.^4)+sum(x)-4*x[1]*x[2]*x[3]
``````

# No symmetry

``````no_symmetry = let poly = poly
m, model_creation_t = @timed sos_problem(poly)
JuMP.set_optimizer(
m,
scs_optimizer(; max_iters = 20_000, eps = 1e-7, accel = 20),
)

optimize!(m)
(
status = termination_status(m),
objective = objective_value(m),
creation_t = model_creation_t,
solve_t = solve_time(m),
)
end
``````

Results:

``````------------------------------------------------------------------
SCS v3.2.4 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 56, constraints m: 90
cones:    z: primal zero / dual free vars: 35
s: psd vars: 55, ssize: 1
settings: eps_abs: 1.0e-07, eps_rel: 1.0e-07, eps_infeas: 1.0e-07
alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
max_iters: 20000, normalize: 1, rho_x: 1.00e-06
acceleration_lookback: 20, acceleration_interval: 10
lin-sys:  sparse-direct-amd-qdldl
nnz(A): 111, nnz(P): 0
------------------------------------------------------------------
iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
0| 2.20e+01  1.00e+00  2.29e+01 -1.06e+01  1.00e-01  2.43e-04
175| 3.71e-09  1.20e-09  2.00e-08  1.42e+00  6.08e-01  1.33e-03
------------------------------------------------------------------
status:  solved
timings: total: 1.34e-03s = setup: 1.93e-04s + solve: 1.14e-03s
lin-sys: 1.52e-04s, cones: 8.63e-04s, accel: 8.44e-06s
------------------------------------------------------------------
objective = 1.417411
------------------------------------------------------------------
(status = MathOptInterface.OPTIMAL, objective = -1.417411154605916, symmetry_adaptation_t = 0.0, creation_t = 0.020466669, solve_t = 0.0013355219999999998)
``````

# SymbolicWedderburn decomposition

``````wedderburn_dec =
let poly = poly,
G = PermGroup([perm"(1,2,3)", perm"(1,2)"]),
action = VariablePermutation(x)

m, stats = sos_problem(poly, G, action)
JuMP.set_optimizer(
m,
scs_optimizer(; max_iters = 20_000, eps = 1e-7, accel = 20),
)

optimize!(m)
(
status = termination_status(m),
objective = objective_value(m),
creation_t = stats["model_creation"],
solve_t = solve_time(m),
)
end
``````

Results

``````------------------------------------------------------------------
SCS v3.2.4 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012
------------------------------------------------------------------
problem:  variables n: 17, constraints m: 27
cones:    z: primal zero / dual free vars: 11
s: psd vars: 16, ssize: 2
settings: eps_abs: 1.0e-07, eps_rel: 1.0e-07, eps_infeas: 1.0e-07
alpha: 1.50, scale: 1.00e-01, adaptive_scale: 1
max_iters: 20000, normalize: 1, rho_x: 1.00e-06
acceleration_lookback: 20, acceleration_interval: 10
lin-sys:  sparse-direct-amd-qdldl
nnz(A): 45, nnz(P): 0
------------------------------------------------------------------
iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)
------------------------------------------------------------------
0| 2.76e+01  1.00e+00  2.82e+01 -1.36e+01  1.00e-01  1.86e-04
200| 1.50e-08  2.67e-09  5.75e-08  1.42e+00  6.09e-01  7.21e-04
------------------------------------------------------------------
status:  solved
timings: total: 7.24e-04s = setup: 1.39e-04s + solve: 5.84e-04s
lin-sys: 6.77e-05s, cones: 4.30e-04s, accel: 7.18e-06s
------------------------------------------------------------------
objective = 1.417411
------------------------------------------------------------------
(status = MathOptInterface.OPTIMAL, objective = -1.4174111165076462, symmetry_adaptation_t = 0.001210972, creation_t = 0.000426226, solve_t = 0.000723593)
``````

EDIT: The results agree also with `poly = sum(x.^4)+sum(x)-4*x[1]*x[2]*x[3]`

1 Like

Can I use this for my problem for now that Benoit has not fixed everything yet? If I can use it would you tell me how? I do not have some of your examples and so the scripts

``````include("examples/action_polynomials.jl")
include("examples/sos_problem.jl")
include("examples/solver.jl")
``````

do not work for me.

Done.

These are located in `SymbolicWedderburn.jl` main directory.

1 Like

I get this error:
WARNING: could not import SymbolicWedderburn.SA into Main
ERROR: MethodError: no method matching action(::VariablePermutation{Vector{PolyVar{true}}}, ::Permutation{Int64, â€¦}, ::Monomial{true})

I also tried to run the example â€śex_S4.jlâ€ť but I got an error. What is the problem? Here is the result of running this example:

``````           SCS v3.2.4 - Splitting Conic Solver
(c) Brendan O'Donoghue, Stanford University, 2012
``````

``````cones:    z: primal zero / dual free vars: 495
s: psd vars: 2485, ssize: 1
settings: eps_abs: 1.0e-007, eps_rel: 1.0e-007, eps_infeas: 1.0e-007
alpha: 1.50, scale: 1.00e-001, adaptive_scale: 1
max_iters: 2000, normalize: 1, rho_x: 1.00e-006
acceleration_lookback: 10, acceleration_interval: 10
compiled with openmp parallelization enabled
lin-sys:  sparse-direct-amd-qdldl
nnz(A): 4971, nnz(P): 0

------------------------------------------------------------------
iter | pri res | dua res |   gap   |   obj   |  scale  | time (s)

------------------------------------------------------------------
0|1.53e+003 1.08e+002 2.15e+006 1.07e+006 1.00e-001 1.83e-002
250|5.92e+001 3.13e-001 4.86e+001 -8.74e+001 5.71e-003 9.57e-001
500|2.44e-001 1.48e-003 4.39e+000 -6.48e+000 5.71e-003 1.90e+000
750|9.02e-011 2.35e-013 3.75e-008 -1.00e+000 5.71e-003 2.89e+000

------------------------------------------------------------------
status:  solved
timings: total: 2.89e+000s = setup: 1.11e-002s + solve: 2.88e+000s
lin-sys: 6.93e-002s, cones: 2.77e+000s, accel: 1.43e-002s

------------------------------------------------------------------
objective = -0.999756

------------------------------------------------------------------
Stacktrace:
[1] wait
[3] macro expansion
[4] invariant_vectors(tbl::SymbolicWedderburn.Characters.CharacterTable{PermGroup{Int64, â€¦}, Cyclotomics.Cyclotomic{Rational{Int64}, SparseVector{Rational{Int64}, Int64}}, PermutationGroups.Orbit1{Permutation{Int64, â€¦}, Nothing}}, act::VariablePermutation{Vector{PolyVar{true}}}, basis::StarAlgebras.Basis{Monomial{true}, UInt32, MonomialVector{true}})
@ SymbolicWedderburn C:\Users\raven\.julia\packages\SymbolicWedderburn\0GTPj\src\wedderburn_decomposition.jl:134
[5] macro expansion
@ f:\darsi\david goluskin\julia\examples\sos_problem.jl:164 [inlined]
[6] macro expansion
@ .\timing.jl:463 [inlined]
[7] sos_problem(poly::Polynomial{true, Int64}, G::PermGroup{Int64, â€¦}, action::VariablePermutation{Vector{PolyVar{true}}}, T::Type; decompose_psd::Bool, semisimple::Bool)
@ Main f:\darsi\david goluskin\julia\examples\sos_problem.jl:157
[8] top-level scope
@ f:\darsi\david goluskin\julia\examples\ex_S4.jl:36

nested task error: MethodError: no method matching action(::VariablePermutation{Vector{PolyVar{true}}}, ::Permutation{Int64, â€¦}, ::Monomial{true})
Closest candidates are:
action(::VariablePermutation, ::AbstractPermutations.AbstractPermutation, ::Monomial) at f:\darsi\david goluskin\julia\examples\action_polynomials.jl:20
action(::SymbolicWedderburn.Action, ::GroupElement, ::AbstractTerm) at f:\darsi\david goluskin\julia\examples\action_polynomials.jl:12
action(::SymbolicWedderburn.Action, ::GroupElement, ::AbstractPolynomial) at f:\darsi\david goluskin\julia\examples\action_polynomials.jl:8
...
Stacktrace:
[1] macro expansion
@ C:\Users\raven\.julia\packages\SymbolicWedderburn\0GTPj\src\wedderburn_decomposition.jl:135 [inlined]

please have a look at how files are included in `./examples/run_examples.jl`

Youâ€™re missing a definition of the action on polynomials by variable transformation and/or your package versions are not correct (you should use the local Project/Manifest).

1 Like

I updated my Julia to the latest version. I downloaded your package in my directory. I opened`./examples/run_examples.jl` and ran it. I got the following error:
`LoadError: UndefVarError: `AP` not defined `

Now, I can run `ex_C2_linear.jl` ,`sos_problem.jl` or `solver.jl` successfully. , but If I run `ex_S4.jl` or `action_polynomials.jl`, I will get the same error.

Why is `AP` an undefined variable for me, how can I resolve it?

I fixed this problem by adding `import AbstractPermutations as AP` at the beginning of `action_polynomials.jl`. However, this should not be a solution. Why `AP` cannot be read automatically from SymbolicWedderburn.jl?

In `action_polynomials.jl`, there is a line of script: `g::AP.AbstractPermutation,`. What would happen if we change it to `g::AP.AbstractPermutations,`?

what version of the package youâ€™re trying to run? most probably git master, try the latest released version; I fix examples only at the end before the release.

1 Like

Now, it works. Thank you. Why is just the objective value negative of the real objective? Here, you can see that in your result:

Just one last question. It seems I cannot implement symmetry reduction properly while using the SumsofSquares package. Using your result, I can do symmetry reduction for SOS optimization problems without the SumsofSquares package. However, I would like to do symmetry reduction in SDSOS or DSOS optimization. I do not know how much you are familiar with these. SDSOS optimization is equivalent to scaled diagonally dominant programming which is a second-order cone programming rather than SDP, and DSOS is a linear programming.
Do you have any suggestions for how I can use your package for invariant SDSOS optimizations or invariant scaled diagonally dominant programming problems?

This is due to internal reformulation of the problem done by JuMP. SCS only solves minimization problems (in particular format), so the model we input is bridged internally to fit that description.

Iâ€™m afraid Wedderburn decomposition will not be of much help for DSOS, as linear programs can be simplified by change of variables only. You should probably

1. compute `symmetry_adapted_basis` (with `semisimple=false`, i.e. the isotypic projections) and create one variable for each vector here.
2. decompose the set of constraints into orbits and create one constraint (the average) per orbit
3. transform the new constraints to the new basis. profit

Iâ€™m not sure about SOC program, Iâ€™d need to think a bit. You should of course try the naive version of simplifying the SDP formulation of the problem

1 Like

In general, symmetry reduction is not helpful for SDSOS nor DSOS, since these cones are basis-dependent. In contrast to SOS cone or SDP cone, symmetry-adapted bases change the scaled diagonally dominant and diagonally dominant cones. So many people use symmetry reduction for SDSOS while not being aware the answer is different from the answer before symmetry reduction. This is exactly my point of research. Iâ€™ve partially characterized the effect of symmetry reduction on these problems. That is why I want to use your package for SDSOS or scaled diagonally dominant optimization problems with different symmetries.