A Parallel Vector-form LDL^ Decomposition for Accelerating Execution-time-certified _1-penalty Soft-constrained MPC

Code

• github.com/liangwu2019/l1-penalty-qp
  OfficialIn papernone★ 1

Abstract

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 wu2023direct (only limited to Box-QP) can be applied. However, our previous Box-QP algorithm 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: 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^ 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 https://github.com/liangwu2019/L1-penalty-QP.

Tasks

Reproductions