A Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
A Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
复制标题
DOI：
10.1109/lcsys.2018.2834316
复制
发表时间：
2018-03
影响因子：
3
通讯作者：
Ran Xin;U. Khan
中科院分区：
文献类型：
--
作者：
Ran Xin;U. Khan
在这封信中，我们研究分布式优化，其中代理网络，抽象为一个有向图，合作，以最小化平均本地已知的凸函数。现有的大多数有向图的方法都是基于推和（类型）技术，它使用一个独立的算法来渐近学习底层权重矩阵的左或右特征向量。这种策略导致算法中的额外计算、通信和非线性。相比之下，我们提出了一个线性算法的基础上不精确的梯度方法和梯度估计技术。在每个局部函数是强凸的Lipschitz连续梯度的假设下，我们证明了该算法以足够小的步长几何收敛到全局极小值。我们提出了模拟来说明的理论研究结果。
In this letter, we study distributed optimization, where a network of agents, abstracted as a directed graph, collaborates to minimize the average of locally known convex functions. Most of the existing approaches over directed graphs are based on push-sum (type) techniques, which use an independent algorithm to asymptotically learn either the left or right eigenvector of the underlying weight matrices. This strategy causes additional computation, communication, and nonlinearity in the algorithm. In contrast, we propose a linear algorithm based on an inexact gradient method and a gradient estimation technique. Under the assumptions that each local function is strongly convex with Lipschitz-continuous gradients, we show that the proposed algorithm geometrically converges to the global minimizer with a sufficiently small step-size. We present simulations to illustrate the theoretical findings.