Semidefinite Cone

To specify an application with a cone of semidefinite constraints, the subroutine

DSDPCreateSDPCone(DSDP dsdp,int nblocks,SDPCone *newsdpcone)

can be used to create a new object that describes a semidefinite cone with $1$ or more blocks. The first argument is an existing semidefinite solver, the second argument is the number of blocks in this cone, and the final argument is an address of a SDPCone variable. This subroutine will allocate structures needed to specify the constraints and point the variable to this structure. Multiple cones can be created for the same solver, but it is usually more efficient to group all blocks into the same conic structure.

All subroutines that pass data to the semidefinite cone use this SDPCone variable in the first argument. The second argument often refers to a specific block. The blocks will be labeled from $0$ to nblocks-1. The subroutine SDPConeSetBlockSize(SDPCone sdpcone, int blockj, int n) can be used to specify the dimension of each block and the subroutine SDPConeSetSparsity( SDPCone sdpcone, int blockj, int nnzmat) can be used to specify the number of nonzero matrices ${\tt A_{i,j}}$ in each block. These subroutines are optional, but using them can improve error checking on the data matrices and perform a more efficient allocation of memory.

The data matrices can be specified by any of the following commands. The choice of data structures is up to the user, and the performance of the problem depends upon this choice of data structures. In each of these subroutines, the first four arguments are a pointer to the SDPCone object, the block number, and the number of variable associated with it, and the number of rows and columns in the matrix. The blocks must be numbered consecutively, beginning with the number $0$. The $y$ variables are numbered consecutively from $1$ to $m$. The objective matrices in (P) are specified as constraint number $0$. The data that is passed to the SDPCone object will be used in the solver, but not modified. The user is responsible for freeing the arrays of data it passes to DSDP after solving the problem.

The square symmetric data matrices $A_{i,j}$ and $C_j$ can be represented with a single array of numbers. DSDP supports the symmetric packed storage format. In symmetric packaged storage format, the elements of a matrix with $n$ rows and columns are ordered as follows:

$$\begin{array}{llllllll} [ a_{1,1} & a_{2,1} & a_{2,2} & a_{3,1} & a_{3,2} & a_{3,3}, & \ldots, & a_{n,n} ]. \end{array}$$ (9)

In this array $a_{k,l}$ is the element in row $k$ and column $l$ of the matrix. The length of this array is $n(n+1)/2$, which is the number of distinct elements on or below the diagonal. Several routines described below have an array of this length in its list of arguments. In this storage format, the element in row $i$ and column $j$, where $i \geq j$, is in element $i(i-1)/2 + j-1$ of the array.

This array can be passed to the solver using the subroutine

SDPConeSetDenseVecMat(SDPCone sdpcone,int blockj, int vari, 
                      int n, const double val[], int nnz);

The first argument point to a semidefinite cone object, the second argument specifies the block number $j$, and the third argument specifies the variable $i$ associated with it. Variables $1, \ldots, m$ correspond to matrices $A_{1,j}, \ldots, A_{m,j}$ whereas variable $0$ corresponds to $C_{j}$. The fourth argument is the dimension (number of rows or columns) of the matrix, $n$. The fifth argument is the array, and sixth argument is the length of the array. The application is responsible for allocating this array of data and eventually freeing it. DSDP will directly access this array in the course of the solving the problem, so it should not be freed until the solver is finished.

A matrix can be passed to the solver in sparse format using the subroutine

SDPConeSetSparseVecMat(SDPCone sdpcone,int blockj, int vari, int n, int ishift
                       const int ind[], const double val[], int nnz);

In this subroutine, the first four arguments are the same as in the subroutine for dense matrices. The sixth and seventh arguments are an array an integers and an array of double precision variables. The final argument states the length of these two arrays, which should equal the number of nonzeros in the lower triangular part of the matrix. The array of integers specifies which elements of the array (9) are included in the array of doubles. For example, the matrix

$$A_{i,j} = \left[ \begin{array}{ccc} 3 & 2 & 0 \ 2 & 0 & 6 \ 0 & 6 & 0 \end{array} \right]$$ (10)

could be inserted into the cone using one of several ways. If the first element in the val array is $a_{1,1}$, the first element in the ind array should be $0$. If the second element in the val array is $a_{3,2}$, then the second element in ind array should be $4$. When the ordering of elements begins with $0$, as just shown, the fifth argument ishift in the subroutine should be set to $0$. In general, the argument ishift specifies the index assigned to $a_{1,1}$. Although the relative ordering of the elements will not change, the indices assigned to them will range from ishift to ishift + $n (n+1)/2 - 1$. Many applications, for instance, prefer to index the array from $1$ to $n(n+1)/2$, setting the index argument to $1$. The matrix (10) can be set in the block $j$ and variable $i$ of the semidefinite cone using one of the routines

SDPConeSetSparseVecMat(sdpcone,j,i,3,0,ind1,val1,3);
SDPConeSetSparseVecMat(sdpcone,j,i,3,1,ind2,val2,3);
SDPConeSetSparseVecMat(sdpcone,j,i,3,3,ind3,val3,4);

where

$$\begin{array}{ll} \tt {ind1} = [ \begin{array}{ccc} 0 & 1 & ... ...begin{array}{cccc} 6 & 3 & 0 & 2 \end{array} ]. \\ \end{array}$$

As these examples suggest, there are many other ways to represent the sparse matrix. The nonzeros in the matrix do not have to be ordered, but ordering them may improve the efficiency of the solver. DSDP assumes that all matrices ${\tt A_{i,j}}$ and ${\tt C_{j}}$ that are not explicitly defined and passed to the SDPCone structure will equal the zero matrix.

To check whether the matrix passed into the cone matches the one intended, the subroutine

SDPConeViewDataMatrix(SDPCone sdpcone,int blockj, int vari)

can be used to print out the the matrix to the screen. The output prints the row and column numbers, indexed from $0$ to $n-1$, of each nonzero element in the matrix. The subroutine SDPConeView(SDPCone sdpcone,int blockj) can be used to view all of the matrices in a block.

After the DSDP solver has been applied to the data and the solution matrix $X_{j}$ have been computed (See DSDPComputeX(), the matrix can be accessed using the command

SDPConeGetXArray(SDPCone sdpcone, int blockj, double *xmat[], int *nn);

The third argument is the address of a pointer that will be set to the array containing the solution. The integer whose address is passed in the fourth argument will be set to the length of this array, $n(n+1)/2$, for the packed symmetric storage format. Since the $X$ solutions are usually fully dense, no sparse representation is provided. These arrays were allocated by the SDPCone object during DSDPSetup() and the memory will be freed by the DSDP solver object when it is destroyed. The array used to store $X_{j}$ could be overwritten by other operations on the SDPCone object. The command,

SDPConeComputeX(SDPCone sdpcone, int blockj, int n, double xmat[], int nn)

recomputes the matrix $X_{j}$ and places it into the array specified in the fourth argument. The length of this array is the fifth argument and the dimension of the block in the third argument. The vectors $y$ and $\Delta y$ needed to compute the matrices $X{j}$ are stored internally in SDPCone object. The subroutine SDPConeMatrixView(SDPCone sdpcone, int blockj); can be used to print this matrix to standard output.

The dimension of each block can be found using the routine

SDPConeGetBlockSize(SDPCone sdpcone, int blockj, int *n)

where the second arguments is the block number and the third arguments are the address of a variable.

The matrix $S$ in (D) can be computed and copied into an array using the command

SDPConeComputeS(SDPCone sdpcone, int blockj, double c, double y[], int m, double r,
                int n, double smat[], int nn);

The second argument specifies which block to use, the fourth argument is an array containing the variables $y$. The second argument is the multiple of the matrix $C$ to be added, and the sixth argument is the multiple of the identity matrix to be added. The sixth argument is the dimension of the block, and the seventh argument is an array whose length is given in the eighth argument.

The memory required for the $X_j$ matrix can be significant for large problems. If the application has an array of double precision variables of length $n(n+1)/2$ available for use by the solver, the subroutine

SDPConeSetXArray(SDPCone sdpcone,int blockj, int n, double xmat[], int nn)

can be used to pass it to the cone. The second argument specifies the block number whose solution will be placed into the array xmat. The third argument is the dimension of the block. The dimension specified in the fifth argument nn refers to the length of the array. The DSDP solver will use this array as a buffer for its computations and store the solution $X$ in this array at its termination. The application is responsible for freeing this array after the solution has been found.

DSDP also supports the symmetric full storage format. In symmetric full storage format, an $n\times n$ matrix is stored in an array of $n^2$ elements in row major order. That is, the elements of a matrix with $n$ rows and columns are ordered

$$\begin{array}{lllllllllllllll} [ a_{1,1} & 0 & \ldots & 0 ... ...& 0 & & \ldots & & a_{n,1} & \ldots, & a_{n,n} ]. \end{array}$$ (11)

The length of this array is $n\times n$. Early versions of DSDP5 used the packed format exclusively, but this format has been added because its more convenient for some applications. The routines

SDPConeSetStorageFormat(SDPCone sdpcone,int blockj, char UPLQ)
SDPConeGetStorageFormat(SDPCone sdpcone, int blockj, char *UPLQ)

set and get the storage format for a block. The second argument specifies the block number and the third argument should be 'P' for packed storage format and 'U' for full storage format. The default value is 'P'. These storage formats correspond the LAPACK storage formats for the upper half matrices in column major ordering. All of the above commands apply to the symmetric full storage format. One difference in their use, however, is that the size of the arrays in the arguments should be $n\times n$ instead of $n \times (n+1)/2$. Using the symmetric full storage format, if the first element in the val array is $a_{1,1}$, the first element in the ind array should be $0$. If the second element in the val array is $a_{3,2}$, then the second element in ind array should be $8$. The matrix (10) can be set in the block $j$ and variable $i$ of the semidefinite cone using one of the routines

SDPConeSetSparseVecMat(sdpcone,j,i,3,0,ind1,val1,3);

where

$$\begin{array}{ll} \tt {ind1} = [ \begin{array}{ccc} 0 & 3 & ... ... [ \begin{array}{ccc} 3 & 2 & 6 \end{array} ] \\ \end{array}.$$