Explicit Example Of Semidefinite Duality

Consider the following semidefinite programming problem:
$$ \text{minimize }\, x+2y \qquad \mbox{subject to} \quad \begin{bmatrix} x & 1 \\ 1 & y \end{bmatrix} \succeq 0.$$

(a) Draw the feasible set. Is it convex?

(b) Write the dual semidefinite program.

(c) What are the optimal solutions?

(d) What can you say about strong duality?


(a) It is convex:

(b) The dual problem is to maximize $2t$ subject to the constraint that $\begin{pmatrix} 1 & 0 \\ 0 & 2 \end{pmatrix}-t\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\succeq 0$.

(c)The optimal solutions (not the value(s), right?) are $X=\begin{pmatrix} \sqrt{2} & 1 \\ 1 & \frac{\sqrt{2}}{2} \end{pmatrix}$ and $t = \sqrt{2}$.

(d) Since the optimal solutions from (c) yield the same optimal value (equal to $2\sqrt{2}$), we say that strong duality holds(?). -MH

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License