1
$\begingroup$

For a SDP problem with LMI, we can write it as: $$minimize \quad c^Tx$$ $$ s.t. \quad x_1F_1+x_2F_2+...+x_nF_n+G \preceq 0$$ $$Ax=b$$ where $G,F_1,F_2,...,F_n \in S^k,A \in R^{p \times n}$.

Now I want to transform above form to SDP of standard form: $$minimize \quad tr(CX)$$ $$s.t. \quad tr(A_iX)=b_i,i=1,2,...,p$$ $$X \succeq 0$$ Where $C,A_1,...,A_p \in S^n$.

Suppose $A=\begin{bmatrix} a^T_1 \\ a^T_2 \\ \vdots \\a^T_p\end{bmatrix}$, I tried to diagonalize $c,x,a_i$ such that: $$C=diag(c),X=diag(x),A_i=diag(a_i)$$

But I cannot figure out how satisfying constraint $X \succeq 0$. So what is the trick?

$\endgroup$
6
  • $\begingroup$ Why $\preceq$?? $\endgroup$ Sep 11, 2017 at 13:42
  • $\begingroup$ Did you refer to "$ \preceq$" in $x_1F_1+x_2F_2+...+x_nF_n+G \preceq 0$? $\endgroup$
    – Finley
    Sep 11, 2017 at 13:49
  • 1
    $\begingroup$ Yes. Usually, $\succeq$ is used instead. $\endgroup$ Sep 11, 2017 at 13:54
  • 1
    $\begingroup$ This might help, but it's not a true duplicate: Convert Semidefinite program forms $\endgroup$ Sep 11, 2017 at 14:12
  • 2
    $\begingroup$ Is this an academic exercise or do you think you need to do this to actually solve it? Because if it's the latter, you should stop right now, and use a proper modeling framework like YALMIP or CVX (disclaimer: mine) so you don't have to. $\endgroup$ Sep 11, 2017 at 14:13

2 Answers 2

1
$\begingroup$

You can dualize the problem but for that we need to assume that Slater's condition holds.

First, we build the Lagrangian

$$L(x,P,\mu):=c^Tx-\mathrm{trace}(PM(x))+\mu^T(Ax-b)$$

where $M(x):=x_1F_1+x_2F_2+...+x_nF_n+G$, $P$ is symmetric positive semidefinite and $\mu$ is a real vector.

The dual problem is, therefore,

$$\max_{P\succeq0,\mu\in\mathbb{R}^n}-(\mathrm{trace}(PG)-\mu^Tb)$$ such that

$$\mathrm{trace}(PF_i)+\mu^TAe_i=c_i.$$

where $\{e_1,\ldots,e_n\}$ is the natural basis of $\mathbb{R}^n$.

It is also possible to lump all the variables in the single matrix $\tilde P=\mathrm{diag}(P,U)$ where $U=\mathrm{diag}(\mu)$ to get

$$\max_{\tilde P}-\mathrm{trace}(\tilde PZ_0)$$ such that

$$\mathrm{trace}(\tilde PZ_i)=c_i$$

where $Z_0=\mathrm{diag}(G,\mathrm{diag}(b))$ and $Z_i=\mathrm{diag}(F_i,\mathrm{diag}(Ae_i))$.

$\endgroup$
0
$\begingroup$

Instead of trying to rewrite it directly, since you already have a LMI it might be easier to write $Ax=b$ into the LMI.

Let \begin{align*} &\min c^{\mathsf T} x \\ &\text{s.t. } \sum_{i=1}^n x_i F_i - G \succcurlyeq 0,\ Ax=b \end{align*} be the given problem, where $G,\ F_i \in S^k$, $A \in \mathbb{R}^{p\times n}$, $x \in \mathbb{R}^n$, $b \in \mathbb{R}^p$.

Let $a_i$ be the columns of $A$, $i=1,\dots,n$. We can rewrite $Ax=b$ as $\sum_{i=1}^n a_i x_i - b = 0$ element wise. This can then be written as two constraints $\sum_{i=1}^n a_i x_i - b \ge 0$ and $\sum_{i=1}^n -a_i x_i - (-b) \ge 0$. Now we can simply add this to the LMI, so we get $\sum_{i=1}^n x_i F'_i - G' \succcurlyeq 0$, for block matrices \begin{align*} F'_i &= \begin{bmatrix} F_i & & \\ & \text{diag}(a_i) & \\ && -\text{diag}(a_i) \end{bmatrix} \\ G' &= \begin{bmatrix} G && \\ & \text{diag}(b) & \\ &&-\text{diag}(b) \end{bmatrix} \end{align*} using that a block matrix is PSD if and only if its blocks are PSD, and a diagonal matrix is PSD if and only if its diagonal elements are nonnegative.

Now we are done, because the dual is \begin{align*} &\max \langle G', X \rangle \\ &\text{s.t. } \langle F'_i, X \rangle = c_i \quad i=1,\dots,n \\ &\qquad X \succcurlyeq 0. \end{align*}

$\endgroup$

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.