Symmetry reduction in Sumsofsquares

Specific Domains Optimization (Mathematical)
, , ,
7

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

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),
            symmetry_adaptation_t = stats["symmetry_adaptation"],
            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