Semidefinite Programming

This package provides a Julia interface for low-level modeling of semidefinite programming problems and for solving semidefinite programs with solvers such as SDPA and CSDP.

Maintenance status: This package is no longer maintained.

Introduction

Consider a semidefinite program of the form

max tr(C X) subject to X is positive semidefinite
                       tr(A_i X) = b_i for i = 1, ...,m

Here C, X, and A_1, ..., A_m are symmetric block matrices (all assumed to have identical size and block structure), and b_1, ..., b_m are scalars.

This problem can be modeled by constructing a sparse semidefinite program with

using SemidefiniteProgramming
sdp = SparseSDP(maximize=true)

and then setting the nonzero scalars and the nonzero entries of the matrices. The most basic way to do this is as follows: For the scalars b_i use

setrhs!(sdp, i, value)

For the entries of the objective matrix C use

setobj!(sdp, blockindex, rowindex, columnindex, value)

For the constraint matrices A_i use

setcon!(sdp, i, blockindex, rowindex, columnindex, value)

Then we solve the program with

sol = solve(sdp, solver)

and print the (primal) objective value:

println(obj(sol))

Notice that the number of constraints, the number of blocks, and the blocksizes do not need to be specified; they will be determined automatically based on the entries you have set. Of course all the matrices involded are assumed to have identical block structure. The indices of the contraints, blocks, and matrices do not need be integers; you can use any Julia object here. When storing a SparseSDP in for instance the SDPA-sparse format the indices will be converted to integers automatically.

Example

Consider the program above with b1 = 10, b2 = 20,

C = [1 0 0 0;
     0 2 0 0;
     0 0 3 0;
     0 0 0 4],

A1 = [1 0 0 0;
      0 1 0 0;
      0 0 0 0;
      0 0 0 0],

and

A2 = [0 0 0 0;
      0 1 0 0;
      0 0 5 2;
      0 0 2 6]

To solve this we use

using SemidefiniteProgramming

sdp = SparseSDP(maximize=true)

setobj!(sdp, 1, 1, 1, 1.0)
setobj!(sdp, 2, 1, 1, 2.0)
setobj!(sdp, 3, 1, 1, 3.0)
setobj!(sdp, 3, 2, 2, 4.0)

setrhs!(sdp, 1, 10.0)
setcon!(sdp, 1, 1, 1, 1, 1.0)
setcon!(sdp, 1, 2, 1, 1, 1.0)

setrhs!(sdp, 2, 20.0)
setcon!(sdp, 2, 2, 1, 1, 1.0)
setcon!(sdp, 2, 3, 1, 1, 5.0)
setcon!(sdp, 2, 3, 1, 2, 2.0)
setcon!(sdp, 2, 3, 2, 1, 2.0)
setcon!(sdp, 2, 3, 2, 2, 6.0)

println(obj(solve(sdp, CSDP())))

Solvers

To use a solver construct an immutable solver object with CSDP(), SDPA(), etc, and supply it as the second argument to the solve function. The solver objects support the optional named arguments

verbose (print solver output to stdout)
executable (path to the solver executable)

CSDP

To use the CSDP solver you need to install CSDP and make sure that the CSDP binary is in your path. On Debian/Ubuntu you can do this by installing the coinor-csdp package. On Fedora it is the csdp package.

SDPA

To use one of the SDPA solvers install SDPA and make sure the executable is in your path. On Debian/Ubuntu you can do this by installing the package sdpa (this package only contains the standard SDPA solver). Use SDPA for the standard SDPA solver and SDPAQD or SDPAGMP for the high precision solvers.

SparseSDPSolution objects

Having solved a semidefinite program with

sol = solve(sdp, CSDP())

you can extract the primal and dual objective values with obj(sol) and dualobj(sol). To extract the values of the optimal primal variables (the matrix X in the notation above) use

primalmatrix(sol)[blockindex][rowindex, columnindex]

Variable extraction is currently only supported with the CSDP solver.