(457f) Execution-Time-Certified and Fast MPC Solver

Model Predictive Control (MPC) technology is the core of Advanced Process Control (APC) of process industry. After the MPC design phase, MPC is then deployed into production embedded processors such as Programmable logic controllers (PLC) and Microcontrollers. Deploying a real-time Model Predictive Controller (MPC) on embedded processors could lead to either: 1) control inputs failing to return on time, or 2) control inputs being empty upon return. Clearly, both scenarios will render the process open-loop, thus resulting in safety concerns, particularly in safety-critical process systems. The former arises due to the lack of an execution time certificate, meaning that the worst-case (maximum) execution time of MPC must be theoretically guaranteed to be smaller than the sampling time in closed-loop. If the execution time of the MPC exceeds the sampling time, control inputs fail to return on time.The latter arises from the possible infeasibility of MPC problems, wherein unknown disturbances or modeling errors may drive the plant state into a region where the real-time MPC problem becomes infeasible. In such instances, MPC returns an empty solution. Therefore, providing an execution time certificate and handling possible infeasibility in closed-loop are two pressing requirements of MPC. To handle possible infeasibility, our previous work adopts an $\ell_1$ penalty-based soft-constrained MPC formulation, resulting in non-smooth QPs. To provide an execution time certificate, the non-smooth QPs are innovatively transformed into smooth box-constrained QPs, solved thereafter by our execution-time-certified algorithm. Notably, our execution-time-certified algorithm has only dimension-dependent, simple-calculated, and exact time complexity, making it trivially to certify the execution time of nonlinear MPC (via online linearized scheme such as Real-Time Iteration) or adaptive MPC problems. However, our previous execution-time-certified algorithm is not fast compared to current state-of-the-art MPC solvers. But most current state-of-the-art MPC solvers boast about their computational efficiency in terms of statistical average execution time, often based on extensive numerical experiments. Therefore, their computational advantage is empirical rather than theoretical. Moreover, only when the certified worst-case execution time, instead of the average execution time, is small, MPC can be applied to fast dynamic systems. Based on our previous execution-time-certified algorithm, this work introduces a novel modified algorithm. This modified algorithm has the same iteration complexity as its predecessor but reduces the computational cost per iteration, aligning its time complexity with that of general direct linear system solvers. Therefore, our new algorithm stands out as a game-changer, offering theoretically certified computational efficiency and the ability to provide an execution time certificate and handle possible infeasibility.