BI-ALTERNATING DIRECTION METHOD OF MULTIPLIERS OVER GRAPHS

In this paper, we extend the bi-alternating direction method of multipliers (BiADMM) designed on a graph of two nodes to a graph of multiple nodes. In particular, we optimize a sum of convex functions defined over a general graph, where every edge carries a linear equality constraint. In designing the new algorithm, an augmented primal-dual Lagrangian function is carefully constructed which naturally captures the associated graph topology. We show that under both the synchronous and asynchronous updating schemes, the extended BiADMM has the convergence rate of O(1/K) (where K denotes the iteration index) for general closed, proper and convex functions. As an example, we apply the new algorithm for distributed averaging. Experimental results show that the new algorithm remarkably outperforms the state-of-the-art methods.