Distributed mirror descent method for saddle point problems over directed graphs

In this article, we consider a mini-max multi-agent optimization problem where multiple agents cooperatively optimize a sum of local convex–concave functions, each of which is available to one specific agent in a network. To solve the problem, we propose a distributed optimization method by extending classical mirror descent algorithms to the distributed setting. We obtain the convergence of the algorithm under wild conditions that the agent communication follows a directed graph and the related weighted matrices are row stochastic. In particular, when the weighted matrices are restricted to be doubly stochastic, we provide the explicit convergence rate of the algorithm by choosing the stepsize in a suitable way. The proposed algorithm can be viewed as a generalization of the subgradient projection methods since it utilizes a customized Bregman divergence instead of the usual Euclidean squared distance. Finally, some simulation results on a matrix game are presented to illustrate the performance of the algorithm. © 2016 Wiley Periodicals, Inc. Complexity 21: 178–190, 2016. © 2016 Wiley Periodicals, Inc.