# Dual of a Second Order Cone Program (SOCP)

I was reading on second order cone programs https://www.di.ens.fr/~aspremon/PDF/MVA/Duality.pdf page 33 and have trouble trying to derive its dual. While I am able to formulate the lagrangian easily, I do not understand how the following steps are carried out.

For the steps below, I perfectly understand that the minimum over x and t is only bounded if the expression in the green and blue boxes (excluding x and t) are zero. But what about the minimum over y ? Why is the infimum over y = 0 if the L2 norm of $v_i$ is less than $\lambda_i$ ?

• Your question is closely related to the derivation of the convex conjugate of the 2-norm. – LinAlg Apr 15 '18 at 14:29

First assume that $\| \nu_i \|_2 \leq \lambda_i$. From the Cauchy-Schwarz inequality we have $$- \nu_i^T y_i \leq \| \nu_i \|_2 \| y_i \|_2 \leq \lambda_i \| y_i \|_2$$ which implies that $$\lambda_i \| y_i \|_2 + \nu_i^T y_i \geq 0.$$ It follows that $$\inf_{y_i} \,\lambda_i \| y_i \|_2 + \nu_i^T y_i = 0$$ in this case.
Next assume that $\| \nu_i \|_2 > \lambda_i$. Note that $\lambda_i$ is constrained to be nonnegative in the dual problem. If we take $y_i = - s \nu_i$ for some $s > 0$, then \begin{align} \lambda_i \| y_i \|_2 + \nu_i^T y_i &= \lambda_i s \| \nu_i \|_2 - s \| \nu_i \|_2^2 \\ &= s\| \nu_i \|_2 ( \underbrace{\lambda_i - \| \nu_i \|_2}_{< \,0 }), \end{align} which can be made as negative as we like by taking $s$ to be very large. Thus in this case we have $$\inf_{y_i} \,\lambda_i \| y_i \|_2 + \nu_i^T y_i = -\infty.$$