Solution to a Strongly Convex Non-smooth Minimization Problem involving an L1 Norm

118 Views Asked by At

Let $X \in \mathbb{R}^{n \times d}, w \in \mathbb{R}^d, y \in \{\pm 1\}^{n}, \alpha \in [0,1], \lambda \in \mathbb{R}$. I have an expression that looks as follows

$\frac{1}{2}\|Xw -y \|_{2}^2 + \alpha \|w\|_{2}\|Xw-y\|_{1} + \frac{\lambda}{2}\|w\|_{2}^{2}$

where $\lambda>0$ is sufficiently large so that the entire objective is strongly convex. Note that the second term contains an $L_{1}$-norm term, and that the second term on its own may be non-convex, having local minima both at the origin and in the solution space of $Xw - y$. Furthermore notice that this objective is lower bounded by the first and last terms,

$\frac{1}{2}\|Xw -y \|_{2}^2 + \frac{\lambda}{2}\|w\|_{2}^{2}$

and so the geometry of the first objective is lower bounded by a bowl defined by the second objective. The minimum of the second objective is, straight-forwardly, $w^{*} = (X^{\top}X + \lambda I)^{-1}X^{\top}y$.

However this is not, in general, the minimum of the first objective. Are there tools that will help me find the minimum solution of the first objective in closed form?