Name: CSDP.jl
Owner: JuliaOpt
Description: Julia Wrapper for CSDP (https://projects.coin-or.org/Csdp/)
Created: 2016-03-25 19:01:16.0
Updated: 2018-04-27 13:09:17.0
Pushed: 2018-04-27 13:09:15.0
Size: 209
Language: Julia
GitHub Committers
User | Most Recent Commit | # Commits |
---|
Other Committers
User | Most Recent Commit | # Commits |
---|
| PackageEvaluator | Build Status | |:——————–:|:—————-:| | | | | | |
Julia wrapper to CSDP semidefinite programming solver.
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.
First, make sure that you have a compiler available and that LAPACK and BLAS are installed. On Ubuntu, simply do
do apt-get install build-essential liblapack-dev libopenblas-dev
Then, install CSDP using
a> Pkg.add("CSDP")
To use CSDP with JuMP, do
g JuMP
Model(solver=CSDPSolver())
The primal is represented internally by CSDP as follows:
?C, X?
A(X) = a
X ? 0
where A(X) = [?A_1, X?, ..., ?A_m, X?]
.
The corresponding dual is:
?a, y?
A'(y) - C = Z
Z ? 0
where A'(y) = y_1A_1 + ... + y_mA_m
CSDP will terminate successfully (or partially) in the following cases:
y
and Z ? 0
such that -?a, y? / ||A'(y) - Z||_F > pinftol
, it returns 1
with y
such that ?a, y? = -1
.X ? 0
such that ?C, X? / ||A(X)||_2 > dinftol
, it returns 2
with X
such that ?C, X? = 1
.X, Z ? 0
such that the following 3 tolerances are satisfied:||A(x) - a||_2 / (1 + ||a||_2) < axtol
||A'(y) - C - Z||_F / (1 + ||C||_F) < atytol
gap / (1 + |?a, y?| + |?C, X?|) < objtol
usexygap
is 0
, gap = ?a, y? - ?C, X?
usexygap
is 1
, gap = ?Z, X?
then it returns 0
.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.
The table below shows how the different CSDP status are converted to MathProgBase status.
CSDP code | State | Description | MathProgBase status |
——— | ————— | ————————————————————- | ——————- |
0
| Success | SDP solved | Optimal |
1
| Success | The problem is primal infeasible, and we have a certificate | Infeasible |
2
| Success | The problem is dual infeasible, and we have a certificate | Unbounded |
3
| Partial Success | A solution has been found, but full accuracy was not achieved | Suboptimal |
4
| Failure | Maximum iterations reached | UserLimit |
5
| Failure | Stuck at edge of primal feasibility | Error |
6
| Failure | Stuck at edge of dual infeasibility | Error |
7
| Failure | Lack of progress | Error |
8
| Failure | X
, Z
, or O
was singular | Error |
9
| Failure | Detected NaN
or Inf
values | Error |
If the printlevel
option is at least 1
, the following will be printed:
1
, CSDP will print ?a, y?
and ||A'(y) - Z||_F
2
, CSDP will print ?C, X?
and ||A(X)||_F
?a, y? - ?C, X?
and objective relative duality gap (?a, y? - ?C, X?) / (1 + |?a, y?| + |?C, X?|)
,?Z, X?
and XY relative duality gap ?Z, X? / (1 + |?a, y?| + |?C, X?|)
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)
.
Name | | Default Value |
———— | ———————————– | ————– |
axtol
| Tolerance for primal feasibility | 1.0e-8
|
atytol
| Tolerance for dual feasibility | 1.0e-8
|
objtol
| Tolerance for relative duality gap | 1.0e-8
|
pinftol
| Tolerance for determining primal infeasibility | 1.0e8
|
dinftol
| Tolerance for determining dual infeasibility | 1.0e8
|
maxiter
| Limit for the total number of iterations | 100
|
minstepfrac
| The minstepfrac
and maxstepfrac
parameters determine how close to the edge of the feasible region CSDP will step | 0.90
|
maxstepfrac
| The minstepfrac
and maxstepfrac
parameters determine how close to the edge of the feasible region CSDP will step | 0.97
|
minstepp
| If the primal step is shorter than minstepp then CSDP declares a line search failure | 1.0e-8
|
minstepd
| If the primal step is shorter than minstepp then CSDP declares a line search failure | 1.0e-8
|
usexzgap
| If usexzgap
is 0
then CSDP will use the objective duality gap d - p
instead of the XY duality gap ?Z, X?
| 1
|
tweakgap
| If tweakgap
is set to 1
, and usexzgap
is set to 0
, then CSDP will attempt to “fix” negative duality gaps | 0
|
affine
| If affine
is set to 1
, then CSDP will take only primal-dual affine steps and not make use of the barrier term. This can be useful for some problems that do not have feasible solutions that are strictly in the interior of the cone of semidefinite matrices | 0
|
perturbobj
| The perturbobj
parameter determines whether the objective function will be perturbed to help deal with problems that have unbounded optimal solution sets. If perturbobj
is 0
, then the objective will not be perturbed. If perturbobj
is 1
, then the objective function will be perturbed by a default amount. Larger values of perturbobj
(e.g. 100
) increase the size of the perturbation. This can be helpful in solving some difficult problems. | 1
|
fastmode
| The fastmode
parameter determines whether or not CSDP will skip certain time consuming operations that slightly improve the accuracy of the solutions. If fastmode
is set to 1
, then CSDP may be somewhat faster, but also somewhat less accurate | 0
|
printlevel
| The printlevel
parameter determines how much debugging information is output. Use a printlevel
of 0
for no output and a printlevel
of 1
for normal output. Higher values of printlevel will generate more debugging output | 1
|
The original make-file build system only provides a static library.
The quite old (September 2010) pycsdp
interface by Benjamin Kern circumvents the problem by writing some C++ code to which the static library is linked.
The Sage module by @mghasemi is a Cython interface; I don't know how the libcsdp is installed or whether they assume that it is already available on the system.
That is why this package tries to parse the makefile and compiles it itself on Unix systems (so gcc
is needed).
For Windows, a pre-compiled DLL is downloaded (unless you configure the build.jl
differently).
libcsdp
to use 64bit Lapack, aka replace ?some int
s? by long int
(the variables used in a Lapack call). Started in brach julias_openblas64
libcsdp
.sparsematrixblock
.libcsdp.dll
for Windows via Appveyor deployment as described at
JuliaCon.
Currently we use a separate repository.