csdp function

Solve semidefinite program with CSDP

Interface to CSDP semidefinite programming library. The general statement of the primal problem is [REMOVE_ME]$\max\, \mathrm{tr}(CX)max tr(CX) [REMOVE_ME_2]$

[REMOVE_ME]$\mathrm{s.t.}\; A(X) = bs.t. A(X) = b [REMOVE_ME_2]$

[REMOVE_ME]$X \succeq 0X >= 0 [REMOVE_ME_2]$

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 [REMOVE_ME]$\min\, b'ymin b'y [REMOVE_ME_2]$

[REMOVE_ME]$\mathrm{s.t.}\; A'(y) - C = Zs.t. A'(y) - C = Z [REMOVE_ME_2]$

[REMOVE_ME]$Z \succeq 0Z >= 0 [REMOVE_ME_2]$

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

Description

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

$$\max\, \mathrm{tr}(CX)max tr(CX)$$ $$\mathrm{s.t.}\; A(X) = bs.t. A(X) = b$$ $$X \succeq 0X >= 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'ymin b'y$$ $$\mathrm{s.t.}\; A'(y) - C = Zs.t. A'(y) - C = Z$$ $$Z \succeq 0Z >= 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).

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.

Returns

• 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

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

Author(s)

Hector Corrada Bravo. CSDP written by Brian Borchers.

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)