Using CVX with Gurobi to solve a typical QP that involved in the objective a quadratic form $$x’ (I + L) , x , ,$$ where I is the identity matrix and L is a graph Laplacian (of order 1500), I noticed speedups (up to factor 4) when I implemented it as a sum of two quadratic forms $$x’ x + x’ L , x ,.$$
The speedup is explained by the fact that Gurovi produced a sparser model in the latter case (Dense cols : 102) than in the former (Dense cols : 380).
Why did Gurobi generated different models in these two cases?
Is there a way to write optimized
CVX code that produces sparser models for a solver?
Great observation, great question. I think you’ve effectively answered it yourself.
CVX presented Gurobi with one quadratic form in the first case, and two in the second. Different models are going to produce different levels of performance—even if they are numerically equivalent, due to differences in their structure.
As for your second question, CVX does not attempt to refactor the nonlinear structure of your model—like, for example, detecting that those two quadratics could be combined. You are doing exactly the right thing here by experimenting with different models to find the one that suits your model the best.
However, please note the cautions provided in the CVX Users Guide in the section entitled Eliminating quadratic forms. Not surprisingly, we would strongly encourage you to find a nice, sparse square root of your I+L matrix yourself so that you can avoid quadratic forms altogether. That is, find a matrix R satisfying R^TR=I+L, and then use the unsquarednorm(R*x) as your objective instead of the quadratic. It’s possible that the fault actually lies with CVX here, not with Gurobi, and specifically how it performs this factorization automatically. It can’t get every case right—but you can…
Please remember as well that CVX is not designed to give you the best performance for your model. That is not its goal. CVX is designed to make it convenient for you to build convex models. Situations like this are simply an unavoidable consequence of the design goals of CVX.
Thanks for the great addition, Erling. Indeed, the diagonal-plus-low-rank case you describe in this paper cannot be detected by CVX’s quad_form command—which is used when you build quadratic forms like x'*Q*x—so it simply cannot take advantage of that structure.
Why / when / for which solvers a conic reformulation of a QP results in optimized code? Are quadratic forms in Gurobi converted to conic form, and if yes, how? That could perhaps answer my questions.
BTW, by converting my QP in conic form, often the performance dropped! It would be great if we could get more information on the underlying reformulations (all the way from CVX code to final model per solver) so as to be able to optimize our code—but I know I may be asking too much
Thanks - however, the refactoring in my question does not involve any special structure (such as low rank) that is exploited, it just subtracts a set of 1’s from the diagonal of a psd matrix and this speeds up the code! This is what I found remarkable and I’d like to understand better.
The solver is irrelevant to the translation process—CVX presents effectively the same problem to every single solver. Experimentation is really your only option here. What trick works for your model might make another model worse. Again, CVX is designed for ease of use, not speed.
One particular point: CVX converts all quadratic forms to conic form. Even if you don’t do it yourself, CVX is going to do it for you, and it might not be the best choice for your model. It is far better for you to do it yourself, experimenting with a few choices to find the one that’s best.
