3
$\begingroup$

Consider a vector $a \in R^n$.

I want to know how I can find analytically the solution of the following optimization problem: $x^* = argmin_{x \in R^n} f(x)$, where

  • $f(x) = ||x-a||_{2}^2 + \lambda ||x||_1$
  • $\lambda > 0$ and
  • $||.||_p$ is the p-norm in $R^n$.

Thanks in advance.

$\endgroup$
8
  • $\begingroup$ What's the question? are you asking for some optimization algorithm? pretty much any would do. $\endgroup$ Jan 16, 2019 at 11:42
  • $\begingroup$ @anymous.asker my question is to find $x^*$. Thanks in advance $\endgroup$ Jan 16, 2019 at 12:02
  • $\begingroup$ Take the derivative, set it to zero, isolate x. $\endgroup$ Jan 16, 2019 at 12:04
  • $\begingroup$ @anymous.asker thanks for your answer. The problem that I don' know how to derivate when we have norms. $\endgroup$ Jan 16, 2019 at 12:16
  • 1
    $\begingroup$ @anymous.asker Your comment is not helpful at all. The OP is asking about an objective function with l1 norm, which is not differentiable. Clearly "take the derivative, set it to zero" won't work. And that's why people develops subgradient methods. $\endgroup$
    – user12075
    Jan 16, 2019 at 15:49

1 Answer 1

2
$\begingroup$

In response to the comments suggesting subgradient descent methods: the problem in the question does not contain any sum or similar terms, therefore the variables are independent of each other and there is a closed-form solution: $$ x^* = \begin{cases} a - \frac{\lambda}{2},& \text{if } a > \frac{\lambda}{2}\\ a + \frac{\lambda}{2},& \text{if } -a > \frac{\lambda}{2}\\ 0, & \text{otherwise} \end{cases} $$

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your answer. Could you detail the solution, please? $\endgroup$ Jan 16, 2019 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.