4 ms·

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 O

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
- sidereus 9y ago
  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 https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems 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.
  - tmyklebu 9y ago
    > 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 https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems 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.

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

sidereus 9y ago
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 https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems 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.
- tmyklebu 9y ago
  > 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 https://github.com/oxfordcontrol/osqp_benchmarks) we used the conversion scripts from here: https://github.com/YimingYAN/QP-Test-Problems 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.