Learning Over-Relaxation Policies for ADMM with Convergence Guarantees

📄 arXiv: 2604.26932v1 📥 PDF

作者: Junan Lin, Paul J. Goulart, Luca Furieri

分类: math.OC, cs.LG

发布日期: 2026-04-29

💡 一句话要点

提出一种基于在线学习的ADMM松弛策略，提升收敛速度并保证收敛性，应用于模型预测控制等场景。

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

关键词: ADMM 在线学习 模型预测控制 凸优化 参数自适应

📋 核心要点

  1. ADMM的性能高度依赖于惩罚和松弛参数的选择，而手动调整这些参数非常耗时且效果不佳。
  2. 论文提出了一种在线学习方法，用于自适应地更新ADMM的松弛参数，从而优化特定问题类的性能。
  3. 实验结果表明，该方法在迭代次数和实际运行时间上均优于基线OSQP，验证了其有效性。

📝 摘要（中文）

交替方向乘子法(ADMM)是一种广泛应用于结构化凸优化的方法，其性能很大程度上取决于惩罚参数和松弛参数的选择。受模型预测控制(MPC)等场景的启发，在这些场景中，人们重复求解具有固定结构和变化参数值的相关优化问题，我们提出学习松弛参数的在线更新，以提高在感兴趣的问题类别上的性能。这种选择在类似OSQP的架构中具有计算吸引力，因为调整松弛参数不会触发与惩罚更新相关的矩阵重构。我们在温和的假设下，建立了具有时变惩罚和松弛参数的ADMM的收敛性保证，并在基准二次规划上表明，由此产生的学习策略在迭代次数和实际运行时间上都优于基线OSQP。

🔬 方法详解

问题定义：ADMM算法的性能受惩罚参数和松弛参数的影响很大。传统方法通常需要手动调整这些参数，这既耗时又难以找到最优值。尤其是在模型预测控制(MPC)等场景中，需要重复求解结构相似但参数不同的优化问题，固定的参数设置难以适应变化的需求。因此，如何自动地、自适应地调整ADMM的参数，以提高收敛速度和整体性能，是一个重要的研究问题。

核心思路：论文的核心思路是利用在线学习的方法，学习一个策略来动态调整ADMM的松弛参数。通过观察ADMM算法在迭代过程中的表现，例如残差的变化，学习一个策略来预测下一步应该使用的松弛参数。这种方法避免了手动调整参数的繁琐过程，并且能够根据问题的具体情况进行自适应调整。由于调整松弛参数不需要像调整惩罚参数那样进行矩阵分解，因此计算成本较低。

技术框架：该方法主要包含以下几个模块：1) ADMM算法：作为优化的基础算法，用于求解优化问题。2) 在线学习策略：使用机器学习模型（例如神经网络或线性模型）来学习松弛参数的更新策略。3) 奖励函数：用于评估ADMM算法在当前松弛参数下的表现，例如收敛速度或残差大小。4) 更新机制：根据奖励函数的结果，更新在线学习策略，使其能够更好地预测合适的松弛参数。整体流程是：首先使用当前的松弛参数运行ADMM算法，然后根据算法的表现计算奖励，接着使用奖励更新在线学习策略，最后使用更新后的策略来选择下一个迭代的松弛参数。

关键创新：该论文的关键创新在于将在线学习与ADMM算法相结合，提出了一种自适应调整松弛参数的方法。与传统的固定参数或手动调整参数的方法相比，该方法能够根据问题的具体情况动态调整参数，从而提高收敛速度和整体性能。此外，该方法还证明了在时变惩罚和松弛参数下的ADMM算法的收敛性，为该方法的应用提供了理论保障。

关键设计：论文的关键设计包括：1) 在线学习策略的选择：可以使用不同的机器学习模型，例如神经网络或线性模型。2) 奖励函数的定义：奖励函数应该能够准确地反映ADMM算法的表现，例如收敛速度或残差大小。3) 更新机制的选择：可以使用不同的在线学习算法，例如梯度下降或强化学习算法。4) 惩罚参数的更新策略：虽然论文主要关注松弛参数的更新，但惩罚参数的选择也会影响ADMM算法的性能。因此，需要设计合适的惩罚参数更新策略。

📊 实验亮点

实验结果表明，该方法在基准二次规划问题上，相较于基线OSQP，在迭代次数和实际运行时间上均有显著提升。具体而言，学习到的松弛策略能够有效地减少ADMM的迭代次数，从而降低计算成本。此外，由于调整松弛参数不需要进行矩阵分解，因此该方法的计算效率更高。实验结果验证了该方法的有效性和实用性。

🎯 应用场景

该研究成果可广泛应用于需要重复求解结构相似优化问题的领域，例如模型预测控制(MPC)、机器人路径规划、图像处理和机器学习等。特别是在MPC中，控制器需要实时求解优化问题，快速的收敛速度至关重要。该方法能够自适应地调整ADMM的参数，提高收敛速度，从而提高控制器的性能和鲁棒性。此外，该方法还可以应用于大规模优化问题，通过自动调整参数，降低人工干预的需求，提高优化效率。

📄 摘要（原文）

The Alternating Direction Method of Multipliers (ADMM) is a widely used method for structured convex optimization, and its practical performance depends strongly on the choice of penalty and relaxation parameters. Motivated by settings such as Model Predictive Control (MPC), where one repeatedly solves related optimization problems with fixed structure and changing parameter values, we propose learning online updates of the relaxation parameter to improve performance on problem classes of interest. This choice is computationally attractive in OSQP-like architectures, since adapting relaxation does not trigger the matrix refactorizations associated with penalty updates. We establish convergence guarantees for ADMM with time-varying penalty and relaxation parameters under mild assumptions, and show on benchmark quadratic programs that the resulting learned policies improve both iteration count and wall-clock time over baseline OSQP.