Express SDP problem in CSDP

I am trying to use CSDP and am struggling with this.

Consider for example the SDP problem proposed by prof. Borchers here. Namely:

$$\max_{A,z} \sum_{i} z_{i}\quad\text{subject to}\quad\mbox{tr}(P_{i}A) \geq z_{i},\quad i=1, 2, \ldots, n.\quad A \succeq 0.$$

I am wondering how one represents it in the standard CSDP format:

$$\max_{X} \mbox{Tr}(CX)\quad\text{subject to}\quad\mbox{tr}(A_{i}X)= b_{i},\quad i=1, 2, \ldots, n.\quad X \succeq 0.$$

More precisely, I can see how to specify the $A_i$'s. My problem is how to express the $\sum_i z_i$ in the objective function as $\mbox{Tr}(CX)$.

Inequality constraints in an SDP can be turned into equality constraints by introducing non-negative slack variables. If your original problem is

$\max \Sigma_{i=1}^{n} z_{i}$

subject to

$\mbox{tr}(P_{i}X) \geq z_{i}\;\;$ $i=1, 2, \ldots, n$

$X \succeq 0$

You can rewrite the constraints as

$\mbox{tr}(P_{i}X) - z_{i} \geq 0\;\;$ $i=1, 2, \ldots, n.$

You can then introduce slack variables $w_{i}$, $i=1, 2, \ldots, n$ and write the constraints as

$\mbox{tr}(P_{i}X) - z_{i} -w_{i} = 0\;\;$ $i=1, 2, \ldots, n.$

where $w_{i} \geq 0$, $i=1, 2, \ldots, n$.

I'll assume for this answer that the $z_{i}$ variables are also nonnegative. If they're free to be negative, you could handle this by writing $z_{i}=r_{i}-s_{i}$, where $r, s \geq 0$.

Let $Z=\mbox{diag}(z)$ and $W=\mbox{diag}(w)$. Let

$V=\left[ \begin{array}{ccc} X & 0 & 0 \\ 0 & Z & 0 \\ 0 & 0 & W \\ \end{array} \right]$.

Let

$C=\left[ \begin{array}{ccc} 0 & 0 & 0 \\ 0 & I & 0 \\ 0 & 0 & 0 \\ \end{array} \right]$.

Note that $\mbox{tr}(CV)=\sum_{i=1}^{n} z_{i}$.

Let

$A_{i}=\left[ \begin{array}{ccc} P_{i} & 0 & 0 \\ 0 & -E_{i,i} & 0 \\ 0 & 0 & -E_{i,i} \\ \end{array} \right]\;\;$ $i=1, 2, \ldots, n$.

Here $E_{i,i}$ is the 0 matrix with a single $1$ in the $(i,i)$ position.

Now the original problem can be written in standard form as

$\max \mbox{tr}(CV)$

subject to

$\mbox{tr}(A_{i}V)=b_{i}\;\;$ $i=1, 2, \ldots, n$

$V \succeq 0$.

Note that $V$ is a block diagonal matrix, and that furthermore, $Z$ and $W$ are diagonal blocks. In the SDPA sparse matrix format it is easy to encode $X$ as an $n$ by $n$ positive semidefinite block and $Z$ and $W$ as $n$ by $1$ vectors of non-negative variables. The additional storage required for $Z$ and $W$ is minimal.

The constraint $V \succeq 0$ ensures that all of the blocks on the diagonal of $V$ are positive semidefinite. In particular, $X \succeq 0$, $z \geq 0$, and $w \geq 0$.

I assume that you probably have additional linear constraints on $X$ and $z$. These can easily be added to the formulation.

• Thanks. One more question: does using $-\pmb I$ as the central entry of $\pmb C$ compromises the concavity of the problem? – user189035 Sep 6 '16 at 17:34
• No. The objective $\mbox{tr}(CV)$ is always linear and thus both convex and concave. – Brian Borchers Sep 6 '16 at 17:36
• In case you weren't aware, $\mbox{tr}(CV)=\sum_{i=1}^{n}\sum_{j=1}^{n} C_{i,j}V_{i,j}$ This is a linear combination of the elements of $V$. – Brian Borchers Sep 7 '16 at 0:08