Sparsity and condensing with "dense API" solvers

[stephane-caron]

Following up to the second point made by @giaf in #7 (comment):

Another issue is common to all solvers that cannot exploit generic sparsity in the problem.
Looking at the interfaces source code, it seems that in case of solvers that can exploit generic sparsity in the problem such as OSQP, clarabel, qpalm, scs for example, the matrix data is passed as an union of ndarray and csc_matrix, and thus the solvers can exploit the sparsity in the problem formulation.
On the other hand, , it seems that in case of solvers that can not exploit generic sparsity in the problem such as quadprog, HPIPM, qpOASES or DAQP for example, all problem data is passed only as ndarray, and there seem to be no pre-processing steps such as condensing: this means that the sparse multi-stage MPC problem is cast as a dense one with a bunch of structural zeros too.
While this could be understandable in benchmarking these solvers on generic QPs, in the special case of MPC QP benchmarking this leads to at least misleading conclusions, as this is not the way such MPC-tailored solvers are designed and expected to be used.
Dense QP solvers are always coupled with condensing routines when solving MPC problems, such that the dynamics equality constraints are exploited to remove the state variable form the problem formulation, leaving only the true degrees of freedom (i.e. the control variables) as the optimization variables.

[stephane-caron]

Thank you for raising this point 👍 In all three types of problem in the test set so far (QUADCMPC* , LIPMWALK* and WHLIPBAL*), problems are already condensed in the sense you mention. That is, state variables have been eliminated and only the control variables $U = [u_0\ u_1\ ...\ u_{N-1}]$ remain.

For LIPMWALK and WHLIPBAL this can be checked in the small qpmpc (prototype) library used to build the QPs, where states $X = [x_1\ ...\ x_N]$ derived from inputs if needed (e.g. state constraints) as some $X = U x_0 + V U + c$.

Thus, so far we don't have problems with state-control decision variables in the test set. If some such problems are added in the future, we could consider adding a condensing preprocessing stage, but it would come with pros and cons. Or we could duplicate all state-control problems in original and condensed forms, and add a subset with only condensed problems... But we are not there yet 😁