A Push-Pull Gradient Method for Distributed Optimization in Networks
A Push-Pull Gradient Method for Distributed Optimization in Networks
复制标题
DOI：
10.1109/cdc.2018.8619047
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Shi Pu;Wei Shi;Jinming Xu;A. Nedić
中科院分区：
文献类型：
--
作者：
Shi Pu;Wei Shi;Jinming Xu;A. Nedić
本文主要研究网络中的分布式凸优化问题，其中每个代理都有自己的凸代价函数，目标是在满足网络连通性结构的同时最小化代理代价函数之和。为了最小化代价函数的总和，我们考虑了一种新的基于梯度的分布式方法，其中每个节点维护两个估计，即最优决策变量的估计和代理目标函数平均值的梯度估计。从智能体的角度来看，关于决策变量的信息被推送给邻居，而关于梯度的信息则从邻居那里拉出(由此产生了推拉梯度法)。该方法将算法与不同类型的分布式体系结构相统一，包括分散式(对等)、集中式(主从式)和半集中式(领导者-跟随式)结构。我们证明了该算法对于有向静态网络上的强凸光滑目标函数是线性收敛的。在我们的数值测试中，该算法即使对于时变的有向网络也表现得很好。
In this paper, we focus on solving a distributed convex optimization problem in a network, where each agent has its own convex cost function and the goal is to minimize the sum of the agents' cost functions while obeying the network connectivity structure. In order to minimize the sum of the cost functions, we consider a new distributed gradient-based method where each node maintains two estimates, namely, an estimate of the optimal decision variable and an estimate of the gradient for the average of the agents' objective functions. From the viewpoint of an agent, the information about the decision variable is pushed to the neighbors, while the information about the gradients is pulled from the neighbors (hence giving the name “push-pull gradient method”). The method unifies the algorithms with different types of distributed architecture, including decentralized (peer-to-peer), centralized (master-slave), and semi-centralized (leader-follower) architecture. We show that the algorithm converges linearly for strongly convex and smooth objective functions over a directed static network. In our numerical test, the algorithm performs well even for time-varying directed networks.