Analytical result of cost function

84 Views Asked by At

I have a convex optimization problem with the following cost function: $$f(w) = \frac{1}{2}\beta\cdot(w-w^*)^2 + \alpha|w|$$

where $\alpha,\beta,w^*\in R$ and $w$ is my variable. I have to derivate with respect to $w$ and set the derivative equal to zero.

$$\nabla_w f = \beta w- \beta w^* + \alpha\cdot sgn(w) = 0$$

Now, can you show that from the equation above it the result is:

$$w = sgn(w^*)\text{max}(|w^*| - \frac{\alpha}{\beta}, 0)$$

1

There are 1 best solutions below

2
On BEST ANSWER

I am assuming that $\alpha, \beta >0$. Then $f$ is convex, in fact strictly convex and $f(w) \to \infty $ as $|w| \to \infty$ hence it has a unique minimiser.

$f$ is not differentiable at $w=0$, so setting the derivative to zero is not appropriate. Since $f$ is convex, we have that $w$ is a minimiser iff $0 \in \partial f(w)$, where $\partial f(w)$ is the convex subdifferential.

A quick computation shows $\partial f(w) = \begin{cases} \{ \beta(w-w^*)-\alpha \}, & w < 0\\ [-\beta w^*-\alpha, -\beta w^*+\alpha ], & w=0 \\ \{ \beta(w-w^*)+\alpha \} , & w > 0 \end{cases}$

Let $w$ be the unique minimiser. There are three distinct cases to consider, (1) $0 \in [-\beta w^*-\alpha, -\beta w^*+\alpha ]$, (2) $0 < -\beta w^*-\alpha$ and (3) $-\beta w^*+\alpha < 0$.

Note that (1) is equivalent to $|w^*| \le {\alpha \over \beta}$, (2) is equivalent to $w^* < -{\alpha \over \beta}$ and (3) is equivalent to ${\alpha \over \beta} < w^*$.

In Case (1), we see that $0 \in \partial f(0)$ hence $w=0$.

In Case (2), we either have $0 = \beta(w-w^*)-\alpha$ (if $w<0$) or $0 = \beta(w-w^*)+\alpha$ (if $w>0$). The latter case gives $0 = \beta(w-w^*)+\alpha > \beta w + 2 \alpha$ and hence $w <0$ which would be a contradiction, hence $w= w^*+{\alpha \over \beta}$.

Case (3) is similar to Case (2) and gives $w= w^*-{\alpha \over \beta}$.

Combining gives $w = \begin{cases} w^*+{\alpha \over \beta}, & w^* < -{\alpha \over \beta} \\ 0, & |w^*| \le {\alpha \over \beta} \\ w^*-{\alpha \over \beta}, & {\alpha \over \beta} < w^* \end{cases}$, which is equivalent to the formula in the question.