李德权++张晓倩

摘 要：针对多个体系统在个体间进行信息交换时发生接收信息滞后，存在通信时延，影响优化算法的收敛速度的问题，提出一种时延情形下的分布式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]。……