Exploiting Sparse Structures in Nonlinear Model Predictive Control with Hypergraphs

摘要

This paper proposes a hypergraph formulation for solving MPC problems. The hypergraph approach exploits the sparse structure in the calculation of derivatives. It is therefore computationally more efficient in case of multiple-shooting, collocation and full-discretization methods compared to a dense formulation. Recent advances in realtime optimization rely on automatic differentiation (AD) to compute derivatives. An extensive analysis compares MPC variants with both hypergraph and AD on two benchmark control problems. Even though AD requires a computational overhead to set up the problem structure, solving the nonlinear program at each iteration is fast. The overhead in the hypergraph approach is negligible, and computational effort in the solving phase is inferior but comparable to AD. This observation favors the hypergraph representation for MPC problems with non-static problem structure.