ADD-OPT: Accelerated Distributed Directed Optimization

In this paper, we consider distributed optimization problems where the goal is to minimize a sum of objective functions over a multiagent network. We focus on the case when the interagent communication is described by a strongly connected, directed graph. The proposed algorithm, Accelerated Distributed Directed OPTimization (ADDOPT), achieves the best known convergence rate for this class of problems, O(μk), 0 <; μ <; 1, given strongly convex, objective functions with globally Lipschitz-continuous gradients, where k is the number of iterations. Moreover, ADD-OPT supports a wider and more realistic range of step sizes in contrast to existing work. In particular, we show that ADD-OPT converges for arbitrarily small (positive) step sizes. Simulations further illustrate our results.