2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Brian Borchers Aug 1 '14 at 2:14
0
$\begingroup$

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.

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

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.