# Least Absolute Deviation (LAD) with Non Negative Constraint

I would like to solve the following:

\begin{align} \text{minimize} & \quad & \left\| A x - b \right\|_{1} \\ \text{subject to} & \quad & x \succeq 0 \end{align}

What kind of toolkit should we use to solve this problem?
I know we can turn this into a linear programming problem. Can that be done by just adding another constraint?

• if you don't want to make the transformation yourself. try modeling toolkits like cvx for matlab. – user251257 Aug 5 '15 at 22:30
• You may want to checkout a similar question (answered) here math.stackexchange.com/q/1309671/168758 – dohmatob Aug 6 '15 at 6:44

The problem is given by:

\begin{align} \text{minimize} & \quad & \left\| A x - b \right\|_{1} \\ \text{subject to} & \quad & x \succeq 0 \end{align}

The easiest (Yet one of the slowest) methods to solve this would be using the Projected Sub Gradient Method.

The Gradient of $\left\| A x - b \right\|_{1}$ is given by ${A}^{T} \operatorname{sgn} \left( A x - b \right)$.
The projection onto the non negative orthant is given by ${x}_{+}$.

Here is the code:

vX = zeros([numCols, 1]);

for ii = 1:numIterations
vX = vX - ((stepSize / sqrt(ii)) * mA.' * sign(mA * vX - vB));
vX = max(vX, 0);
end

objVal = norm(mA * vX - vB, 1);

disp([' ']);

• Other method based on $\operatorname{Prox}$ operator or Primal - Dual Method are also applicable and efficient in this case.