Barrier algorithm; what kind of matrices can it handle the best (sparse or dense, large or small problems)?
Hi,
I have some general questions about the barrier algoritm that Gurobi uses to solve a QP.
For which type of problems does the algorithm work the best? Largescale systems or smallscale systems?
Do dense matrices work the best for the barrier algorithm or sparse matrices? What are the causes of that? Or works a combination better?
For example small, the fastest for small, dense problems and large, sparse problems.
Does the algorithm need a lot of iterations to converge or less iterations, but each iteration is more expensive, in general?
I found a Powerpoint about Gurobi and this was the only thing I found of the above subject, but I don't exactly know what they mean with:
Dozens of expensive iterations: Why many iterations and expensive at both time
Much denser matrices: Why denser matrices? I thought Gurobi could handle sparse matrices better?
Lots of opportunities to exploit parallelism: What is parallelism?

Hello Soufyan:
these are very general questions that can be answered by learning about the interiorpoint methods (or barrier algorithms) from a course, so maybe the support forum is not quite the best place for it. I will try to answer some though.
>> For example small, the fastest for small, dense problems and large, sparse problems.
Generally, small sparse problems will be faster than large dense ones.
>> Does the algorithm need a lot of iterations to converge or less iterations, but each iteration is more expensive, in general?
As compared to simplex, where the method would generally require lots of relatively inexpensive iterations, the barrier will require much fewer iteration but each one of those is much more expensive.
>> Dozens of expensive iterations: Why many iterations and expensive at both time
See above.
>> Much denser matrices: Why denser matrices? I thought Gurobi could handle sparse matrices better?
This probably refers to the internal structures in the solver, meaning that it will operate on denser (intermediate) matrices at every iteration.
>> Lots of opportunities to exploit parallelism: What is parallelism?
Parallelism refers to using several CPU cores.
Hope this helps.

Hi,
As compared to simplex, where the method would generally require lots of relatively inexpensive iterations, the barrier will require much fewer iteration but each one of those is much more expensive.
And compared to Matlab's interiorpointconvex? Gurobi and quadprog gave the same objective function value, but what is the relation between the convergence and cost of iterations? And with GPAD?
This probably refers to the internal structures in the solver, meaning that it will operate on denser (intermediate) matrices at every iteration.
Were the internal structures of the solver not sparse, which leads to the fact that Gurobi could handle sparse matrices very good in comparison to for example Matlab's quadprog. The computation times of quadprog is for a sparse QP problem much higher compared to solving a sparse QP problem in Gurobi.
Please sign in to leave a comment.
Comments
2 comments