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?


Solution:

(a) It is convex:
sage0.png

(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