5 ms·

Show HN: OSQP: a new first-order solver for large-scale quadratic programs

39 points by sidereus 9y ago

sidereus 9y ago
arXiv paper: https://arxiv.org/abs/1711.08013 https://arxiv.org/abs/1711.08013 benchmarks: https://github.com/oxfordcontrol/osqp_benchmarks https://github.com/oxfordcontrol/osqp_benchmarks It is the default LP/QP solver in cvxpy 1.0: https://github.com/cvxgrp/cvxpy https://github.com/cvxgrp/cvxpy
LolWolf 9y ago
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,1715-1735.pdf https://users.wpi.edu/~walker/Papers/Walker-Ni,SINUM,V49,171...
- sidereus 9y ago
  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.
  - LolWolf 9y ago
    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.
santaclaus 9y ago
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.
- sidereus 9y ago
  I am happy to compare IPOPT as well. There was a github issue for this: https://github.com/oxfordcontrol/osqp_benchmarks/issues/1 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.
  - wenc 9y ago
    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.
deleted 9y ago
[deleted]
amelius 9y ago
Is it possible to define whether the x's are real numbers or integers?
- LolWolf 9y ago
  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.
- sidereus 9y ago
  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 https://github.com/oxfordcontrol/miosqp However, there are more advanced MIQP algorithms out there such as GUROBI or CPLEX.
  - tmyklebu 9y ago
    Did you test miosqp against standard MIQPs? For example, in QPLIB, there is a handful of convex mixed-integer QPs.
    - sidereus 9y ago
      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.
      - tmyklebu 9y ago
        You could compare number of nodes explored rather than absolute timings to see how inaccuracy solving the relaxations affects branch-and-bound.
tmyklebu 9y ago
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.
- sidereus 9y ago
  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 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)
  - tmyklebu 9y ago
    > 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
nimish 9y ago
Hmm better than mosek?
- sidereus 9y ago
  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.

39 points by sidereus 9y ago

arXiv paper: https://arxiv.org/abs/1711.08013 https://arxiv.org/abs/1711.08013 benchmarks: https://github.com/oxfordcontrol/osqp_benchmarks https://github.com/oxfordcontrol/osqp_benchmarks It is the default LP/QP solver in cvxpy 1.0: https://github.com/cvxgrp/cvxpy https://github.com/cvxgrp/cvxpy

LolWolf 9y ago

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,1715-1735.pdf https://users.wpi.edu/~walker/Papers/Walker-Ni,SINUM,V49,171...

sidereus 9y ago
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.
- LolWolf 9y ago
  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.

santaclaus 9y ago

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.

sidereus 9y ago
I am happy to compare IPOPT as well. There was a github issue for this: https://github.com/oxfordcontrol/osqp_benchmarks/issues/1 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.
- wenc 9y ago
  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.

deleted 9y ago

[deleted]

amelius 9y ago

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

LolWolf 9y ago
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.
sidereus 9y ago
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 https://github.com/oxfordcontrol/miosqp However, there are more advanced MIQP algorithms out there such as GUROBI or CPLEX.
- tmyklebu 9y ago
  Did you test miosqp against standard MIQPs? For example, in QPLIB, there is a handful of convex mixed-integer QPs.
  - sidereus 9y ago
    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.
    - tmyklebu 9y ago
      You could compare number of nodes explored rather than absolute timings to see how inaccuracy solving the relaxations affects branch-and-bound.

tmyklebu 9y ago

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.

sidereus 9y ago
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 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)
- tmyklebu 9y ago
  > 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

nimish 9y ago

Hmm better than mosek?

sidereus 9y ago
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.