CVX with Gurobi takes minutes to hours to begin solving

I’m using CVX and Gurobi to solve problems like

cvx_begin
    variable y(n)
    minimize(norm(A * y, 1))
    subject to 
        R * y = b
        y >= 0;
cvx_end

(where n is about 1,000,000)
and I’ve been noticing that there’s a very long gap between the message that says:
Calling Gurobi_4 9.02: 793420 variables, 269131 equality constraints
and when Gurobi actually starts solving the problem.

I debugged the issue and am pretty sure I understand what is going on. This problem results in a relatively large number of simple quadratic constraints of the form y_i^2 - y_j^2 \le 0 (i.e. |y_i| \le |y_j|), which makes total sense.
However, these quadratic constraints appear with the q term set to a large dense vector filled entirely of zeros. CVX appears to be taking advantage of Matlab’s copy-on-write functionality to avoid actually storing all of these vectors separately, but Gurobi’s Matlab wrapper must go through all of these vectors to check for non-zeros. This checking phase takes several minutes. I haven’t timed it, but it easily takes more than 30 minutes in some cases.
Gurobi’s Matlab wrapper allows the q term to be sparse. If I interrupt CVX before it calls Gurobi and replace all of the q terms with the sparse representation, Gurobi starts solving the problem almost immediately.
I know CVX is not designed for very large problems, but this seems like low hanging fruit, so I wanted to suggest the improvement.
Thanks,
Philip

1 Like

With another user we noticed that when you write

norm(x, 1)

then CVX generates a model with “fake” quadratic cones, i.e. t \geq \sqrt{x^2}, to model the absolute value bound t\geq |x|. Since you have a linear problem this is redundant. If instead you write

sum(max(x, -x))

then CVX produces a linear model and the solver will be called with a linear problem which should (hopefull) speed up both the modeling and solution.

I don’t know if that is what you are talking about here, but then I cannot imagine where else quadratic terms could come from in your model.

1 Like

@Michal_Adamaszek that does eliminate the quadratic constraints, which does improve both the modeling and the solution! Thanks! The optimization I’m suggesting could still be helpful, but this fixes the immediate problem.

2 Likes