2024/03/27 by Liang Wu, Wu, Liang, Zhou, Liwei +1 · 1 citation
Computer Science · Engineering · #Advanced Control Systems Optimization #FOS: Electrical engineering #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2403.18235
openalex publication_date 2024/03/27 · openalex created_date 2024/03/29 · openalex updated_date 2026/07/28
Handling possible infeasibility and providing an execution time certificate are two pressing requirements of real-time Model Predictive Control (MPC). To meet these two requirements simultaneously, this paper proposes an ℓ1-penalty soft-constrained MPC formulation that is globally feasible and solvable with an execution time certificate using our proposed algorithm. This paper proves for the first time that ℓ1-penalty soft-constrained MPC problems can be equivalently transformed into a box-constrained quadratic programming (Box-QP) and then our previous execution-time-certified algorithm \citewu2023direct (only limited to Box-QP) can be applied. However, our previous Box-QP algorithm \citewu2023direct, which provides a theoretical execution-time certificate, is conservative in its iteration analysis, thus sacrificing computation efficiency. To this end, this paper proposes a novel LDL^\top decomposition for the first time, to accelerate the computation of Newton step at each iteration. The speedup of our LDL^\top decomposition comes from two-fold: i) exploitation of the fact that the number of inequality constraints is generally larger than the number of variables in condensed MPC formulations, ii) vectorized and parallel implementation based on based on its vector-wise operations, instead of element-wise operations of previous decomposition methods. Numerical experiments demonstrate great speedups of the proposed LDL^\top decomposition (even up to 1000-fold, compared to the standard Choleksky method), which thus helps our solver achieve comparable computation performance to the state-of-the-art solvers such as IPOPT and OSQP. Code is available at \urlhttps://github.com/liangwu2019/L1-penalty-QP.