I'm curious why Gurobi uses Cholesky decomposition to solve the linear system in the barrier method, instead of Gaussian elimination.
In the Appendix C of the book Convex Optimization., Boyd, S., & Vandenberghe, L. (2004), the authors say that Gaussian elimination can take advantage of the matrix structure so it has much lower complexity than the Cholesky decomposition in some cases.
So can't Gurobi be much faster (or achieve similar performance in the worst case) by using Gaussian elimination? What is the bottleneck/difficulty of doing it?
Please sign in to leave a comment.