Hi everyone,
I would like to discuss a feature that could unlock the full potential of the sparse QP solvers in acados, OSQP and Clarabel, in particular when using them inside SQP.
Current situation
OSQP and Clarabel work on sparse matrices in CSC format and exploit sparsity in all their linear algebra. When building these matrices, acados already exploits the stage structure of the OCP, asonly the stage blocks are stored, nothing between them. Within each block, however, all entries are written, including the zeros. In typical MPC problems many of these entries are structurally zero. The cost matrices are often diagonal, and dynamics and constraint matrices frequently contain many zeros. The solvers then factorize and multiply with these zeros as if they were nonzeros.
Proposed feature
acados could allow defining sparsity patterns for the matrices A, B, Q, S, R, C, D (dense by default). In contrast to the one-sided constraint masks, which can change between solves, the patterns would be fixed at solver creation (e.g. as part of the dims), since they determine the memory and the symbolic factorization of the sparse solvers. The interface code of the sparse solvers would then build the CSC matrices only from the entries in the pattern.
- In the QP interface, the user would set the patterns together with the dimensions.
- In the NLP interface, the patterns could come from the sparsity of the CasADi functions.
- The modules between NLP and QP solver (integrator, Hessian approximation, regularization, condensing) would carry the patterns through at solver creation. Some steps are less straightforward (e.g. fill-in in A/B when integrating continuous dynamics, exact Hessians through the integrator, eigenvalue-based regularization like MIRROR/PROJECT), but in the worst case a module can always report a dense block.
Initial results
As we are currently comparing QP solvers, our student @jmiddelberg prototyped OSQP and Clarabel interfaces that detect the pattern from the data . On our humanoid walking MPC ( a QP with N = 9, 13 states, 12 inputs, 32 general constraints per stage), it reduces the median solve time by a factor of about 3:
The data-driven detection works, but each rebuild costs time and the warm start. A pattern defined at creation avoids that.
Questions
- What do you think of such a feature?
- Where would such a pattern live at best - in the dims?
- Would you accept a stepwise contribution, starting with the QP interface and the OSQP/Clarabel interfaces, and extending to the NLP interface later?
Curious to hear your opinions!
Best,
Franek