1
$\begingroup$

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$.

  • 1
    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.)2012-11-11

2 Answers 2

2

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.

-1

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 :)