1

I have so far:

$x-a+\lambda = 0,x>0$

$x-a-\lambda = 0,x<0$

Is there an explicit solution w.r.t. $a$ and $\lambda$?

jubueche
  • 145
  • i think this is A.M-G.M application question, to minimize the G.M you need to equate both terms and find $x$ – avz2611 Nov 02 '17 at 14:37
  • Split the problem into two cases, $\lambda \ge 0$ and $\lambda <0 $. It might help to note that $|x| = \max(x,-x)$. – copper.hat Nov 02 '17 at 14:49
  • I have the choice between $x=a-\lambda$ or $x=a+\lambda$ (depending on $sign(x)$).When plugged into $f(x)$, they both yield $1/2*\lambda^2$ at the end. So it really depends on the first term, right? The first $|x|$ is minimal for $min(a-\lambda,a+\lambda)$. Is this my x? $min(a-\lambda,a+\lambda)$? – jubueche Nov 02 '17 at 16:57

1 Answers1

1

Some thoughts...

Given $$\min_x f(x) = \lambda |x| + \frac{1}{2}(x-a)^2$$ we find $$f^{\prime}(x) = \lambda \frac{x}{|x|} + (x-a) \\ f^{\prime\prime}(x) = 1.$$

Now the minimum will occur either when $f^{\prime}(x)= 0$ or when $x$ is at an endpoint (i.e., unbounded). Assuming $x \neq 0$, we have: $$ \begin{align} \frac{x\lambda - a|x| + x|x|}{|x|} &= 0 \\ x\lambda - a|x| + x|x| &= 0 \\ x\lambda + x|x| &= a|x| \\ \frac{x\lambda + x|x|}{a} &= |x| \\ \end{align} $$ Now we have two cases: $$ \begin{align} \begin{cases} x &= \frac{x\lambda + x|x|}{a} \\ x &= -\frac{x\lambda + x|x|)}{a}\\ \end{cases} \end{align} $$ These cases end up giving the same result, so following the first case, we have: $$ \begin{align} \frac{ax + x\lambda + x|x|}{a} &= 0 \\ x(a-\lambda - |x|) &= 0 \\ a - \lambda - |x| &= 0 \quad \text{ (assuming } x\neq 0 \text{ again)} \\ |x| = a - \lambda &\implies \begin{cases} x = a - \lambda \\ x = -(a - \lambda) \end{cases} \end{align} $$

jjjjjj
  • 2,671
  • 1
    Ok cool. So $x$ is determined by $min(a-\lambda,a+\lambda)$. This seems to be what I wrote in the above comment. Thank you. – jubueche Nov 03 '17 at 15:58
  • 1
    Btw, if you draw it with a fixed positive $\lambda$, a on the x-axis and x on the y-axis you get soft thresholding! https://www.google.ch/search?q=soft+thresholding&source=lnms&tbm=isch&sa=X&ved=0ahUKEwi4kqPLi6jXAhXFSRoKHUt3CMYQ_AUICigB&biw=1280&bih=612#imgrc=FVrk0OP7FKMH0M: – jubueche Nov 05 '17 at 18:47
  • Cool! I didn't think of it this way, but now that you mention it, the structure reminds me of a regularized least squares problem! Also here – jjjjjj Nov 05 '17 at 18:55