1
$\begingroup$

I am trying to understand how to solve the following simple semidefinite program by hand.

$$\begin{array}{ll} \text{minimize} & x_{11}\\ \text{subject to} & 2 x_{12} = 1\\ & \begin{pmatrix} x_{11} & x_{12}\\ x_{12} & x_{22} \end{pmatrix} \succeq 0\end{array}$$

I have figured out that in the standard formulation we have

$$\begin{array}{ll} \text{minimize} & \mbox{tr} \left( C X \right)\\ \text{subject to} & \mbox{tr} \left( A X \right) = b\\ & X \succeq 0\end{array}$$

where

$$ C = \left(\begin{array}{cc}1 & 0\\ 0 & 0 \end{array}\right)$$ and $$ A = \left(\begin{array}{cc}0 &1\\ 1 & 0 \end{array}\right)$$ and $ b = 1$

However, I have no idea how to proceed from there. Any pointers?

$\endgroup$
  • 1
    $\begingroup$ You mean $ Trace( AX ) $, right? $\endgroup$ – Dunkel Jun 5 at 21:45
  • $\begingroup$ No, $ tr(C \cdot X)$ is correct. $\endgroup$ – lara123456 Jun 6 at 7:15
  • $\begingroup$ I meant this for the constraint. Instead of $ A X = b $, it should $ Tr (A X) = b $. $\endgroup$ – Dunkel Jun 6 at 7:32
  • $\begingroup$ yes, that is correct. $\endgroup$ – lara123456 Jun 6 at 7:42
  • $\begingroup$ This helps? math.stackexchange.com/questions/2982336/… $\endgroup$ – Dunkel Jun 6 at 8:13
0
$\begingroup$

Because of the restriction we get $ X = \left( \begin{array}{cc} x_{11} & 1/2 \\ 1/2 & x_{22} \end{array} \right)$ and therefore $x_{11}x_{22} - 1/4 \geq 0 $ because $X$ is positive semidefinite. This is the solution for the primal form. However I have no idea how to calculate the solution for the dual form.

$\endgroup$
  • $\begingroup$ You forgot the diagonal entries. The constraint $X \succeq 0$ encapsulates $2^2 - 1 = 3$ inequality constraints, namely, $x_{11} \geq 0$, $x_{22} \geq 0$ and $\det (X) \geq 0$ (which you have considered already). $\endgroup$ – Rodrigo de Azevedo Jun 8 at 8:03
  • $\begingroup$ Why do you need the dual? $\endgroup$ – Rodrigo de Azevedo Jun 8 at 8:38

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.