The state of open-source quadratic programming convex optimizers

I explore here a few open-source optimizers on a relatively simple problem of finding a good convex subset, but with many constraints: 30104 constraints for essentially 174 variables. My particular problem can be easily expressed in the form of a quadratic programming problem.

Java

1. Ojalgo: very difficult to setup properly in the absence of documentation for convex minimization. I suspect it does not work well, as it has a tendency to never finish. Don’t waste your time on this.
2. JOptimizer: much better documentation, but the algorithms seem very primitive, and can’t solve my problem with a relatively large number of variables as it keeps complaining on KKT solution failed. It worked when I truncated the problem to 4 variables.

I could not find much else. It is quite surprising that the state of optimizers is so poor in Java, given that it is one of the most used languages in the enterprise.

Python

1. CVXOPT: very good documentation, and seems robust. It took 4s to solve my problem.
2. OSQP: it works, but it is somewhat slow: 25s to find a solution, while CVXOPT takes 4s for a better result.
3. CVXPY: it is front-end towards existing solvers. It has a very neat documentation. The results depend a lot on the underlying solver, and the approach used.

• The default solver (which I think is OSQP) finds a solution that does not obeys the constraints. If I override the settings the same way as in my direct OSQP test, then it solves correctly but is slower. The CVXPY abstraction layer can significantly slow down the optimization.
• When I create a large array of individual constraints, which is the simplest to code, the performance is not great. The use of a numpy sparse matrix representation to describe all constraints together improves the performance by a factor 50 with the ECOS solver. But it does not impact much the SCS or CVXOPT solvers.
• The default settings for each solver are different. The performance is not strictly comparable and the default settings for OSQP might not be appropriate on my problem

A while ago, I also tried IPOPT, which is a more general convex non-linear solver as it appeared here and there in forums and Google. Unfortunately, I found it a pain to setup on Linux, and after all my efforts, it did not lead to particularly good results.

Octave, Scilab

Scilab solveqp can be used only if the quadratic matrix is positive definite. On my example the matrix is diagonal, and some diagonal elements are 0, it is thus only positive semi-definite. I had to set a small epsilon value on the diagonal to be able to solve with Scilab. It also only works with non sparse matrices. The error reporting is quite bad, it is not obvious at all that solveqp does not work with sparse matrices.

A very similar function, solve_qp, can however work with a sparse matrix to describe the constraints, and it becomes the fastest of all solvers. Note that the scilab documentation is wrong, the format for the input is really the same as the code from Berwin Turlach. The documentation says it computes $$ \min \frac{1}{2} x^t Q x + p^t x,. $$ while the function actually computes $$ \min \frac{1}{2} x^t Q x - p^t x,. $$

I could not get a solution out of Octave qp or quadprog routines.

Summary

Here are the results sorted in ascending solving time:

From Python, the optimizers are of much higher quality. It is not too surprising since they are often written in close collaboration with universities and researchers in the field.

Scilab looks really from another century (a slow Java GUI), and the project is really redundant with Octave. I wish they would both work on the same code base and produce something of higher quality. Clearly, they have lost ground against Python, especially with the IPython/Jupiter notebooks.