Darn, no benchmark against Ipopt, which in my experience still gives the best black-box performance on large, sparse quadratic problems. In my experience the commercial solvers (Gurobi, Mosek) are actually quite slow.

I am happy to compare IPOPT as well. There was a github issue for this: https://github.com/oxfordcontrol/osqp_benchmarks/issues/1

As I said there, the current IPOPT Python interfaces do not report the timings. If you are aware of any fair way to time it from Python, I would be happy to add it. In my opinion using the Python "time" module can cause lags due to the Python interpreter.

If you can write your models in AMPL or GAMS or some modeling language, you would be able to test IPOPT's raw speed.

I used IPOPT from AMPL for years and it is a formidable solver for general large-sparse NLPs. It would be nice to see benchmarks against it.

arXiv paper: https://arxiv.org/abs/1711.08013

benchmarks: https://github.com/oxfordcontrol/osqp_benchmarks

It is the default LP/QP solver in cvxpy 1.0: https://github.com/cvxgrp/cvxpy

This is pretty cool; Boyd had mentioned to me something about there being a good method for solving QPs that was nicer than the usual SOCP reduction (that's horrible and pretty slow in the general case). I think this was the case he was referring to.

Anyways, the results here are quite impressive; I wonder what would happen if Anderson acceleration[0] was used to speed this up further? IIRC, someone from the lab was doing some work on that, but for general splitting-cone methods rather than just QP solving.

---

[0] C.f. https://users.wpi.edu/~walker/Papers/Walker-Ni,SINUM,V49,171...

Yes! Cvxpy 1.0 now detects QPs and avoids the slow SOCP reduction. Also, it exploits OSQP to perform factorization caching and warm starting. If you solve parametric QPs in a sequence (e.g., lasso pareto frontier) the speedups are even bigger.

It would be very interesting to try the Anderson acceleration for QPs! We tried other line search methods but they did not bring consistent improvements for different problems. I think Anderson acceleration could be more useful (also from the theoretical point of view).

Could you put me in touch with the person working on that in the lab? I would be happy to try it. We have a prototype Python implementation that could be used for that.

Yay! That's awesome, I'm glad (this was a bit of a problem with last year's EE364A exam, actually, since the solver for a problem was too slow, so we decided to not include it). The benchmarks are quite impressive as well!

Anyways, one of the TAs for 364 was working on it---I believe under Boyd, but unsure; I can ask if it was specifically SOCPs, which is what I recall---and I'm also applying it to certain other large-scale (but non-convex) cases. I'll ask him and get back to you on that. My profile has my email, if you'd like to not dox yourself as well, and I can put you two in touch.

What sort of QP problems are you hoping to solve using OSQP? When I tried OSQP on stock LP problems (i.e. the P = 0 special case; instances were afiro, adlittle, fit1p, dfl001, maros-r7, wood1p), I didn't get encouraging results. Apart from afiro, I got a lot of pretty wrong answers after relatively long periods of computation.

Which version of OSQP did you try for? 0.2 has improved a lot compared to previous versions (much better convergence behavior with adaptive rho).

Even though OSQP can solve also LPs, it is optimized to solve QPs. You can find some benchmarks here: https://github.com/oxfordcontrol/osqp_benchmarks They include:

- Randomly generated QPs from several classes such as control, portfolio, lasso, svm, Huber fitting

- The hard QP problems from the Maros-Meszaros test class (the reference benchmark testset for convex QPs)

> Which version of OSQP did you try for? 0.2 has improved a lot compared to previous versions (much better convergence behavior with adaptive rho).

I did a 'git clone' of your repository this morning; I have 0edd758. (I learned about your project this morning.)

> Even though OSQP can solve also LPs, it is optimized to solve QPs.

I understand that, but (apart from dfl001) these aren't especially difficult LPs.

> - Randomly generated QPs from several classes such as control, portfolio, lasso, svm, Huber fitting

OK, but you wouldn't normally use a general-purpose IPM like Gurobi or Mosek for lasso or SVM problems, would you?

Separately, why randomly-generated QPs? Randomly-generated LPs tend to be very easy to solve, and I'd imagine a convex quadratic term in the objective only makes it easier. For SVMs, there's a bunch of available, fairly standard data associated with Chih-Jen Lin's libsvm.

> - The hard QP problems from the Maros-Meszaros test class (the reference benchmark testset for convex QPs)

How did you convert the Maros-Meszaros problems? The results output by your solver don't line up with the numbers in "00README.QP" on Maros's site. For example, Maros has:

  aug3d       1000    3873    6546    2673        0    5.5406773e+02
  aug3dc      1000    3873    6546    3873        0    7.7126244e+02
  aug3dcqp    1000    3873    6546    3873        0    9.9336215e+02
  aug3dqp     1000    3873    6546    2673        0    6.7523767e+02

while you get:

  13092,25,4873,3873,AUG3D,-782.432274207,0.012742196,OSQP_polish,optimal,1
  14292,25,4873,3873,AUG3DC,-1165.23756131,0.012990161,OSQP_polish,optimal,1
  14292,75,4873,3873,AUG3DCQP,-943.137853475,0.023050472,OSQP_polish,optimal,1
  13092,75,4873,3873,AUG3DQP,-661.262328725,0.023125477,OSQP_polish,optimal,1

When polishing succeeds, you get a different objective value from Maros (in this case by about 1e4, so a relative 1e-2):

  aug2d      10000   20200   40000   19800        0    1.6874118e+06
  aug2dc     10000   20200   40000   20200        0    1.8183681e+06
  aug2dcqp   10000   20200   40000   20200        0    6.4981348e+06
  aug2dqp    10000   20200   40000   19800        0    6.2370121e+06

  80000,25,30200,20200,AUG2D,1677511.7529,0.074053448,OSQP_polish,optimal,1
  80400,25,30200,20200,AUG2DC,1808268.06557,0.073366168,OSQP_polish,optimal,1
  80400,775,30200,20200,AUG2DCQP,6488034.73924,0.866898539,OSQP_polish,optimal,1
  80000,775,30200,20200,AUG2DQP,6227112.02536,0.8685775,OSQP_polish,optimal,1

We compared our OSQP solver to other general-purpose solvers. That's why we chose GUROBI and Mosek. There are also examples of control problems for which it is possible to design very efficient tailored methods. However our point is not to compare our solver to specific methods for certain classes (like libsvm).

In the benchmarks we are comparing examples with randomly generated data because we were interested in ~1400 problems in a range from 100 to 10 million nonzeros. The examples are not just random QPs, but data are generated in a reasonable manner and they have the same structure as problems people would actually solve in practice. In the arXiv paper we described in detail how we generated and checked optimality for the examples.

As mentioned in the README of the repository that you checked out (https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems

If you know better ways to convert the Maros problems (or other QP/LP benchmarks) to mat files or other formats compatible with Python, please let me know. I would be happy to try them.

> We compared our OSQP solver to other general-purpose solvers. That's why we chose GUROBI and Mosek.

Your computational results don't support calling OSQP general-purpose. OSQP does okay on the easy problems you randomly generate, but this doesn't seem to generalise---OSQP gives results on a bunch of the Maros-Meszaros problems that markedly disagree with previously published work.

> However our point is not to compare our solver to specific methods for certain classes (like libsvm).

You may not want to compare against libsvm's solver (though I imagine you look pretty good on the problems you're generating) but there is also a lot of data available at the libsvm webpage. This data might serve as a more representative SVM testbed than the random easy instances you're creating.

> In the benchmarks we are comparing examples with randomly generated data because we were interested in ~1400 problems in a range from 100 to 10 million nonzeros. The examples are not just random QPs, but data are generated in a reasonable manner and they have the same structure as problems people would actually solve in practice.

The "random QPs" and "random equality QPs" do seem to be "just random QPs."

I get cond(A^T A) ranging between 1.3 to 1.7 with your Lasso problem generator. These instances are going to be incredibly easy to solve, even with very naive algorithms. (Separately, why not eliminate the 'y' variable from your formulation? You get a formulation that's about 100 times smaller, and you should see a corresponding speedup.)

> In the arXiv paper we described in detail how we generated and checked optimality for the examples.

Yes, you check for a bunch of residuals' infinity-norms being smaller than 1e-3. But you get results that differ markedly from the other solvers' results. To me, that raises the question of whether the 1e-3 test is appropriate.

> As mentioned in the README of the repository that you checked out (https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems > > If you know better ways to convert the Maros problems (or other QP/LP benchmarks) to mat files or other formats compatible with Python, please let me know. I would be happy to try them.

Well, QPS is a punch-card style input format like MPS. Like MPS, I imagine you can write a parser for it in a couple of highly unfulfilling hours.

Is it possible to define whether the x's are real numbers or integers?

OSQP solves only continuous QPs. For integer variables you need an MIQP solver.

We wrote a Python branch-and-bound wrapper around OSQP to solve MIQPs: https://github.com/oxfordcontrol/miosqp

However, there are more advanced MIQP algorithms out there such as GUROBI or CPLEX.

Did you test miosqp against standard MIQPs? For example, in QPLIB, there is a handful of convex mixed-integer QPs.

Haven't tried the MIQP extension against the QPLIB yet. It is just a prototype and it is written in Python. We first need to implement it in C to compare the timings.

You could compare number of nodes explored rather than absolute timings to see how inaccuracy solving the relaxations affects branch-and-bound.

If the variable is constrained to be an integer, the problem becomes NP-hard-as-hell (in both a complexity sense and an approximation sense), sadly. It also stops being convex, so splitting-cone methods can't be directly applied and the solution here goes out the window.

In general, you assume the variables here to be real-valued vectors.

Hmm better than mosek?

For QPs it looks like. Mosek works really well for SDPs. However, it converts QPs to SOCPs before solving them. This slows down a lot the timings.