0

I am trying to solve the optimization problem

$$\underset{x}{\arg\min}\left\{||x||_2+\frac{\beta}{2}||x-v||_2^2\right\}$$

where $\beta>0$ and $v$ is some fixed vector.

$\textbf{My approach so far:}$

I know that $||x||_2$ is not differentiable at $x=0$, so assuming that $x\neq 0$, then from nulling the gradient I get

$$\frac{x}{||x||_2}+\beta(x-v)=0$$

I seem to have problems with the $x$ and $||x||_2$ terms. Is there a way to combine those two terms? Or is there another approach to solving this? I know the solution can be obtained by using shrinkage, but I don't see how. Any hints would be highly appreciated.

Thanks in advance!

James
  • 434
  • We should probably know what $\beta$ and what $v$ are – FShrike Aug 17 '21 at 09:24
  • 1
    Sorry, I forgot about that. I have added what $\beta$ and $v$ are. The optimization problem is related to proximal operators if I'm not mistaken. – James Aug 17 '21 at 09:31
  • 1
    @James From your last equality you see that any solution of the stationarity system must satisfy $|x-v| =\frac{1}{\beta}$ and that it must be a multiple of $v$. – PierreCarre Aug 17 '21 at 10:53
  • @PierreCarre Thank you for the hints! I have managed to derive those observations now. But I don't see how I can combine these two to obtain my solution. – James Aug 17 '21 at 11:03
  • 1
    @James Just make a sketch of what happens in 2D... The first condition places the solution in a circunference and the second condition reduces the possibilities to two points on that circunference. Depending on the value of $\beta, v$ the minimiser may be $x = 0$, which is not a solution of the system. – PierreCarre Aug 17 '21 at 11:09

1 Answers1

2

Just a hint... From your last equality you see that

  1. $\|v-x\|_2 = \frac{1}{\beta}$.
  2. Since $(\frac{1}{\|x\|_2}+\beta) x = \beta v$, you also see that $x$ has the same direction as $v$, say $x = a(x) v$.

If you substitute (2) in the stationarity condition, you'll find a solution when $\beta > \frac{1}{\|v\|}$, which will be $x = \left(1-\frac{1}{\beta \|v\|}\right) v$.

In the picture below you can see (with $\beta = 0.8$ and $v = (2,2)$) the contours of the objective function (black), the circumference $\|x-v\|=\frac{1}{\beta}$ (red) and the stationary point.enter image description here

However, if $beta$ is too low (e.g. $\beta = 0.2$), you will can something like

enter image description here

where the minimum will not correspond to a critical point, but rather to $x=0$.

PierreCarre
  • 20,974
  • 1
  • 18
  • 34