SumOfSquaresOptimization

A Julia library to solve sum-of-squares relaxations of polynomial systems. Developtment has now ceased, in favor of the collaboration SumOfSquares.jl; see also PolyJuMP.jl.

This software is open-source, hosted in this github repository.

example

The following solves the degree 4 SoS relaxation for vertex cover on the complete graph on five vertices:

using SumOfSquaresOptimization

prog = Program(minimize=true)

for i in 1:5
    for j in 1:5
        if j > i
            @constraint(prog, "x%d + x%d >= 1", i,j) # coverage constraint
        end
    end
    @constraint(prog, "x%d^2 - x%d = 1", i,i) # hypercube constraint
    @partobjective(prog, "x%d", i) # objective: min sum x_i
end

sol = sossolve(prog,4) # 4 indicates degree
dumpsol(sol)

functions

The following four macros specify constraints and objectives in printf style:

  • @constraint(prog, fmt, ...) adds a polynomial constraint
  • @objective(prog, fmt, ...) sets a polynomial objective
  • @partconstraint(sos, key, fmt, ...) adds a polynomial to the constraint labeled by key
  • @partobjective(sos, fmt, ...) adds a polynomial to the current objective

There are also function analogues for plain strings: constraint, objective, partconstraint, and partobjective.

The following will solve a polynomial system and access a solution:

  • sossolve(sos, deg) solves the program, returning a solution object. You can optionally specify solver="csdp" or solver="sdpa", with csdp being the default. One of these two must be installed.
  • dumpsol(sol) outputs the objective, moments, and dual matrix to stdout. These will be more readable in the future.
  • @moment(sol, fmt, ...) outputs the pseudo-expectation of the given polynomial, specified in printf style.
  • primalobj(sol) and dualobj(sol) return the objective values (which are hopefully equal).
  • status(sol) returns the solution status: :Normal, :Infeasible, :Unbounded, :Warning, or :Error.

The following functions provide symmetry hints, enabling faster solution and ensuring symmetric moments:

  • symmetrize!(prog, perms), where perms is an array of Dict{Symbol,Symbol} objects encoding generating permutations.
  • symmetrize_dihedral!(prog, cycle), where cycle is an array of Symbols. This imposes symmetry under the action of the dihedral group.
  • symmetrize_cyclic!(prog, cycle), much as the previous but for the cyclic group – so no reflection symmetry of the given cycle is imposed.
  • symmetrize_full!(prog, symbols), for full permutation symmetry of the given Array{Symbol}.

troubleshooting

There are probably still a lot of issues with this code. One issue I’ve encountered is that csdp doesn’t seem to accept more than 23169 constraints in some compiled 32-bit versions. I’ve worked on reducing the number of constraints, so I expect this isn’t too much of a barrier anymore. Hinting any symmetries of your program will reduce the number of SDP constraints handed to the solver.