5
$\begingroup$

I plans to use CSDP to solve the following semi-definite problem: $$\min_{B, \beta}\operatorname{trace}(CB) \\ \text{s.t.} \ \operatorname{trace}(AB)=1 \\ \beta\geqslant 0 \\ \begin{bmatrix} 1 & \beta^{T}\\ \beta& B \end{bmatrix}\succeq 0$$ where $A$, $B$, $C$ are $M\times M$ matrices,and $\beta$ is an $M$-dimensional column vector.

But I have some difficulty in transforming it to the standard form: $$\max_{X}\operatorname{trace}(CX) \\ \text{s.t.} \ \operatorname{trace}(A_{i}X)=a \\ X\succeq 0$$

Thanks!

$\endgroup$
  • $\begingroup$ How are you going to call CSDP? From MATLAB, or from C, or... ? Or are you going to create an SDPA-format file? Because really, that standard form is not necessarily what you want to transform it to---it's the input format you use that matters. $\endgroup$ – Michael Grant May 23 '13 at 17:05
  • $\begingroup$ I'm going to use the subroutine interface of CSDP. So I have to fix $C$ and constraint matrices as input of CSDP's callable functions. $\endgroup$ – ZeyuHu May 24 '13 at 1:04
  • $\begingroup$ OK, then I think what I have shared with you below will do it. $\endgroup$ – Michael Grant May 24 '13 at 1:08
3
$\begingroup$

[NOTE: I'm using $n$ instead of $M$ as the key dimension here, sorry... it's too much trouble to go back and change everything...]

Well, $X$ is actually going to be an $2n+1\times 2n+1$ matrix with this block structure when you are done: $$\begin{bmatrix} 1 & \beta^T \\ \beta & B \\ & & \beta_1 \\ & & & \beta_2 \\ & & & & \ddots \\ & & & & & \beta_n \end{bmatrix}$$ So in addition to your single equality constraint you need to make sure that $X_{1,1}=1$ and $X_{k+1,1}=X_{n+k+1,n+k+1}$ for $k=1,2,\dots,n+1$. So you have $n+2$ equality constraints to build. So I think it looks something like this: $$\bar{C} = \begin{bmatrix} 0 & 0_{1\times n} \\ 0_{n\times 1} & C \\ & & 0\\ & & & 0\\ & & & & \ddots \\ & & & & & 0 \end{bmatrix}$$ $$\bar{A}_1 = \begin{bmatrix} 0 & 0_{1\times n} \\ 0_{n\times 1} & A \\ & & 0\\ & & & 0\\ & & & & \ddots \\ & & & & & 0 \end{bmatrix}, \quad a_1 = 1$$ $$\bar{A}_2 = \begin{bmatrix} 1 & 0_{1\times n} \\ 0_{n\times 1} & 0_{n\times n} \\ & & 0\\ & & & 0\\ & & & & \ddots \\ & & & & & 0 \end{bmatrix}, \quad a_2 = 1$$ $$\bar{A}_{k+2} = \begin{bmatrix} 0 & \tfrac{1}{2}e_k^T \\ \tfrac{1}{2}e_k & 0_{n\times n} \\ & & -\mathop{\textrm{diag}}(e_k) \end{bmatrix}, \quad a_{2+k} = 0, \quad k=1,2,\dots, n$$ where $e_k$ is the $n$-vector with $1$ in the $k$th position and zeros elsewhere. See the section "Using the subroutine interface to CSDP" in the CSDP user guide for information about how to translate this block structure into CSDP's preferred format.

But, since I have you here: it would be much easier for you if you did not have to plug this into CSDP. If running in MATLAB is acceptable to you, you could use my toolbox CVX to solve this, and the model would look like this:

cvx_begin sdp
    variables B(n,n) b(n)
    minimize(trace(C*B))
    subject to
        trace(A*B) == 1;
        [ 1, b' ; b, B ] >= 0;
        b >= 0; 
cvx_end

Of course, if you're stuck in C, I understand! CSDP is a very nice solver particularly for standalone applications. I hope I have been helpful either way.

$\endgroup$
  • 1
    $\begingroup$ There's also a midway option in which you use the MATLAB interface to CSDP. This interface works very much like the SeDuMi interface, so you could test both solvers on your problem without any great effort. $\endgroup$ – Brian Borchers May 23 '13 at 18:08
  • $\begingroup$ Yes, very good point. $\endgroup$ – Michael Grant May 23 '13 at 18:16
  • $\begingroup$ Thanks a lot! It is really helpful! I have a question: Does it hold that a symmetric matrix(like$X$ here) is positive semi-definite if all of its main diagonal entries is positive? What about its inverse? $\endgroup$ – ZeyuHu May 24 '13 at 2:04
  • $\begingroup$ Another question, here we get a new $\bar {X}$, but we didn't make sure it has such a block structure which should be stated as a constraint,I wonder the off-diagonal entries of $\bar {X}$'s blocks may not be zero during output. $\endgroup$ – ZeyuHu May 24 '13 at 2:43
  • $\begingroup$ CSDP knows what to do here. X will have the block structure you want. Actually, SDP duality theory helps guarantee that. $\endgroup$ – Michael Grant May 24 '13 at 2:59

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.