3 ms·

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 hor

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.

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.