Bi-alternating direction method of multipliers over graphs
- Publication Type:
- Conference Proceeding
- ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, 2015, 2015-August pp. 3571 - 3575
- Issue Date:
© 2015 IEEE. 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.
Please use this identifier to cite or link to this item: