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
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),
symmetry_adaptation_t = 0.0,
creation_t = model_creation_t,
solve_t = solve_time(m),
)
end
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
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})
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).
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.
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.
To answer the other questions:
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
compute symmetry_adapted_basis (with semisimple=false, i.e. the isotypic projections) and create one variable for each vector here.
decompose the set of constraints into orbits and create one constraint (the average) per orbit
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
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.
