Optimization over directed graphs: Linear convergence rate

Abstract

This paper considers distributed multi-agents optimization problems where agents collaborate to minimize the sum of locally known convex functions. We focus on the case when the communication between agents is described by a directed graph. The proposed algorithm achieves the best known rate of convergence for this class of problems, O(μ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> ) for 0 <; μ <; 1, given that the objective functions are strongly-convex, where k is the number of iterations. Moreover, it provides a wider and more realistic range of step-size compared with existing methods.