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$.
L1 Minimization with Non-negativity constraints.
-
1It 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.) – 2012-11-11
2 Answers
You can convert problems like this into linear programs by introducing variables $t_i, i = 1,\ldots,n$ that satisfy \begin{equation} -t_i \leq x_i \leq t_i \end{equation} 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 :)