Time-Certified and Efficient NMPC via Koopman Operator

Abstract

Certifying and accelerating execution times of nonlinear model predictive control (NMPC) implementations are two core requirements. Execution-time certificate guarantees that the NMPC controller returns a solution before the next sampling time, and achieving faster worst-case and average execution times further enables its use in a wider set of applications. However, NMPC produces a nonlinear program (NLP) for which it is challenging to derive its execution time certificates. Our previous works, \citep{wu2025direct,wu2025time} provide data-independent execution time certificates (certified number of iterations) for box-constrained quadratic programs (BoxQP). To apply the time-certified BoxQP algorithm \citep{wu2025time} for state-input constrained NMPC, this paper i) learns a linear model via Koopman operator; ii) proposes a dynamic-relaxation construction approach yields a structured BoxQP rather than a general QP; iii) exploits the structure of BoxQP, where the dimension of the linear system solved in each iteration is reduced from $5N(n_u+n_x)$ to $Nn_u$ (where $n_u, n_x, N$ denote the number of inputs, states, and length of prediction horizon), yielding substantial speedups (when $n_x \gg n_u$, as in PDE control).