Push-Sum Distributed Dual Averaging for Convex Optimization in Multiagent Systems With Communication Delays
Cong Wang, Shengyuan Xu, Deming Yuan, Baoyong Zhang, Zhengqiang Zhang
Abstract
The distributed convex optimization problem over the multiagent system is considered in this article, and it is assumed that each agent possesses its own cost function and communicates with its neighbors over a sequence of time-varying directed graphs. However, due to some reasons, there exist communication delays while agents receive information from other agents, and we are going to seek the optimal value of the sum of agents’ loss functions in this case. We desire to handle this problem with the push-sum distributed dual averaging (PS-DDA) algorithm. We study the effects of communication delays on the convergence results of the PS-DDA algorithm and propose an explicit bound on the convergence rate. It is proved that this algorithm converges, and the convergence result of the PS-DDA algorithm will be worse as the maximum delay value on one edge becomes larger. Our analysis indicates that the PS-DDA algorithm can converge at a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathcal {O}}(T^{-0.5})$ </tex-math></inline-formula> with proper step size, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> is iteration span. We finally apply the theoretical results to numerical simulations to show the PS-DDA algorithm’s performance.