# How can I convert this SDP constraint?

I have the following SDP problem:

max: $Tr(CX)$

subject to: $X \geq 0, I - X \geq 0$.

I want to convert it into the standard form specified by CSDP (I'm using the callable C interface), which is:

max: $Tr(CX)$

subject to: $\forall_i, Tr(A_iX) = a_i, X \geq 0$.

The SDP is part of an algorithm which iteratively increases the dimensions of $X$ until the value of $\max\ Tr(CX)$ converges.

Is there any efficient way? $X$ is already known to be sparse, if that helps.

• You haven't said whether $X$ has entries that are unimportant or whether these entries must be 0 in the optimal solution. Do you care either way? – Brian Borchers Aug 1 '14 at 2:14

Suppose that $X \in \mathbb{R}^{n \times n}$, and $X$ is positive semidefinite. For convenience, define

\begin{align} \langle A, B\rangle = \sum_{k, l} A_{kl}B_{kl} \end{align}

for square matrices $A, B$ of equal size; this operation corresponds to the trace of the matrix product.

So your formulation currently looks like

\begin{align} \max \langle{C, X}\rangle \\ \mathrm{s.t.}\,\, X \succeq 0,\,\,I - X \succeq 0, \end{align}

where $X \succeq 0$ means that $X$ is positive semidefinite.

Essentially, I'd create a positive semidefinite matrix of slack variables $S \in \mathbb{R}^{n \times n}$ such that $S + X = I$, and $S \succeq 0$. Let $E_{ij}$ is a matrix of consisting of all zeros except for the $(i,j)$th element, which is set to 1. Also, define the matrices

\begin{align} X' = \left[\begin{array}{cc}X & 0 \\ 0 & S\end{array}\right], \\ C' = \left[\begin{array}{cc}C & 0 \\ 0 & 0\end{array}\right], \\ A_{ij} = \left[\begin{array}{cc} E_{ij} & 0 \\ 0 & E_{ij}\end{array}\right]. \end{align}

Then, (I think,) the following reformulation works:

\begin{align} \max \langle{C', X'}\rangle \\ \mathrm{s.t.}\,\, X' \succeq 0,\,\,\langle A_{ij}, X' \rangle = \delta_{ij},\,\,i,j=1,\ldots,n \end{align}

where $\delta_{ij}$ is the Kronecker delta symbol.

• It does! I checked it with some old notes. – avak Aug 1 '14 at 0:30