0
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. One more question: does using $-\pmb I$ as the central entry of $\pmb C$ compromises the concavity of the problem? $\endgroup$ – user189035 Sep 6 '16 at 17:34
  • 2
    $\begingroup$ No. The objective $\mbox{tr}(CV)$ is always linear and thus both convex and concave. $\endgroup$ – Brian Borchers Sep 6 '16 at 17:36
  • $\begingroup$ 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$. $\endgroup$ – Brian Borchers Sep 7 '16 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.