A Parallel Vector-form $LDL^\top$ Decomposition for Accelerating Execution-time-certified $\ell_1$-penalty Soft-constrained MPC

📄 arXiv: 2403.18235v3 📥 PDF

作者: Liang Wu, Liwei Zhou, Richard D. Braatz

分类: eess.SY, math.OC

发布日期: 2024-03-27 (更新: 2024-08-09)

备注: 11 pages

🔗 代码/项目: GITHUB

💡 一句话要点

提出$ ext{l}_1$惩罚软约束MPC以解决实时控制中的可行性问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 模型预测控制 实时控制 优化算法 计算效率 软约束 二次规划 并行计算

📋 核心要点

  1. 现有的实时模型预测控制（MPC）方法在处理不可行性和提供执行时间证明方面存在挑战。
  2. 本文提出了一种$ ext{l}_1$惩罚软约束MPC的全局可行性形式，并通过$LDL^ op$分解加速计算。
  3. 实验结果显示，所提方法的计算速度相比标准Cholesky方法提升高达1000倍，性能接近最先进的求解器。

📝 摘要（中文）

处理可能的不可行性和提供执行时间证明是实时模型预测控制（MPC）的两个紧迫需求。为同时满足这两个需求，本文提出了一种$ ext{l}_1$惩罚软约束MPC的形式，该形式在全球范围内是可行的，并且可以通过我们提出的算法提供执行时间证明。本文首次证明了$ ext{l}_1$惩罚软约束MPC问题可以等价转化为盒约束二次规划（Box-QP），并可以应用我们之前的执行时间证明算法。然而，之前的Box-QP算法在迭代分析中较为保守，牺牲了计算效率。为此，本文首次提出了一种新的$LDL^ op$分解方法，以加速每次迭代的牛顿步计算。通过利用不等式约束数量通常大于变量数量的事实，以及基于向量操作的并行实现，本文的$LDL^ op$分解在计算效率上取得了显著提升，甚至相比于标准的Cholesky方法快了1000倍，使我们的求解器在计算性能上与IPOPT和OSQP等最先进的求解器相当。

🔬 方法详解

问题定义：本文旨在解决实时模型预测控制（MPC）中的可行性问题及执行时间证明的需求。现有方法在处理不等式约束时效率较低，导致计算时间过长。

核心思路：论文提出的核心思路是将$ ext{l}_1$惩罚软约束MPC问题转化为盒约束二次规划（Box-QP），并利用$LDL^ op$分解加速牛顿步的计算，从而提高求解效率。

技术框架：整体框架包括将MPC问题转化为Box-QP，应用$LDL^ op$分解进行牛顿步计算，并通过并行化和向量化操作提高计算速度。主要模块包括问题转化、分解算法和求解器实现。

关键创新：本文的关键创新在于首次提出$LDL^ op$分解方法，利用不等式约束数量大于变量数量的特性，显著提高了计算效率，与传统的元素级操作方法相比，具有本质区别。

关键设计：在设计中，采用了向量化的并行实现方式，优化了牛顿步的计算过程，确保了在高维情况下的计算稳定性和效率。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的$LDL^ op$分解方法在计算速度上相比于标准Cholesky方法提升高达1000倍，使得求解器的性能与IPOPT和OSQP等最先进的求解器相当，展示了显著的效率提升。

🎯 应用场景

该研究的潜在应用领域包括自动驾驶、机器人控制和工业过程控制等实时系统。通过提高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}.