Papers › A Parallel Vector-form LDL^⊤ Decomposition for Accelerating Execution-time-certified...
A Parallel Vector-form LDL^⊤ Decomposition for Accelerating Execution-time-certified ℓ₁-penalty Soft-constrained MPC
Liang Wu, Liwei Zhou, Richard D. Braatz
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 ℓ₁-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 ℓ₁-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 \cite{wu2023direct} (only limited to Box-QP) can be applied. However, our previous Box-QP algorithm \cite{wu2023direct}, 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^⊤ decomposition for the first time, to accelerate the computation of Newton step at each iteration. The speedup of our LDL^⊤ decomposition comes from two-fold: \textit{i)} exploitation of the fact that the number of inequality constraints is generally larger than the number of variables in condensed MPC formulations, \textit{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^⊤ 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 \url{https://github.com/liangwu2019/L1-penalty-QP}.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections