How to obtain the minimum point of the sum of a quadratic form and a L1 norm function?

57 Views Asked by At

Given $u, \gamma \in \mathbb{R}^n$ and $W \in \mathbb{R}^{n,n}$ is a positive definite matrix. The objective function is the sum of a quadratic form and a L1 norm: $f(\gamma) = (\gamma-u)'W(\gamma-u) + \lambda\|\gamma\|_1$, where $(\cdot)'$ is the transpose of a matrix, the L1 norm is $\|\gamma\|_1 = \sum_{i=1}^n |\gamma_i|$ and $\lambda \in \mathbb{R}$ is a known scalar.

My question is how to obtain the point $\gamma^{*}$ that $f(\gamma^{*})$ takes the minimum value. Since the second part $\|\gamma\|_1$ is non-differentiable, I believe $\gamma^{*}(u)$ is a stepwise function.

If $W$ is an identity matrix, then we can have $\gamma^{*}_i(u) = \max\{0, u_i - \frac{\lambda}{2}\} + \min\{0, u_i + \frac{\lambda}{2}\}$. How about the expression of $\gamma^{*}(u)$ in the case where $W$ is no longer an identity matrix?