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