Solving a dense QP (variables-(50-1000), constraints-(100-1000))

Hello everyone,

I was solving a dense and sparse variant of a QP for linear MPC. As indicated in the title I am trying to solve a dense QPs that have decision variables and constraints in the ranges specified. The operator splitting method was very fast when I tested for the sparse version of the QP but became slow when the dense QP was solved (large number of iterations to converge). I was using qpOASES till now for MPC application but in comparison to OSQP, it runs faster by an order of magnitude or higher though the solutions are less accurate than the active set solver.
Could there be any reason for this behavior? Is there any means to reduce the run time of OSQP solver for the dense QP? I am new to operator splitting methods and I would like to know what can be tuned in the solver to achieve better performance.

In general you should expect a dense MPC formulation to run slower than a sparse one. The reason is that for the sparse form the matrices you need to factor turn out to be banded, while in the dense case they are dense or lower triangular. The sparse case therefore scales like O(N), whereas the dense case is O(N^3). Exceptions would be cases with very short horizons and/or a huge number of states.

This effect is not really related to OSQP. You would find the same behaviour with an interior point solver, for example.

If you are also getting a much larger number of iterations (rather than just slower iterations), it could be that the conditioning of your matrices in the dense form is unfavourable. This could happen, for example, if your system is unstable and you have a long horizon. In that case you get terms like A^kB appearing (where (A,B) are from your state space system), which will have very large entries for an unstable A and k large.

Yes. You are absolutely right. I am looking at only short horizons where the dense formulations usually perform better and it is independent of the solver. The second point is true and there are elements with large entries. Are there any solver settings or parameters that can be played with to overcome this problem? It will be nice if I can get the solver to converge in fewer iterations for short horizons