Is there an analytical solution for the following optimization problem:

$b, y \in \mathbb{R}^n$ (vectors), $b^* = \arg min_{b \in \mathbb{R}^n} f(b)$, where $f(b) = ||b-y||_{2}^{2} + \varphi ||b||_{1}$ where $\varphi > 0$

Its so close to $L_1$ regression, but I cant solve this even in that way.

  • $\begingroup$ Welcome to CV. It would all depend on what "$\varphi$" means: that detail is essential for answering your question. $\endgroup$
    – whuber
    Feb 12 '20 at 13:53
  • $\begingroup$ $\phi$ is a constant which greater than 0 $\endgroup$
    – Leeds
    Feb 14 '20 at 10:57
  • $\begingroup$ Ah--so $\phi$ is not a function. This problem is called the "Lasso." See stats.stackexchange.com/search?q=lasso+closed+form for the general problem. Since yours is so specific, it is plausible it would have a specific answer (+1). $\endgroup$
    – whuber
    Feb 14 '20 at 15:49

Using vector math re-writing your problem, also replacing b with X: $$f(X)=(X-Y)^T(X-Y)+\varphi |X|^T 1$$ First Order Conditions: $$f(X)'=0$$ $$2(X-Y)+\varphi \space\mathrm{sign}(X)=0$$ Solution: $$X=Y-\mathrm{sign}(X)\varphi/2$$

  • when $|Y_i|\ge\varphi/2$: $$X=Y-\mathrm{sign}(Y)\varphi /2$$
  • when $|Y_i|<\varphi/2$: $$X=0$$
  • $\begingroup$ +1. But what does "F.O.C." mean? $\endgroup$
    – whuber
    Feb 14 '20 at 17:47
  • 1
    $\begingroup$ @whuber, I spelled it out, 1st order conditions $\endgroup$
    – Aksakal
    Feb 14 '20 at 18:11

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.