Asynchronous Push-sum Dual Gradient Algorithm in Distributed Model Predictive Control
作者: Pengbiao Wang, Xuemei Ren, Dongdong Zheng
分类: math.OC, eess.SY
发布日期: 2025-04-26 (更新: 2025-11-05)
💡 一句话要点
提出异步Push-sum对偶梯度算法，解决分布式模型预测控制中的全局约束问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 分布式模型预测控制 异步算法 对偶梯度法 Push-sum算法 全局约束 分布式优化 自适应步长 线性收敛
📋 核心要点
- 针对分布式模型预测控制中全局约束难以处理的问题，现有方法通常需要同步协调，效率较低。
- 论文提出异步Push-sum对偶梯度（APDG）算法，通过对偶分解和异步更新，避免了同步等待，提升了计算效率。
- 理论分析证明了APDG算法的收敛性，并设计了分布式终止准则，数值实验验证了算法的有效性。
📝 摘要（中文）
本文研究了具有有向通信网络中，同时存在局部和全局约束的分布式离散时间线性系统的分布式模型预测控制（DMPC）问题。我们建立了一个优化问题来构建DMPC策略，包括终端成分的设计。为了处理全局约束，我们将原始优化问题转化为其对偶问题。然后，我们提出了一种新颖的异步push-sum对偶梯度（APDG）算法，该算法具有自适应步长方案，以完全异步的分布式方式解决该对偶问题。所提出的算法不需要同步等待和任何形式的协调，从而大大提高了求解效率。我们证明，只要步长不超过设计的上限，APDG算法就能以R-线性速率收敛。此外，我们开发了一种分布式终止准则，以便在其输出解满足指定次优性和全局约束时终止APDG算法，从而避免了无限次迭代。还建立了闭环系统的递归可行性和稳定性。最后，提供了一个数值例子来阐明和验证我们的理论发现。
🔬 方法详解
问题定义：论文旨在解决分布式模型预测控制（DMPC）中，存在全局约束时，传统方法需要同步协调带来的低效率问题。现有方法在处理全局约束时，通常需要中心化的协调机制或者同步迭代，这在通信受限或者计算资源异构的分布式系统中会成为瓶颈。因此，如何设计一种异步的、无需中心协调的DMPC算法，以高效地处理全局约束，是本文要解决的核心问题。
核心思路：论文的核心思路是将原始的DMPC优化问题转化为其对偶问题，然后利用异步的push-sum算法来求解对偶问题。通过对偶分解，可以将全局约束转化为局部约束，从而允许各个子系统独立地进行优化。而异步的push-sum算法则允许各个子系统在不同的时间点进行更新，无需同步等待，从而提高了计算效率。
技术框架：整体框架如下：1) 将原始DMPC问题转化为对偶问题；2) 设计异步push-sum对偶梯度（APDG）算法，包括梯度计算、push-sum更新和自适应步长调整；3) 提出分布式终止准则，用于判断算法何时收敛；4) 分析算法的收敛性、可行性和稳定性。主要模块包括：对偶问题转换模块、APDG算法模块、终止准则模块和稳定性分析模块。
关键创新：论文的关键创新在于提出了异步push-sum对偶梯度（APDG）算法，该算法能够在完全异步的分布式环境下求解DMPC问题，无需同步等待和任何形式的协调。与传统的同步算法相比，APDG算法具有更高的计算效率和更好的鲁棒性。此外，论文还设计了一种分布式终止准则，可以在算法收敛时及时停止迭代，避免了不必要的计算。
关键设计：APDG算法的关键设计包括：1) 自适应步长方案，根据迭代过程动态调整步长，以保证算法的收敛性；2) push-sum更新机制，用于在分布式网络中传递和聚合信息；3) 分布式终止准则，基于局部信息判断全局约束是否满足，以及解的次优性是否达到要求。步长选择需要满足一定的上限，以保证算法的收敛性。终止准则的设计需要平衡计算复杂度和收敛精度。
🖼️ 关键图片
📊 实验亮点
论文通过数值实验验证了APDG算法的有效性。实验结果表明，APDG算法能够以R-线性速率收敛，并且能够在满足全局约束的条件下，获得接近最优的控制策略。与传统的同步算法相比，APDG算法在计算效率方面有显著提升，尤其是在大规模分布式系统中。
🎯 应用场景
该研究成果可应用于智能电网、多机器人协同、交通控制等领域。在这些场景中，系统通常由多个子系统组成，并且存在全局约束。利用该算法，可以实现对这些系统的分布式优化控制，提高系统的整体性能和效率。未来，该算法可以进一步扩展到非线性系统和时变系统，具有广阔的应用前景。
📄 摘要（原文）
This paper studies the distributed model predictive control (DMPC) problem for distributed discrete-time linear systems with both local and global constraints over directed communication networks. We establish an optimization problem to formulate the DMPC policy, including the design of terminal ingredients. To cope with the global constraint, we transform the primal optimization problem into its dual problem. Then, we propose a novel asynchronous push-sum dual gradient (APDG) algorithm with an adaptive step-size scheme to solve this dual problem in a fully asynchronous distributed manner. The proposed algorithm does not require synchronous waiting and any form of coordination, which greatly improves solving efficiency. We prove that the APDG algorithm converges at an R-linear rate as long as the step-size does not exceed the designed upper bound. Furthermore, we develop a distributed termination criterion to terminate the APDG algorithm when its output solution satisfies the specified suboptimality and the global constraint, thereby avoiding an infinite number of iterations. The recursive feasibility and the stability of the closed-loop system are also established. Finally, a numerical example is provided to clarify and validate our theoretical findings.