KKT conditions on minimization problem

I am trying to get an explicit solution to the following problem with the help of KKT conditions. But I am stuck.

The problem:

$min_x 1/2 ||y-x||^2_2 + \lambda||x||_1$

This is what I have done so far:

I have applied stationarity of KKT to get:

$0 = - (y-x) + \lambda S$

$S_i = sign(X_i) \ if X_i = 0$ else, $S_i \in [-1,1] \ if \ X_i = 0$

Looking at the $i^{th}$ component of this I see:

$y -x = \lambda S_i \ \ i = 1 .....r$

Looking at this we can also conclude that

If $|y-x| < \lambda$ then $X_i = 0$

and,

$|y-x| = \lambda$ then $S_i = +- 1$

What do I do after this in order to get an explicit solution for the problem?

• $y$ and $\lambda$ are given? $r$ is the number of components? There are no constraints? Is anything assumed about $\lambda$? – Robert Israel Oct 27 '13 at 23:21
• Why would you need to use KKT conditions on an unconstrained minimization? – copper.hat Oct 27 '13 at 23:21
• As an aside, the cost is not differentiable, so unless you are using Clark subgradients, you cannot just apply KKT. – copper.hat Oct 28 '13 at 1:04
• Yes. But you could take subgradients? Like I am doing in the problem? – Alice Oct 28 '13 at 1:08
• I am trying to do it with subgradients @copper.hat . How would I proceed? – Alice Oct 28 '13 at 1:08

I am assuming $\lambda \ge 0$.

For $y \in \mathbb{R}$, define $\phi_y: \mathbb{R} \to \mathbb{R}$ by $\phi_y(x) = \frac{1}{2}(x-y)^2 + \lambda |x|$.

Note that the above problem is equivalent to $\min_x \sum_i \phi_{y_i}(x_i)$, so the problem is separable and we can focus on solving $\min_x \phi_y(x)$ where $x \in \mathbb{R}$. (Since $\lim_{x \to \infty} \phi_y(x) = \infty$, it is clear that the problem has a solution.)

If we let $\alpha(x) = |x|$ we have $\partial \alpha(x) = \begin{cases} \{ \operatorname{sgn} x \}, & x \neq 0 \\ [-1,1], & x = 0\end{cases}$.

At a solution $\hat{x}$ we have $0 \in \partial \phi_y(\hat{x})$. Since the cost is regular, we have $0 \in \{\hat{x}-y\} + \lambda \partial \alpha(\hat{x})$, or $y=\hat{x}+\lambda \xi$, where $\xi \in \partial \alpha(\hat{x})$.

If $\hat{x} = 0$, we see $|y| \le \lambda$, and if $\hat{x} \neq 0$, we see that $y = \hat{x} + \lambda \operatorname{sgn} \hat{x} = \operatorname{sgn} \hat{x} (|x|+\lambda)$, and so $|y| > \lambda$.

It follows that if $|y| \le \lambda$, then $\hat{x} = 0$, and if $|y|>\lambda$, then $\hat{x} = y-\lambda \operatorname{sgn} \hat{x}=y-\lambda \operatorname{sgn} y= (\operatorname{sgn}y)(|y|-\lambda)$.

These cases can be combined to get $\hat{x} =(\operatorname{sgn}y)\max(|y|-\lambda,0)$.

Hence the solution to the original problem is given by $\hat{x}_i =(\operatorname{sgn}y_i)\max(|y_i|-\lambda,0)$.

• I have seen this numerous times at many places, but I still fail to understand why is $\partial \alpha(x) = [-1,1]$ when $x=0$, and why not $\partial \alpha(x) =0$? – AAP Oct 28 '13 at 19:10
• @AAP: Since $\alpha$ is convex, we can just look at the subgradient, which is $\partial \alpha(0) = \{ h | f(x)-f(0) \ge h x, \ \forall x \} = \{ h | |x| \ge h x, \ \forall x \}= [-1,1]$. Draw a picture, and look at the supporting hyperplanes to $\operatorname{epi} \alpha$ at $x=0$. – copper.hat Oct 28 '13 at 19:16