A Parallel Vector-form $LDL^\top$ Decomposition for Accelerating Execution-time-certified $\ell_1$-penalty Soft-constrained MPC
<|reference_start|>A Parallel Vector-form $LDL^\top$ Decomposition for Accelerating Execution-time-certified $\ell_1$-penalty Soft-constrained MPC: 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 $\ell_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 $\ell_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 \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^\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: \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^\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 \url{https://github.com/liangwu2019/L1-penalty-QP}.<|reference_end|>
@article{wu2024a,
    title={A Parallel Vector-form $LDL^\top$ Decomposition for Accelerating
  Execution-time-certified $\ell_1$-penalty Soft-constrained MPC},
    author={Liang Wu, Liwei Zhou, Richard D. Braatz},
    journal={arXiv preprint arXiv:2403.18235},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.18235},
    primaryClass={eess.SY cs.SY math.OC}
}