# L1 Minimization with Non-negativity constraints.

Is there any fast approach to solving l1 minimization problem with non-negativity contraints? The problem is to minimize $|x_1|+|x_2|+...+|x_n|_{l_1}$ subject to $Ax = b$ and $Ax \geq 0$.

-
You really have the same matrix $A$ appearing in the equality constraints and the inequality constraints? – littleO Nov 10 '12 at 11:45
Are $x_1,\ldots,x_n$ the components of $x$? So they are real numbers? If so, then $x_1 + \cdots + x_n$ is a scalar, and what you are calling the $\ell_1$ norm is just the absolute value of a scalar. – littleO Nov 10 '12 at 11:47
To elaborate on littleO's comment, the $L_1$ norm of the vector $x = (x_1,x_2,\ldots,x_n)$ would be $\lvert x_1\rvert + \lvert x_2\rvert + \cdots + \lvert x_n\rvert$, not $\lvert x_1+x_2+\cdots+x_n\rvert$. If that's what you mean, you should write that. – Rahul Nov 10 '12 at 23:10
@littleO, the $x_i$ is components of $x$. – Strin Nov 11 '12 at 1:48
It annoys me unreasonably when the OP ignores the very first comment. So I'll repeat: Do you really mean "$Ax=b$ and $Ax\ge0$"? Or do you mean "$Ax=b$ and $x\ge0$"? (Of course, if $x\ge0$ then the $L_1$ norm is simply $x_1+x_2+\cdots+x_n = 1^Tx$. But please please answer the question first.) – Rahul Nov 11 '12 at 2:23

You can convert problems like this into linear programs by introducing variables $t_i, i = 1,\ldots,n$ that satisfy $$-t_i \leq x_i \leq t_i$$ for $i = 1,\ldots, n$. (Note that this is equivalent to requiring $t_i \geq | x_i| \, \forall \, i$.)

Just minimize $t_1 + \cdots + t_n$ subject to these constraints, and to whatever other constraints you have on $x$. Efficient methods are available to solve linear programs.

This trick (which is standard) is described in chapter 6 ("Approximation and fitting") of Vandenberghe's 236b notes. See slide 6-3.

-

Indeed, this can be solved as a quadratic program by any QP solver (I do this routinely).

The problem is (if I understood correctly):

$min||Ax-b||^2_2+c||x||_1$ such that $x>=0$

In your case $c=1$ but in general this is a regularization parameter (for more information read about LASSO or L1-regularized least squares).

Start with the fact that $min||Ax-b||^2_2$ such that $x>=0$ is clearly a QP since:

$||Ax-b||^2_2=x^TA^TAx-2(b^TA)^Tx+b^Tb$

Now the additional constraint won't change much, and the problem is still a QP:

$||Ax-b||^2_2+c||x||_1=x^TA^TAx-2(b^TA)^Tx+b^Tb+c\underline{1}^Tx$

I hope I got all those nasty transpose right :)

-