ProxSDP

Build Status

ProxSDP is a semidefinite programming (SDP) solver based on the paper "Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting". ProxSDP solves general SDP problems by means of a first order proximal algorithm based on the primal-dual hybrid gradient, also known as Chambolle-Pock method. The main advantage of ProxSDP over other state-of-the-art solvers is the ability of exploit the low-rank property inherent to several SDP problems.

Overview of problems ProxSDP can solve

Any semidefinite programming problem in standard form;
Semidefinite relaxations of nonconvex problems, e.g. max-cut, binary MIMO, optimal power flow, sensor localization;
Nuclear norm minimization problems, e.g. matrix completion.

Installing

Currently ProxSDP only works with Julia 0.6.x

To add ProxSDP run:

Pkg.add("ProxSDP")

Building problems with JuMP.jl

Currently the easiest ways to pass problems to ProxSDP is through JuMP (v0.19-alpha) or MathOptInterface (v0.6).

The main caveat is that currently ProxSDP must have one and only one PSD variable, no other variables are allowed.

In the test folder one can find MOI implementations of some problems: MIMO, Sensor Localization, Random SDPs and sdplib problems.

JuMP example

ProxSDP uses the new implementation of JuMP, currently in alpha version.

Therefore one needs to checkout in JuMP on the tag v0.19-alpha

For more example on how to use the latest version of JuMP please refer to the manual.

A quick JuMP example:

using ProxSDP, JuMP

# Create a JuMP model using ProxSDP as the solver
model = Model(with_optimizer(ProxSDP.Solver, log_verbose=true))

# Create a Positive Semidefinite variable
# Currently ProxSDP is only able to hold one PSD
# variable and no other variable
@variable(model, X[1:2,1:2], PSD)

# but you can define pieces of the one PSD
# variable to hold other variable as in the
# Canonical SDP format
x = X[1,1]
y = X[2,2]

# There is no limits on linear constraints
# one can define as many as wanted
@constraint(model, ub_x, x <= 2)

@constraint(model, ub_y, y <= 30)

@constraint(model, con, 1x + 5y <= 3)

# ProxSDP supports maximization or minimization
# of linear functions
@objective(model, Max, 5x + 3 * y)

# Then we can solve the model
JuMP.optimize!(model)

# And ask for results!
JuMP.objective_value(model)

JuMP.result_value(x)

JuMP.result_value(y)

Referencing

The first version of the paper can be found here.

@article{souto2018exploiting,
  title={Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting},
  author={Souto, Mario and Garcia, Joaquim D and Veiga, {\'A}lvaro},
  journal={arXiv preprint arXiv:1810.05231},
  year={2018}
}

TODO

Add support for other cones

migarstka/ProxSDP.jl