Python package for large absolute value optimisation - Computational Science Stack Exchange most recent 30 from scicomp.stackexchange.com 2022-01-27T02:26:05Z https://scicomp.stackexchange.com/feeds/question/20692 https://creativecommons.org/licenses/by-sa/4.0/rdf https://scicomp.stackexchange.com/q/20692 2 Python package for large absolute value optimisation jf328 https://scicomp.stackexchange.com/users/14305 2015-09-10T15:56:36Z 2015-09-11T08:12:38Z <p>I have an absolute value optimisation problem</p> <p>$$\min_x \sum |r-Cx|$$</p> <p>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.</p> <p>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.</p> <p>Is it generally quite slow to solve this kind of problem?</p> <p>Thanks.</p> <hr> <p>Turns out that CVXOPT solving is not bad at all! Solving time in GLPK is just 12 seconds! </p> <p>What has taken long is CVX modelling. I used their integrated modelling module</p> <pre><code>from cvxopt.modeling import variable, op, dot, matrix </code></pre> <p>and </p> <pre><code>y = abs(r-C*x) # quick objfun = sum(y) # this line takes ages </code></pre> <p>I suppose the reason the last line is slow is that it is checking convexity.</p> <p>By converting the problem myself</p> <p>$$\min \sum v\quad s.t.\,-v\leq r-Cx\leq v$$</p> <p>it's now good</p> https://scicomp.stackexchange.com/questions/20692/-/20695#20695 3 Answer by Brian Borchers for Python package for large absolute value optimisation Brian Borchers https://scicomp.stackexchange.com/users/2150 2015-09-10T16:21:26Z 2015-09-10T17:23:23Z <p>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.</p> <p>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)?</p> <p>In any case, since you're just solving </p> <p>$\min \| r-Cx \|_{1}$</p> <p>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. </p>