csdp {Rcsdp}

Solve semidefinite program with CSDP

Description

Interface to CSDP semidefinite programming library. The general statement of the primal problem is

\max\, \mathrm{tr}(CX)

\mathrm{s.t.}\; A(X) = b

X \succeq 0

with A(X)_i = \mathrm{tr}(A_iX) where X \succeq 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

\mathrm{s.t.}\; A'(y) - C = Z

Z \succeq 0

where A'(y) = \sum_{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

csdp(C, A, b, K,control=csdp.control())

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 containing 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:

1. If there are nblocks blocks specified by K, then the matrix must be a list with nblocks components.

2. 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.

3. 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.

csdp_minimal is a minimal wrapper to the C code underlying csdp. It assumes that the arguments sum.block.sizes, nconstraints, nblocks, block.types, and block.sizes are provided as if they were created by Rcsdp:::prob.info and that the arguments C, A, and b are provided as if they were created by Rcsdp:::prepare.data. This function may be useful when calling the csdp functionality iteratively and most of the optimization details stays the same. For example, when the control file created by Rcsdp:::write.control.file stays the same across iterations, but it would be recreated on each iteration by csdp.

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

• https://github.com/coin-or/Csdp/

• 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://pages.stat.wisc.edu/~wahba/ftp1/tr1108rr.pdf

Examples

  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)