数据丢包情形下分布式无梯度Push-sum算法

Distributed Push-sum Gradient-free Algorithm under Data Packet-Dropping

针对多个体网络中个体信息交互常会出现数据丢包及个体目标函数次梯度难以计算或不存在的问题,提出数据丢包情形下分布式无梯度Push-sum算法,该算法要求网络的权矩阵为列随机而无需是双随机。通过增加虚拟节点进行系统扩维,从而建立一个有限的非均匀的马尔可夫链,并结合遍历性系数的结论证明了所提算法的收敛性。研究表明:收敛误差值与高斯近似函数的光滑参数、目标函数的Lipschitz常数成正比,从而有效解决了数据丢包及个体目标函数次梯度不存在或难以计算的分布式优化问题。

The problem of distributed optimization in unbalanced networks with data packet-dropping communication among the agents is investigated in this paper.〖JP2〗Due to the fact that data packet-dropping may occur when agents communicate with each other in the multi-agent network and the subgradient of each agent’s local objective function is computationally infeasible or does not exist,this paper proposes a distributed Push-sum gradient-free〖JP〗optimization algorithm under the condition of data packet-dropping,which requires that the weight matrix associated with the multi-agent network be column stochastic but not necessarily doubly stochastic.By adding virtual nodes for system expansion,a finite inhomogenous Markov chain was obtained,and the convergence of the proposed method to an approximate solution was testified by combining results of ergodic coefficients,.It is shown that the error level of the convergence is proportional to the smoothing parameters of Gaussian approximation function and the Lipschitz constant of the objective function,so it can effectively solve the distributed optimization problem of data packet-dropping when the subgradient of each agent’s local objective function is computationally infeasible or does not exist.