Dense BenchMarks Comparison about qpsolvers

[stephane-caron]

I just compared to the latest version using Python 3. As the problem is dense here I bypassed the CSC matrix conversion to make sure the overhead does not come from there (it doesn't).

Baseline (same as above)

• Python 2.7.12
• cvxpy 0.4.10
• ecos 2.0.4

In [7]: %timeit cvxpy_solve_qp(P, q, G, h, solver="ECOS")
100 loops, best of 3: 2.31 ms per loop

Candidate

• Python 3.5.2
• cvxpy 1.0.28
• ecos 2.0.7post1

In [25]: %timeit cvxpy_solve_qp(P, q, G, h, solver="ECOS")
100 loops, best of 3: 5.72 ms per loop

For some reason it's even worse now with the newer version of cvxpy!

The overhead might come from CVXPY rather than ECOS. For instance, calling CVXOPT via CVXPY is super slow:

In [41]: %timeit cvxpy_solve_qp(P_csc, q, G_csc, h, solver="CVXOPT")
100 loops, best of 3: 8.62 ms per loop

@abhishek-pandala It is then likely you are seeing better computation times for ecos because your matlab interface calls it directly (I guess you are not going through CVX).

[stephane-caron]

A small run in Matlab with ecos tells me that if I enable VERBOSE options 'on', the time taken is around 2 ms as reported in your benchmark, and around 0.08 ms if the VERBOSE option is turned off.

Interesting! Thank you for this feedback. I wonder why the Python version is so slow then.

I find it difficult to believe considering the solvers are state-of-the-art and the problem itself is very small (only 3-dimensional).

Feel free to run it on your machine and report the results you get. Using IPython, this is done by running ipython -i dense.py in the examples folder of this repository.

For instance, I'm now on a more powerful machine than at the time I ran the benchmark reported in the README, but the results are consistent with it:

$ ipython -i dense.py
Python 2.7.12 (default, Oct  8 2019, 14:14:10) 
Type "copyright", "credits" or "license" for more information.

IPython 2.4.1 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

Dense solvers 
-------------
quadprog: 10000 loops, best of 3: 21 µs per loop
  cvxopt: 1000 loops, best of 3: 431 µs per loop
 qpoases: 10000 loops, best of 3: 23.5 µs per loop
 
Sparse solvers 
--------------
cvxpy: 100 loops, best of 3: 2.54 ms per loop
 osqp: 10000 loops, best of 3: 27.9 µs per loop
 ecos: 100 loops, best of 3: 2.55 ms per loop

For the record, my version of cvxpy is outdated (0.4.10, while the latest today is 1.0.28).

Is it because you have not turned off the VERBOSE flags or selected appropriate options for each solver

You can check this in cvxpy_.py: the verbose flag in the call to solve() is left to its default value, which should be verbose=False.

I was just wondering if the benchmark test is doing a fair job in comparing all the solvers.

Well this benchmark is totally open for improvements ;) Feel free to open a PR if you see any way in which you can make it more fair or accurate.

[stephane-caron]

OK, so CVXPY was definitely guilty here.

I just pushed a new ecos interface that does the QP to SOCP conversion on its own, and it is much faster. Now ECOS is faster than CVXOPT on the small example:

In [1]: %timeit x = solve_qp(P, q, G, h, solver="quadprog")
10000 loops, best of 3: 21.3 µs per loop

In [2]: %timeit x = solve_qp(P, q, G, h, solver="ecos")
1000 loops, best of 3: 268 µs per loop

In [3]: %timeit x = solve_qp(P, q, G, h, solver="cvxopt")
1000 loops, best of 3: 432 µs per loop

[stephane-caron]

Released v1.1 of the library with the new ECOS interface.

@abhishek-pandala Thank you again for pointing out this issue!