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

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

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)

Simple support for sparse matrices

Description

Support for sparse matrices in package Rcsdp. The class simple_triplet_sym_matrix is defined to provide support for symmetric sparse matrices. It's definition is copied from the package relations by Kurt Hornik. Coercion functions from objects of class matrix and classes in the Matrix hierarchy are provided.

Usage

   simple_triplet_sym_matrix(i,j,v,n=max(c(i,j)),check.ind=FALSE)
   ## S3 method for class 'matrix'
as.simple_triplet_sym_matrix(x,check.sym=FALSE,...)
   ## S3 method for class 'simple_triplet_sym_matrix'
as.matrix(x,...)
   ## S3 method for class 'simple_triplet_sym_matrix'
as.vector(x,...)
   .simple_triplet_zero_sym_matrix(n,mode="double")
   .simple_triplet_diag_sym_matrix(x,n)
   .simple_triplet_random_sym_matrix(n,occ=.1,nnz=occ*n*(n+1)/2,rfun=rnorm,seed=NULL,...)

Arguments

Details

TO DO

Value

TO DO

Author(s)

Hector Corrada Bravo

References

TO DO

See Also

csdp

Examples

#  TO DO

Pass control parameters to csdp solver.

Description

Utility function to pass control parameters to csdp solver.

Usage

csdp.control(axtol = 1e-08, 
  atytol = 1e-08, 
  objtol = 1e-08, 
  pinftol = 1e+08, 
  dinftol = 1e+08, 
  maxiter = 100, 
  minstepfrac = 0.9, 
  maxstepfrac = 0.97, 
  minstepp = 1e-08, 
  minstepd = 1e-08, 
  usexzgap = 1, 
  tweakgap = 0, 
  affine = 0, 
  printlevel = 1, 
  perturbobj = 1, 
  fastmode = 0)

Arguments

Details

Parameters are fully described in CSDP user guide. https://github.com/coin-or/Csdp/

Value

A list with values for all parameters. Any parameters not passed to function are set to default.

Author(s)

Hector Corrada Bravo, CSDP by Brian Borchers

References

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

Examples

params <- csdp.control(axtol=1e-6)

Reading and writing semidefinite programs for SDPA format files.

Description

Functions to read and write semidefinite program data and solutions in SDPA format.

Usage

   readsdpa(file="",verbose=FALSE)
   writesdpa(C,A,b,K,file="")
   readsdpa.sol(K,C,m,file="")
   writesdpa.sol(X,Z,y,K,file="")

Arguments

Details

Block structured matrices must be specified as described in csdp. Files read must be in SDPA format (see http://euler.nmt.edu/~brian/sdplib/FORMAT). However, these functions don't support comments or grouping characters (e.g. braces, parentheses) in the block sizes specification.

Value

Function readsdpa returns a list with elements C,A,b,K. Function readsdpa.sol returns a list with elements X,Z,y. All returned matrices are lists of objects of class simple_triplet_sym_matrix.

Author(s)

Hector Corrada Bravo

References

http://euler.nmt.edu/~brian/sdplib/FORMAT

See Also

csdp

Examples

#  TO DO