finding $\arg\min_c \sum(c_{yj}-c_j)^2 +\lambda\sum|c_j|$

Question

$c_{yj}$ are my known data coefficients, and I try to minimize the $c_j$'s.

Differentiating I get that $$\frac{\partial}{\partial c_j}=2c_j-2c_{yj}+\lambda \operatorname{sign}(c_j) =0 $$ $$\Rightarrow c_j = \begin{cases} c_{yj}-\lambda/2, & \lambda/2 < c_{yj} \\ c_{yj}+\lambda/2, & -\lambda/2 > c_{yj} \end{cases} $$ I'm not sure what happens in $|c_{yj}|<\lambda/2$. The results get into an infinite loop.

This is equivalent to trying to find (setting $c_{yj}=5, \lambda=20$, replacing $c_{yj}$ with $x$) to

$x=5-10\cdot\operatorname{sign}\left(x\right)$

I think that there is no solution. As you get that the sign of $x$ keeps alternating. Yet when I plot this in Desmos, for example, I get that the solution is $0$. Also, I'm trying to prove (homework exercise) that this is actually $0$, since I know the solution should be

$$\operatorname{sign}(c_j)(|c_j|-\lambda/2)_+ $$

So, how do I get to $0$?

Answer 1

You're missing an important detail in your argument: that function is not differentiable at zero. The case where $-\lambda/2<c<\lambda/2$ corresponds to the case where $x=0$. One way to see this is the following: suppose $-\lambda/2<c<\lambda/2$ then if $x>0$ then you will want to decrease it's value and the contrary if $x<0$. Thus, the optimum is $x=0$. Of course there is a literature on how to solve problems with kinks but I don't think it adds much value here. Now, can you figure out why does this solution converge to zero?

Answer 2

What my optimization professor wrote to me (summarized by myself):

This is a very-very known problem of computing a prox-mapping. The function is coercive, so we know that a minimum must be attained (proved by Weierstraß theorem). If it's not possible to find one where the function is differentiable, then it must be in one of the non-differentiable points, which in this case is only one point - zero.