Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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
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.) –  Rahul Nov 11 '12 at 2:23

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.