In this post I showed how a small non-convex QP could be reformulated as a MIP using KKT conditions plus a special (linear) objective. Will this work in practice? How does this compare performance-wise with global solvers? Let’s see if we can get a feeling for this.
Duplicating the problem
One easy way to make the small test problem bigger is to duplicate the problem:
|Objective||\(c'x_1 + x'_1 Q x_1\)||\(+c'x_2 + x'_2 Q x_2\)||\(\cdots\)||\(+c'x_K + x'_K Q x_K\)|
|Constraints||\(A x_1 \le b\)|
\(\ell \le x_1 \le u\)
|\(A x_2 \le b\)|
\(\ell \le x_2 \le u\)
|\(A x_K \le b\)|
\(\ell \le x_K \le u\)
Basically we need to add an index K to the variables \(x_i\), and to the constraints. Finally we add a summation to the objective. The new model looks like:
For the KKT model we can do something similar.
Here are some results with K=5 and K=10. I stopped after 1000 seconds (if not proven optimal by then, I report the gap).
Note: The global QP solver GloMiQo behaves the same as Antigone.
At least for this model the MIP formulation is doing very well. The Cplex MIP solver beats the Cplex global QP solver by a large margin!
Yalmip has reported similar results produced by its KKTQP method.