COIN-OR SemiDefinite Programming Interface (CSDP.jl)

CSDP.jl is an interface to the COIN-OR SemiDefinite Programming solver. It provides a complete interface to the low-level C API, as well as an implementation of the solver-independent MathProgBase and MathOptInterface API's.

Note: This wrapper is maintained by the JuMP community and is not a COIN-OR project.

Build Status

The original algorithm is described by B. Borchers. CSDP, A C Library for Semidefinite Programming. Optimization Methods and Software 11(1):613-623, 1999. DOI 10.1080/10556789908805765. Preprint.

Installation

The package can be installed with Pkg.add.

julia> import Pkg; Pkg.add("CSDP")

CSDP.jl will use BinaryProvider.jl to automatically install the CSDP binaries. This should work for both the official Julia binaries and source-builds.

Using with JuMP

We highly recommend that you use the CSDP.jl package with higher level packages such as CSDP.jl.

This can be done using the CSDP.Optimizer object. Here is how to create a JuMP model that uses CSDP as the solver.

using JuMP, CSDP

model = Model(CSDP.Optimizer)
set_optimizer_attribute(model, "maxiter", 1000)

CSDP problem representation

The primal is represented internally by CSDP as follows:

max ⟨C, X⟩
      A(X) = a
         X ⪰ 0

where A(X) = [⟨A_1, X⟩, ..., ⟨A_m, X⟩]. The corresponding dual is:

min ⟨a, y⟩
     A'(y) - C = Z
             Z ⪰ 0

where A'(y) = y_1A_1 + ... + y_mA_m

Termination criteria

CSDP will terminate successfully (or partially) in the following cases:

• If CSDP finds y and Z ⪰ 0 such that -⟨a, y⟩ / ||A'(y) - Z||_F > pinftol, it returns 1 with y such that ⟨a, y⟩ = -1.
• If CSDP finds X ⪰ 0 such that ⟨C, X⟩ / ||A(X)||_2 > dinftol, it returns 2 with X such that ⟨C, X⟩ = 1.
• If CSDP finds X, Z ⪰ 0 such that the following 3 tolerances are satisfied:
  • primal feasibility tolerance: ||A(x) - a||_2 / (1 + ||a||_2) < axtol
  • dual feasibility tolerance: ||A'(y) - C - Z||_F / (1 + ||C||_F) < atytol
  • relative duality gap tolerance: gap / (1 + |⟨a, y⟩| + |⟨C, X⟩|) < objtol
    • objective duality gap: If usexygap is 0, gap = ⟨a, y⟩ - ⟨C, X⟩
    • XY duality gap: If usexygap is 1, gap = ⟨Z, X⟩ then it returns 0.
• If CSDP finds X, Z ⪰ 0 such that the following 3 tolerances are satisfied with 1000*axtol, 1000*atytol and 1000*objtol but at least one of them is not satisfied with axtol, atytol and objtol and cannot make progress then it returns 3.

Remark: In theory, for feasible primal and dual solutions, ⟨a, y⟩ - ⟨C, X⟩ = ⟨Z, X⟩ so the objective and XY duality gap should be equivalent. However, in practice, there are sometimes solution which satisfy primal and dual feasibility tolerances but have objective duality gap which are not close to XY duality gap. In some cases, the objective duality gap may even become negative (hence the tweakgap option). This is the reason usexygap is 1 by default.

Remark: CSDP considers that X ⪰ 0 (resp. Z ⪰ 0) is satisfied when the Cholesky factorizations can be computed. In practice, this is somewhat more conservative than simply requiring all eigenvalues to be nonnegative.

Status

The table below shows how the different CSDP status are converted to MathOptInterface (MOI) status.

If the printlevel option is at least 1, the following will be printed:

• If the return code is 1, CSDP will print ⟨a, y⟩ and ||A'(y) - Z||_F
• if the return code is 2, CSDP will print ⟨C, X⟩ and ||A(X)||_F
• otherwise, CSDP will print
  • the primal/dual objective value,
  • the relative primal/dual infeasibility,
  • the objective duality gap ⟨a, y⟩ - ⟨C, X⟩ and objective relative duality gap (⟨a, y⟩ - ⟨C, X⟩) / (1 + |⟨a, y⟩| + |⟨C, X⟩|),
  • the XY duality gap ⟨Z, X⟩ and XY relative duality gap ⟨Z, X⟩ / (1 + |⟨a, y⟩| + |⟨C, X⟩|)
  • and the DIMACS error measures.

Options

The CSDP options are listed in the table below. Their value can be specified in the constructor of the CSDP solver, e.g. CSDPSolver(axtol=1e-7, printlevel=0).