Semidefinite Cones

If the $jth$ cone is a semidefinite cone consisting of a single block with $n$ rows and columns in the matrices, then the first element in this row of the cell array is the string 'SDP' and the second element is the number n. The third element in this row of the cell array is a sparse matrix with $n(n+1)/2$ rows and $m+1$ columns. Columns $1$ to $m$ of this matrix represent the constraints $A_{1,j}, \ldots, A_{m,j}$ for this block and column $m+1$ represents $C_j$.

The square symmetric data matrices $A_{i,j}$ and $C_j$ map to the columns of ${\tt AC\{j,3\}}$ through the operator ${\bf dvec( \cdot )} : \mathbb{R}^{n \times n} \rightarrow \mathbb{R}^{n(n+1)/2}$, which is defined as

$$\begin{array}{lllllllll} {\bf dvec}(A) & = [ a_{1,1} & a_{1,... ...a_{1,3} & a_{2,3} & a_{3,3} & \ldots & a_{n,n} ]^T. \end{array}$$

In this definition, $a_{k,l}$ is the element in row $k$ and column $l$ of $A$. This ordering is often referred to as symmetric packed storage format. The inverse of dvec( ) is ${\bf dmat( \cdot ) : \mathbb{R}^{n(n+1)/2} \rightarrow \mathbb{R}^{n \times n} },$ which converts the vector into a square symmetric matrix. Using these operations,

$$A_{i,j} = {\tt dmat( AC\{j,3\}(:,i) }), \hspace{ 0.5cm } C_{j} = {\tt dmat( AC\{j,3\}(:,m+1) })$$

and

$${\tt AC\{j,3\} = [ \begin{array}{llll} {\tt dvec(A_{1,j})} & \ldots & {\tt dvec(A_{m,j})} & {\tt dvec(C_{j})} \end{array} ]; }$$

For example, the problem:

$$\begin{array}{llllll} \mbox{Maximize} & & y_1 & + & y_2 \\ \... ...{array}{rr} 4 & -1 \ -1 & 5 \ \end{array} \right] \end{array}$$

can be solved by:

> b = [ 1 1 ]';
> AAC = [ [ 1.0 0 0 ]' [ 0 0 1.0 ]' [ 4.0 -1.0 5.0 ]' ];
> AC{1,1} = 'SDP';
> AC{1,2} = [2];
> AC{1,3} = AAC;
> [STAT,y,X]=dsdp(b,AC);
> XX=dmat(X{1});

The solution $y$ is the column vector y' = [ 3 4 ]' and the solution $X$ is a $p \times 1$ cell array. In this case, X = [ 3 x 1 double ], X{1}'=[ 1.0 1.0 1.0 ], and dmat(X{1})=[ 1 1 ; 1 1 ].

Each semidefinite block can be stated in a separate cone of the cell array; only the available memory on the machine limits the number of cones that can be specified.

Each semidefinite block may, however, be grouped into a single cone in the cell array. To group these blocks together, the second cell entry must be an array of integers stating the dimension of each block. The data from the blocks should be concatenated such that the number of rows in the data matrix increases whereas the number of columns remains constant. The following lines indicate how to group the semidefinite blocks in rows $1$ and $2$ of cell array ${\tt AC1}$ into a new cell array ${\tt AC2}$

> AC2{1,1} = 'SDP';
> AC2{1,2} = [AC1{1,2}  AC1{2,2}];
> AC2{1,3} = [AC1{1,3}; AC1{2,3}]

The new cell array ${\tt AC2}$ can be passed directly into DSDP. The advantage of grouping multiple blocks together is that it uses less memory - especially when there are many blocks and many of the matrices in these blocks are zero. The performance of DSDP measured by execution time, will change very little.

This distribution contains several examples files in SDPA format. A utility routine called readsdpa( $\cdot$ ) can read these files and put the problems in DSDP format. They may serve as examples on how to format an application for use by the DSDP solver. Another example can be seen in the file maxcut( $\cdot$ ) , which takes a graph and creates an SDP relaxation of the maximum cut problem from a graph.