# 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.