分布式优化与博弈的统一系统理论框架

《IEEE Transactions on Automatic Control》：A Unifying System Theory Framework for Distributed Optimization and Games

分布式优化与博弈算法的系统设计框架，通过奇异摄动理论将集中式方法分解为优化模块和共识模块，结合-共识机制实现全局信息同步，提出约束耦合问题的线性收敛分布式方案。

　　

摘要：

本文提出了一种系统的方法论框架，用于设计和分析网络上的分布式算法，以解决优化和博弈问题。我们从集中式方法出发，确定了一个涉及所有决策变量的聚合函数（例如全局成本梯度或约束），并引入了一种基于分布式共识的方案，以渐进地逼近每个代理无法获得的信息。然后，我们详细阐述了将这两个关键组成部分（即优化导向的方法和共识导向的方法）结合起来的正确方法。其核心直觉是将这种交互关系视为一个奇异扰动系统。我们依靠这种解释来提供充分条件，以确保这些组成部分能够成功连接成一个具有集中式算法收敛保证的分布式方案。最后，我们通过开发一种新的分布式方案来展示我们方法的潜力，该方案适用于具有线性收敛率的约束耦合问题。

引言

近年来，人们越来越关注将集中式（或并行）架构转变为分布式架构，因为分布式算法具有许多优势：例如，保护隐私并避免单点故障；见图1。在分布式优化中，代理们合作以最小化共同的性能指标；而在网络博弈的背景下，它们相互竞争以最小化各自的成本。有关现有框架、算法和应用场景的全面概述，请参阅最近关于分布式优化[1]、[2]、[3]、[4]、[5]、[6]、[7]、[8]以及聚合博弈[9]、[10]、[11]的综述。在这些场景中使用系统理论工具是一个最近的成功趋势[12]。这种方法的优势已在分布式优化[13]、[14]、[15]、[16]和博弈[17]、[18]中得到验证。文献[19]（另见[20]）提出了一种控制论方法，将分布式优化算法系统地分解为集中式优化方法和二阶共识估计器。其他基于系统理论的系统分解方法在[21]和[22]中也有提出，其中还考虑了时变图。文献[23]首次尝试基于非线性观测理论对分布式连续时间优化方案进行系统设计。我们的核心思想是形式化大多数分布式算法的直觉，这些算法试图通过结合近似优化部分和共识方案来达成对全局信息的共识。在优化[24]、[25]、[26]、[27]、[28]和博弈理论[30]、[31]、[32]、[33]、[34]中，已经针对特定的分布式场景从奇异扰动的角度进行了研究。奇异扰动（或时间尺度分离）是分析由慢速子系统与快速子系统相互连接的系统的强大工具[35]、[36]。为了在我们的方案中处理对全局信息的一致性问题，我们采用了-共识[37]、[38]的形式主义，用于建模具有局部量的代理们旨在达成共识的问题。