Fast distributed optimization over directed graphs
Chenguang Xi, Qiong Wu, Usman A. Khany · 2016
We develop a fast distributed algorithm, termed DEXTRA, to solve optimization problems when N agents reach agreement and collaboratively minimize the sum of their local objectives over the network, where the communications between agents are described by a directed graph. Existing algorithms, including Gradient-Push (GP) and Directed-Distributed Gradient Descent (D-DGD), solve this problem restricted to directed graphs with a convergence rate of O(ln k/√k). Our analysis shows that DEXTRA converges at a linear rate O(ϵk) for some constant ϵ < 1, with the assumption that the objective functions are strongly convex. Simulation examples illustrate our findings.