2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Your question is closely related to the derivation of the convex conjugate of the 2-norm. $\endgroup$
    – LinAlg
    Apr 15, 2018 at 14:29

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you ! I did not learn about the cauchy-schwarz inequality so this is extra useful :) $\endgroup$
    – Kong
    Apr 15, 2018 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, 2018 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, 2018 at 14:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .