Past exam of the continuous optimisation course of the University of Oxford / 2011 / 3 / iv / Solution

Reverse the order of the two optimizations to obtain the Lagrangian dualPut $s=c-A^{T}y$ and $r=\sqrt{s^T{Q}^{-1}s}$. For $\gamma >0$, completing the square givesAt $\gamma =0$ the infimum is finite precisely if $s=0$, when it equals $b^{T}y$. For $r>0$, the expression $\gamma +r^2/(4\gamma )$ is minimized at $\gamma =r/2$, with value $r$. The same optimized value holds when $r=0$, choosing $\gamma =0$. Eliminating $\gamma$ therefore gives ${\sup }_y\{b^{T}y-\sqrt{s^T{Q}^{-1}s}\}$. Introducing $\theta =r$ yieldsThe nonnegative square root is enforced by $\theta \ge 0$. Optimizers correspond by $\gamma =\theta /2$, including the zero case.