Can $L1$-regularization be applied in general case?

Question

I am not very clear about how far $L1$-regularization can work. For example, let $x\in \mathbb{R}^n$.

\begin{equation}\label{eq:Lasse1} \begin{aligned} &\max_{\mathbf{x}} & & f(\mathbf{x}) + \lambda\|\mathbf{x}\|_1\\ &\text{ s.t.} & & \|\mathbf{x}\|_1 \leq k \\ & & & 0\leq x_i\leq 1, \, i = 1, \ldots, n \end{aligned} \end{equation}

$f(\mathbf{x})$ is any nonconvex polynomial function of $x_i$, $i = 1, \ldots, n$.
$k\leq n$.
Note that it is a maximization problem.

Suppose the optimal solution $\mathbf{x}^*$ exists when $\lambda = 0$.

In this case, can we get a sparsity approximated optimal solution $\mathbf{x}^*_{sp}$?

Note: in my research problem, it looks like that the solution does not change if I add $\lambda \|\cdot\|_1$ or not. I am not sure if it depends on the choice of $\lambda$

Answer 1

The whole idea with $L_1$ regularization is that you add a penalty on the variable in order to encourage sparsity when minimizing some objective. As you are doing it know, you are saying that a larger 1-norm is good. To obtain a regularization, you should subtract the norm when maximizing.

The fact that your solution is unaffected by your addition could be due to several reasons, one being that you are solving a nonconvex problem and thus easily could be stuck in some local minima.