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.

enter image description here enter image description here

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$ ?

enter image description here

  • 1
    $\begingroup$ Your question is closely related to the derivation of the convex conjugate of the 2-norm. $\endgroup$ – 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. $$

  • $\begingroup$ Thank you ! I did not learn about the cauchy-schwarz inequality so this is extra useful :) $\endgroup$ – Kong Apr 15 '18 at 12:50
  • $\begingroup$ Sure. A lot of computations similar to this one are done in the textbook Boyd and Vandenberghe, which might be worth checking out if you're not already reading it. $\endgroup$ – littleO Apr 15 '18 at 13:06
  • $\begingroup$ That is interesting. Based on the font I assumed the source of the question was exactly that book. As it turns out, the slides are copied from Question 5.43 of that book and its solution manual. $\endgroup$ – LinAlg Apr 15 '18 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.