Distributed ADMM With Linear Updates Over Directed Networks

摘要

Distributed optimization over a network of agents is ubiquitous in applications such as power system, robotics and statistical learning. In many settings, the communication network is directed, i.e., the communication links between agents are unidirectional. While several variations of gradient-descent-based primal methods have been proposed for distributed optimization over directed networks, an extension of dual-ascent methods to directed networks remains a less-explored area. In this paper, we propose a distributed version of the Alternating Direction Method of Multipliers (ADMM) with linear updates for directed networks using balancing weights, called BW-DADMM (Balancing Weights Directed ADMM). We show that if the objective function of the minimization problem is smooth and strongly convex, then BW-DADMM achieves a geometric rate of convergence to the optimal point. Our algorithm exploits the robustness inherent to ADMM by not enforcing accurate consensus, thereby significantly improving the convergence rate. We illustrate this by numerical examples, where we compare the performance of BW-DADMM with that of state-of-the-art ADMM methods over directed graphs.