# Solving simple SDP by hand

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?

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

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.
• 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). – Rodrigo de Azevedo Jun 8 at 8:03