csdp: Solve semidefinite program with CSDP
In Rcsdp: R interface to the CSDP semidefinite programming library
Description
Usage
Arguments
Details
Value
Author(s)
References
Examples
Description
Interface to CSDP semidefinite programming library. The general statement of the primal problem is
max tr(CX)
s.t. A(X) = b
X >= 0
with
A(X)_i = tr(A_iX)
where X >= 0 means X is positive
semidefinite, C and all A_i are symmetric matrices of the same
size and b is a
vector of length m.
The dual of the problem is
min b'y
s.t. A'(y) - C = Z
Z >= 0
where
A'(y) = ∑_{i=1}^m y_i A_i.
Matrices C and A_i are assumed to be block diagonal
structured, and must be specified that way (see Details).
Usage
1
Arguments
C
A list defining the block diagonal cost matrix C.
A
A list of length m containing block diagonal constraint matrices
A_i. Each constraint matrix A_i is specified by a list
of blocks as explained in the Details section.
b
A numeric vector of length m containg the right hand side of the constraints.
K
Describes the domain of each block of the sdp problem. It is a list with the following elements:
- type:
A character vector with entries "s" or
"l" indicating the type of each block. If the jth entry
is "s", then the jth block is a positive semidefinite matrix.
otherwise, it is a vector with non-negative entries.
- size:
A vector of integers indicating the dimension of each
block.
control
Control parameters passed to csdp. See CSDP documentation.
Details
All problem matrices are assumed to be of block diagonal structure,
and must be specified as follows:
If there are nblocks blocks specified by K, then
the matrix must be a list with nblocks components.
If K$type == "s" then the jth element of the list must define a symmetric
matrix of size K$size. It can be an object of class
"matrix", "simple_triplet_sym_matrix", or a valid
class from the class hierarchy in the "Matrix" package.
If K$type == "l" then the jth element of the list
must be a numeric vector of length K$size.
This function checks that the blocks in arguments C and A agree with
the sizes given in argument K. It also checks that the
lengths of arguments b and A
are equal. It does not check for symmetry in the problem data.
Value
X
Optimal primal solution X. A list containing blocks in the
same structure as explained above. Each element is of class
"matrix" or a numeric vector as appropriate.
Z
Optimal dual solution Z. A list containing blocks in the same
structure as explained above. Each element is of class
"matrix"
or a numeric vector as appropriate.
y
Optimal dual solution y. A vector of the same length as
argument b
pobj
Optimal primal objective value
dobj
Optimal dual objective value
status
Status of returned solution.
- 0:
Success. Problem solved to full accuracy
- 1:
Success. Problem is primal infeasible
- 2:
Success. Problem is dual infeasible
- 3:
Partial Success. Solution found but full accuracy was
not achieved
- 4:
Failure. Maximum number of iterations reached
- 5:
Failure. Stuck at edge of primal feasibility
- 6:
Failure. Stuch at edge of dual infeasibility
- 7:
Failure. Lack of progress
- 8:
Failure. X or Z (or Newton system O) is singular
- 9:
Failure. Detected NaN or Inf values
Author(s)
Hector Corrada Bravo. CSDP written by Brian Borchers.
References
-
Borchers, B.:
CSDP, A C Library for Semidefinite Programming Optimization Methods and Software 11(1):613-623, 1999
http://euler.nmt.edu/~brian/csdppaper.pdf
Lu, F., Lin, Y., and Wahba, G.:
Robust Manifold Unfolding with Kernel Regularization TR
1108, October, 2005.
http://www.stat.wisc.edu/~wahba/ftp1/tr1108rr.pdf
Examples
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
C <- list(matrix(c(2,1,
1,2),2,2,byrow=TRUE),
matrix(c(3,0,1,
0,2,0,
1,0,3),3,3,byrow=TRUE),
c(0,0))
A <- list(list(matrix(c(3,1,
1,3),2,2,byrow=TRUE),
matrix(0,3,3),
c(1,0)),
list(matrix(0,2,2),
matrix(c(3,0,1,
0,4,0,
1,0,5),3,3,byrow=TRUE),
c(0,1)))
b <- c(1,2)
K <- list(type=c("s","s","l"),size=c(2,3,2))
csdp(C,A,b,K)
# Manifold Unrolling broken stick example
# using simple triplet symmetric matrices
X <- matrix(c(-1,-1,
0,0,
1,-1),nc=2,byrow=TRUE);
d <- as.vector(dist(X)^2);
d <- d[-2]
C <- list(.simple_triplet_diag_sym_matrix(1,3))
A <- list(list(simple_triplet_sym_matrix(i=c(1,2,2),j=c(1,1,2),v=c(1,-1,1),n=3)),
list(simple_triplet_sym_matrix(i=c(2,3,3),j=c(2,2,3),v=c(1,-1,1),n=3)),
list(matrix(1,3,3)))
K <- list(type="s",size=3)
csdp(C,A,c(d,0),K)
Example output
Iter: 0 Ap: 0.00e+00 Pobj: 3.0434379e+02 Ad: 0.00e+00 Dobj: 0.0000000e+00
Iter: 1 Ap: 8.36e-01 Pobj: 3.6123735e+01 Ad: 1.00e+00 Dobj: 3.6192774e+01
Iter: 2 Ap: 9.91e-01 Pobj: 1.7890107e+00 Ad: 1.00e+00 Dobj: 3.4979250e+01
Iter: 3 Ap: 1.00e+00 Pobj: 1.5056174e+00 Ad: 1.00e+00 Dobj: 8.0480383e+00
Iter: 4 Ap: 1.00e+00 Pobj: 1.8308676e+00 Ad: 1.00e+00 Dobj: 3.3375932e+00
Iter: 5 Ap: 9.97e-01 Pobj: 2.6201334e+00 Ad: 1.00e+00 Dobj: 3.0665242e+00
Iter: 6 Ap: 1.00e+00 Pobj: 2.7034721e+00 Ad: 1.00e+00 Dobj: 2.7846974e+00
Iter: 7 Ap: 1.00e+00 Pobj: 2.7475837e+00 Ad: 1.00e+00 Dobj: 2.7511007e+00
Iter: 8 Ap: 1.00e+00 Pobj: 2.7499233e+00 Ad: 9.98e-01 Dobj: 2.7500315e+00
Iter: 9 Ap: 1.00e+00 Pobj: 2.7499976e+00 Ad: 9.98e-01 Dobj: 2.7499990e+00
Iter: 10 Ap: 1.00e+00 Pobj: 2.7499999e+00 Ad: 9.99e-01 Dobj: 2.7500000e+00
Iter: 11 Ap: 9.70e-01 Pobj: 2.7500000e+00 Ad: 9.70e-01 Dobj: 2.7500000e+00
Success: SDP solved
Primal objective value: 2.7500000e+00
Dual objective value: 2.7500000e+00
Relative primal infeasibility: 5.49e-16
Relative dual infeasibility: 7.62e-10
Real Relative Gap: 2.02e-10
XZ Relative Gap: 4.80e-10
DIMACS error measures: 5.92e-16 0.00e+00 2.24e-09 0.00e+00 2.02e-10 4.80e-10
$X
$X[[1]]
[,1] [,2]
[1,] 0.125 0.125
[2,] 0.125 0.125
$X[[2]]
[,1] [,2] [,3]
[1,] 6.666670e-01 0.00000e+00 -4.518324e-07
[2,] 0.000000e+00 2.20063e-10 0.000000e+00
[3,] -4.518324e-07 0.00000e+00 2.200636e-10
$X[[3]]
[1] 5.868345e-10 4.401261e-10
$Z
$Z[[1]]
[,1] [,2]
[1,] 0.25 -0.25
[2,] -0.25 0.25
$Z[[2]]
[,1] [,2] [,3]
[1,] 6.895277e-10 0 -4.263657e-10
[2,] 0.000000e+00 2 0.000000e+00
[3,] -4.263657e-10 0 2.000000e+00
$Z[[3]]
[1] 0.75 1.00
$y
[1] 0.75 1.00
$pobj
[1] 2.75
$dobj
[1] 2.75
$status
[1] 0
Iter: 0 Ap: 0.00e+00 Pobj: 9.0000000e+01 Ad: 0.00e+00 Dobj: 0.0000000e+00
Iter: 1 Ap: 9.00e-01 Pobj: 1.7028241e+01 Ad: 1.00e+00 Dobj: 4.1063426e+01
Iter: 2 Ap: 9.00e-01 Pobj: 4.5709021e+00 Ad: 1.00e+00 Dobj: 2.8971765e+01
Iter: 3 Ap: 1.00e+00 Pobj: 3.3068682e+00 Ad: 1.00e+00 Dobj: 7.5887982e+00
Iter: 4 Ap: 6.56e-01 Pobj: 3.5852957e+00 Ad: 9.00e-01 Dobj: 4.1169886e+00
Iter: 5 Ap: 8.10e-01 Pobj: 3.9231476e+00 Ad: 1.00e+00 Dobj: 4.0023928e+00
Iter: 6 Ap: 9.00e-01 Pobj: 3.9923166e+00 Ad: 1.00e+00 Dobj: 3.9999980e+00
Iter: 7 Ap: 9.00e-01 Pobj: 3.9992317e+00 Ad: 1.00e+00 Dobj: 3.9999960e+00
Iter: 8 Ap: 1.44e-02 Pobj: 3.9992424e+00 Ad: 1.00e+00 Dobj: 4.0000216e+00
Iter: 9 Ap: 1.00e+00 Pobj: 3.9999991e+00 Ad: 1.00e+00 Dobj: 3.9999977e+00
Iter: 10 Ap: 1.00e+00 Pobj: 3.9999999e+00 Ad: 1.00e+00 Dobj: 4.0000000e+00
Iter: 11 Ap: 1.00e+00 Pobj: 4.0000000e+00 Ad: 9.00e-01 Dobj: 4.0000000e+00
Success: SDP solved
Primal objective value: 4.0000000e+00
Dual objective value: 4.0000000e+00
Relative primal infeasibility: 6.19e-16
Relative dual infeasibility: 7.57e-10
Real Relative Gap: 1.08e-10
XZ Relative Gap: 6.39e-10
DIMACS error measures: 7.90e-16 0.00e+00 1.03e-09 0.00e+00 1.08e-10 6.39e-10
$X
$X[[1]]
[,1] [,2] [,3]
[1,] 2.000000e+00 1.776316e-11 -2.000000e+00
[2,] 1.776316e-11 2.005202e-16 -1.776336e-11
[3,] -2.000000e+00 -1.776336e-11 2.000000e+00
$Z
$Z[[1]]
[,1] [,2] [,3]
[1,] 36.63246 35.63246 36.63246
[2,] 35.63246 37.63246 35.63246
[3,] 36.63246 35.63246 36.63246
$y
[1] 1.00000 1.00000 36.63246
$pobj
[1] 4
$dobj
[1] 4
$status
[1] 0
Rcsdp documentation built on May 2, 2019, 6:08 p.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Description Usage Arguments Details Value Author(s) References Examples
Description
Interface to CSDP semidefinite programming library. The general statement of the primal problem is
max tr(CX)
s.t. A(X) = b
X >= 0
with A(X)_i = tr(A_iX) where X >= 0 means X is positive semidefinite, C and all A_i are symmetric matrices of the same size and b is a vector of length m.
The dual of the problem is
min b'y
s.t. A'(y) - C = Z
Z >= 0
where A'(y) = ∑_{i=1}^m y_i A_i.
Matrices C and A_i are assumed to be block diagonal structured, and must be specified that way (see Details).
Usage
1 |
Arguments
C |
A list defining the block diagonal cost matrix C. |
A |
A list of length m containing block diagonal constraint matrices A_i. Each constraint matrix A_i is specified by a list of blocks as explained in the Details section. |
b |
A numeric vector of length m containg the right hand side of the constraints. |
K |
Describes the domain of each block of the sdp problem. It is a list with the following elements:
|
control |
Control parameters passed to csdp. See CSDP documentation. |
Details
All problem matrices are assumed to be of block diagonal structure, and must be specified as follows:
If there are
nblocksblocks specified byK, then the matrix must be a list withnblockscomponents.If
K$type == "s"then thejth element of the list must define a symmetric matrix of sizeK$size. It can be an object of class"matrix","simple_triplet_sym_matrix", or a valid class from the class hierarchy in the"Matrix"package.If
K$type == "l"then thejth element of the list must be a numeric vector of lengthK$size.
This function checks that the blocks in arguments C and A agree with
the sizes given in argument K. It also checks that the
lengths of arguments b and A
are equal. It does not check for symmetry in the problem data.
Value
X |
Optimal primal solution X. A list containing blocks in the
same structure as explained above. Each element is of class
|
Z |
Optimal dual solution Z. A list containing blocks in the same
structure as explained above. Each element is of class
|
y |
Optimal dual solution y. A vector of the same length as
argument |
pobj |
Optimal primal objective value |
dobj |
Optimal dual objective value |
status |
Status of returned solution.
|
Author(s)
Hector Corrada Bravo. CSDP written by Brian Borchers.
References
Borchers, B.:
CSDP, A C Library for Semidefinite Programming Optimization Methods and Software 11(1):613-623, 1999
http://euler.nmt.edu/~brian/csdppaper.pdfLu, F., Lin, Y., and Wahba, G.:
Robust Manifold Unfolding with Kernel Regularization TR 1108, October, 2005.
http://www.stat.wisc.edu/~wahba/ftp1/tr1108rr.pdf
Examples
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | C <- list(matrix(c(2,1,
1,2),2,2,byrow=TRUE),
matrix(c(3,0,1,
0,2,0,
1,0,3),3,3,byrow=TRUE),
c(0,0))
A <- list(list(matrix(c(3,1,
1,3),2,2,byrow=TRUE),
matrix(0,3,3),
c(1,0)),
list(matrix(0,2,2),
matrix(c(3,0,1,
0,4,0,
1,0,5),3,3,byrow=TRUE),
c(0,1)))
b <- c(1,2)
K <- list(type=c("s","s","l"),size=c(2,3,2))
csdp(C,A,b,K)
# Manifold Unrolling broken stick example
# using simple triplet symmetric matrices
X <- matrix(c(-1,-1,
0,0,
1,-1),nc=2,byrow=TRUE);
d <- as.vector(dist(X)^2);
d <- d[-2]
C <- list(.simple_triplet_diag_sym_matrix(1,3))
A <- list(list(simple_triplet_sym_matrix(i=c(1,2,2),j=c(1,1,2),v=c(1,-1,1),n=3)),
list(simple_triplet_sym_matrix(i=c(2,3,3),j=c(2,2,3),v=c(1,-1,1),n=3)),
list(matrix(1,3,3)))
K <- list(type="s",size=3)
csdp(C,A,c(d,0),K)
|
Example output
Iter: 0 Ap: 0.00e+00 Pobj: 3.0434379e+02 Ad: 0.00e+00 Dobj: 0.0000000e+00
Iter: 1 Ap: 8.36e-01 Pobj: 3.6123735e+01 Ad: 1.00e+00 Dobj: 3.6192774e+01
Iter: 2 Ap: 9.91e-01 Pobj: 1.7890107e+00 Ad: 1.00e+00 Dobj: 3.4979250e+01
Iter: 3 Ap: 1.00e+00 Pobj: 1.5056174e+00 Ad: 1.00e+00 Dobj: 8.0480383e+00
Iter: 4 Ap: 1.00e+00 Pobj: 1.8308676e+00 Ad: 1.00e+00 Dobj: 3.3375932e+00
Iter: 5 Ap: 9.97e-01 Pobj: 2.6201334e+00 Ad: 1.00e+00 Dobj: 3.0665242e+00
Iter: 6 Ap: 1.00e+00 Pobj: 2.7034721e+00 Ad: 1.00e+00 Dobj: 2.7846974e+00
Iter: 7 Ap: 1.00e+00 Pobj: 2.7475837e+00 Ad: 1.00e+00 Dobj: 2.7511007e+00
Iter: 8 Ap: 1.00e+00 Pobj: 2.7499233e+00 Ad: 9.98e-01 Dobj: 2.7500315e+00
Iter: 9 Ap: 1.00e+00 Pobj: 2.7499976e+00 Ad: 9.98e-01 Dobj: 2.7499990e+00
Iter: 10 Ap: 1.00e+00 Pobj: 2.7499999e+00 Ad: 9.99e-01 Dobj: 2.7500000e+00
Iter: 11 Ap: 9.70e-01 Pobj: 2.7500000e+00 Ad: 9.70e-01 Dobj: 2.7500000e+00
Success: SDP solved
Primal objective value: 2.7500000e+00
Dual objective value: 2.7500000e+00
Relative primal infeasibility: 5.49e-16
Relative dual infeasibility: 7.62e-10
Real Relative Gap: 2.02e-10
XZ Relative Gap: 4.80e-10
DIMACS error measures: 5.92e-16 0.00e+00 2.24e-09 0.00e+00 2.02e-10 4.80e-10
$X
$X[[1]]
[,1] [,2]
[1,] 0.125 0.125
[2,] 0.125 0.125
$X[[2]]
[,1] [,2] [,3]
[1,] 6.666670e-01 0.00000e+00 -4.518324e-07
[2,] 0.000000e+00 2.20063e-10 0.000000e+00
[3,] -4.518324e-07 0.00000e+00 2.200636e-10
$X[[3]]
[1] 5.868345e-10 4.401261e-10
$Z
$Z[[1]]
[,1] [,2]
[1,] 0.25 -0.25
[2,] -0.25 0.25
$Z[[2]]
[,1] [,2] [,3]
[1,] 6.895277e-10 0 -4.263657e-10
[2,] 0.000000e+00 2 0.000000e+00
[3,] -4.263657e-10 0 2.000000e+00
$Z[[3]]
[1] 0.75 1.00
$y
[1] 0.75 1.00
$pobj
[1] 2.75
$dobj
[1] 2.75
$status
[1] 0
Iter: 0 Ap: 0.00e+00 Pobj: 9.0000000e+01 Ad: 0.00e+00 Dobj: 0.0000000e+00
Iter: 1 Ap: 9.00e-01 Pobj: 1.7028241e+01 Ad: 1.00e+00 Dobj: 4.1063426e+01
Iter: 2 Ap: 9.00e-01 Pobj: 4.5709021e+00 Ad: 1.00e+00 Dobj: 2.8971765e+01
Iter: 3 Ap: 1.00e+00 Pobj: 3.3068682e+00 Ad: 1.00e+00 Dobj: 7.5887982e+00
Iter: 4 Ap: 6.56e-01 Pobj: 3.5852957e+00 Ad: 9.00e-01 Dobj: 4.1169886e+00
Iter: 5 Ap: 8.10e-01 Pobj: 3.9231476e+00 Ad: 1.00e+00 Dobj: 4.0023928e+00
Iter: 6 Ap: 9.00e-01 Pobj: 3.9923166e+00 Ad: 1.00e+00 Dobj: 3.9999980e+00
Iter: 7 Ap: 9.00e-01 Pobj: 3.9992317e+00 Ad: 1.00e+00 Dobj: 3.9999960e+00
Iter: 8 Ap: 1.44e-02 Pobj: 3.9992424e+00 Ad: 1.00e+00 Dobj: 4.0000216e+00
Iter: 9 Ap: 1.00e+00 Pobj: 3.9999991e+00 Ad: 1.00e+00 Dobj: 3.9999977e+00
Iter: 10 Ap: 1.00e+00 Pobj: 3.9999999e+00 Ad: 1.00e+00 Dobj: 4.0000000e+00
Iter: 11 Ap: 1.00e+00 Pobj: 4.0000000e+00 Ad: 9.00e-01 Dobj: 4.0000000e+00
Success: SDP solved
Primal objective value: 4.0000000e+00
Dual objective value: 4.0000000e+00
Relative primal infeasibility: 6.19e-16
Relative dual infeasibility: 7.57e-10
Real Relative Gap: 1.08e-10
XZ Relative Gap: 6.39e-10
DIMACS error measures: 7.90e-16 0.00e+00 1.03e-09 0.00e+00 1.08e-10 6.39e-10
$X
$X[[1]]
[,1] [,2] [,3]
[1,] 2.000000e+00 1.776316e-11 -2.000000e+00
[2,] 1.776316e-11 2.005202e-16 -1.776336e-11
[3,] -2.000000e+00 -1.776336e-11 2.000000e+00
$Z
$Z[[1]]
[,1] [,2] [,3]
[1,] 36.63246 35.63246 36.63246
[2,] 35.63246 37.63246 35.63246
[3,] 36.63246 35.63246 36.63246
$y
[1] 1.00000 1.00000 36.63246
$pobj
[1] 4
$dobj
[1] 4
$status
[1] 0
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.