时延情形下分布式Push—sum次梯度优化算法的研究

李德权++张晓倩

摘 要：针对多个体系统在个体间进行信息交换时发生接收信息滞后，存在通信时延，影响优化算法的收敛速度的问题，提出一种时延情形下的分布式Push-sum次梯度优化算法，该方法在权矩阵不具有正对角线元素时仍适用，并应用系统扩维的方法将有时延优化问题转化为无时延优化问题。在时延和次梯度有界且有向切换网络周期强连通的条件下，证明了所提出的分布式Push-sum次梯度优化算法的收敛性。研究表明：存在通信时延时的算法收敛速度比无时延时的收敛速度要慢，并具有较大的收敛误差。最后，通过数值仿真验证了研究的结论。

关键词：时延；Push-sum算法；次梯度；分布式优化

中图分类号：TP13 文献标志码：A 文章编号：1672-1098（2015）02-0006-07

（School of Science， Anhui University of Science and Technology， Huainan Anhui 232001， China.）

Abstract：The distributed optimization problem in directed switching networks with time-varying delay communication among the agents was studied. Due to delay may happen when agents communicate with each other in the multi-agent system， this paper proposes a distributed Push-sum subgradient optimization algorithm in the context of communication delays， which will affect the convergence rate of optimization algorithm. Then based on state augmentation method， the analysis is carried out by reducing the optimization problem with delays to a problem without delays and this algorithm does not require the diagonal elements of the adjacency matrix are all positive.Under the assumptions that communication delays and the subgradients are bounded， and the switching directed networks are periodically strongly connected， we prove that the convergence of the proposed distributed Push-sum subgradient optimization algorithm. It is shown that the convergence rate in the case of communication delays is slower than that without communication delays， and meanwhile the proposed algorithm may bring out large convergence error. Finally， the conclusion is verified by numerical simulation.

Key words：time-varying delays； Push-sum algorithm； subgradient； distributed optimization

近年来，基于局部信息交互协同的整个网络的优化问题成为多个体网络新的研究热点[1-2]，因而引起了众多学者的广泛兴趣。科学与工程领域的众多问题，如大规模机器学习、分布式跟踪与定位等，都可以归类于多个体网络分布式优化问题。目前分布式优化算法主要分为三种：原始优化算法[3]6 857，对偶优化算法，原始-对偶优化算法，且这三种优化算法通常解决的问题具有如下特点：整个网络优化的目标函数可以分解成网络中各个个体的目标函数之和，每个个体仅知道其自身的目标函数，且只能通过和其邻居个体信息交互协同地解决整个网络的问题，即此时所有个体状态趋于一致且这个一致性值还是网络优化问题目标函数的最优解[4]。由于分布式优化问题涉及到个体间的局部信息交互，因而与多个体网络的一致性问题，特别是平均一致性（即每个个体状态收敛到所有个体初始状态的算术平均值）密切相关。目前一致性的研究主要分为基于单变量信息通信[5]和双变量信息通信两类。单变量信息通信即个体间交互的仅是某一个状态变量，目前绝大部分多个体网络一致性的研究是基于单变量信息通信，但其缺点是，只有有向平衡网络中的个体才能达到平均一致性，这要求网络对应的邻接矩阵必须是双随机矩阵，因而具有很大的局限性。但实际多个体网络通常是动态切换、有向非平衡的，这就需要用到双变量信息通信。因此，基于双变量信息通信的Push-sum算法的一致性研究近年来引起学者的极大兴趣，Push-sum一致性算法并不要求网络是有向平衡的，但要求网络中每个个体有两个状态变量，每次迭代交互的是这两个状态变量的比值。

当个体间进行信息交换时，信息会因为网络拥塞或受实际通信设备的影响，不能及时的送达接收端，即出现信息接收滞后的情况，这导致多个体网络信息传递产生时延。因此对有时延的多个体网络的一致性研究成为一个热点。在时延有界的情况下，文献[6-7]分别研究了一致性问题、受限一致性问题和平均一致性问题，其共同之处均是随机邻接矩阵需具有正对角元素，但当随机邻接矩阵需不具有正对角元素时，这些方法均不再适用。endprint