0
$\begingroup$

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?

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

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

$\endgroup$
2
  • $\begingroup$ 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 $? $\endgroup$ – AAP Oct 28 '13 at 19:10
  • $\begingroup$ @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$. $\endgroup$ – copper.hat Oct 28 '13 at 19:16

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.