How to transform this problem, $$\min_{x_1, x_2} x_1 + x_2$$

$$\text{subject to} \\ \|P_\Omega(X-Z)\|_{F}^2 \leq x_1\\ \lambda\| X \|_{\text{tr}} \leq x_2$$

to the standard SDP problem, \begin{equation*} \begin{array}{ll} \min_{x \in \mathbb{R}^p} & c^T x \\ \text{subject to} & x_1 A_1 + \cdots + x_p A_p \preceq B, \end{array} \end{equation*}

Given that solving $\| X \|_{\text{tr}}$ is equivalent to the optimization problem defined as, $$\max_{Y \in \mathbb{R}^{m \times n}} \text{trace}(X^T Y) \\ $$ $$\text{subject to} \left[ \begin{array}{cc} I_m & Y \\ Y^T & I_n \end{array} \right]\succeq 0$$

I know that $\text{trace}(X^T Y) = \langle X,Y\rangle$, so solving $\| X \|_{\text{tr}}$, so it actually looks very much like the conic problem, but how to transform that into standard SDP, where $c$ and $x$ are vectors?

  • 1
    $\begingroup$ Have you taken a look at Maryam Fazel's PhD thesis? Matrix Rank Minimization with Applications (pdf)? $\endgroup$ – Rodrigo de Azevedo Nov 3 '16 at 18:40
  • 1
    $\begingroup$ don't you have constraints? I mean the minimum of every norm is $0$... $\endgroup$ – user251257 Nov 3 '16 at 18:41
  • $\begingroup$ @RodrigodeAzevedo I didn't have chance to look at it yet. Could you tell me which part might be important for this proof? $\endgroup$ – good2know Nov 3 '16 at 18:49
  • $\begingroup$ @user251257 Actually I have $\|\left(P_\Omega(X-Z)\right)^TP_\Omega(X-Z)\|_{tr} \leq \epsilon$. $\endgroup$ – good2know Nov 3 '16 at 18:53
  • $\begingroup$ @v-2 you should include it in your question. $\endgroup$ – user251257 Nov 3 '16 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.