0
$\begingroup$

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?

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

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([' ']);
disp(['Projected Gradient Solution Summary']);
disp(['The Optimal Value Is Given By - ', num2str(objVal)]);
disp(['The Optimal Argument Is Given By - [ ', num2str(vX.'), ' ]']);
disp([' ']);

The full code (Including verification against CVX) can be found in my Mathematics Exchange Q1385984 GitHub Repository.

Remarks:

  • You certainly can transfer this problem into another form (Like Linear Programming Problem) and solve it more efficiently. Yet this will require a solver.
  • Other method based on $ \operatorname{Prox} $ operator or Primal - Dual Method are also applicable and efficient in this case.
$\endgroup$
  • $\begingroup$ It could also be solved using the Chambolle-Pock algorithm or ADMM. $\endgroup$ – littleO Aug 1 '17 at 21:20
  • 1
    $\begingroup$ @littleO, Well yea. Yet I thought it would be easier for the OP to solve it that way. In order to be efficient it is obvious, as written, the Projected Sub Gradient is not the path to take. Still answers the OP Question and easy to understand for anyone who tried Gradient Descent method. Thank You. $\endgroup$ – Royi Aug 1 '17 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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