Python package for large absolute value optimisation

Question

I have an absolute value optimisation problem

$$\min_x \sum |r-Cx|$$

where $x$ is small around 200 dimension. But $C$ has lots of rows, $C_{30000\times200}$ and $r$ is $30000\times1$. So this will introduce large number of help variables for the absolute value.

Could someone recommend a package in Python that can solve it efficiently? I tried CVXOPT but it took 3 hours to solve a slimmed version of 5000 x 200.

Is it generally quite slow to solve this kind of problem?

Thanks.

---

Turns out that CVXOPT solving is not bad at all! Solving time in GLPK is just 12 seconds!

What has taken long is CVX modelling. I used their integrated modelling module

from cvxopt.modeling import variable, op, dot, matrix

and

y = abs(r-C*x) # quick
objfun = sum(y) # this line takes ages

I suppose the reason the last line is slow is that it is checking convexity.

By converting the problem myself

$$\min \sum v\quad s.t.\,-v\leq r-Cx\leq v$$

it's now good

Answer 1

This problem is easy to convert into a linear programming problem which will have 60,000 constraints and 60,000 (slack variables) + 200 (x variables.) I assume that the $C$ matrix is fully dense, but the problem is otherwise sparse. This should be solvable by a reasonably good LP solver. I'm somewhat surprised that CVXOPT had such trouble with this.

You weren't clear in your question about how exactly you solved this in CVXOPT. Were you using your own LP formulation with the MOSEK solver? GLPK? Were you using the l1() or l1blas() function in CVXOPT (these internally solve the LP formulation)?

In any case, since you're just solving

$ \min \| r-Cx \|_{1} $

and not a more general LP, it really isn't necessary to formulate this problem as an LP. There are many other algorithms for solving this 1-norm minimization problem including iteratively reweighted least squares (IRLS) and subgradient descent methods. Solving the LP formulation is generally not the most efficient approach.