Skip to content
master
Go to file
Code

README.md

ProxSDP logo

Build Status
Build Status Codecov branch

ProxSDP is an open-source semidefinite programming (SDP) solver based on the paper "Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting". The main advantage of ProxSDP over other state-of-the-art solvers is the ability to exploit the low-rank structure inherent to several SDP problems.

Overview of problems ProxSDP can solve

Installation

You can install ProxSDP through the Julia package manager:

] add ProxSDP

Using ProxSDP with JuMP

For example, consider the semidefinite programming relaxation of the max-cut problem

    max   0.25 * W•X
    s.t.  diag(X) = 1,
          X ≽ 0,

This problem can be solved by the following code using ProxSDP and JuMP.

# Load packages
using ProxSDP, JuMP, LinearAlgebra

# Number of vertices
n = 4
# Graph weights
W = [18.0  -5.0  -7.0  -6.0
     -5.0   6.0   0.0  -1.0
     -7.0   0.0   8.0  -1.0
     -6.0  -1.0  -1.0   8.0]

# Build Max-Cut SDP relaxation via JuMP
model = Model(with_optimizer(ProxSDP.Optimizer, log_verbose=true, tol_gap=1e-4, tol_feasibility=1e-4))
@variable(model, X[1:n, 1:n], PSD)
@objective(model, Max, 0.25 * dot(W, X))
@constraint(model, diag(X) .== 1)

# Solve optimization problem with ProxSDP
JuMP.optimize!(model)

# Retrieve solution
Xsol = JuMP.value.(X)

Citing this package

The preprint 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}
}

Disclaimer

  • ProxSDP is a research software, therefore it should not be used in production.
  • Please open an issue if you find any problems, developers will try to fix and find alternatives.
  • ProxSDP assumes primal and dual feasibility. Currently, it is not able to reliably identify infeasibility and unboundedness.

ROAD MAP

  • Support for exponential and power cones;
  • Warm start.
You can’t perform that action at this time.