Distributed Optimization Using the Primal-Dual Method of Multipliers

Abstract

In this paper, we propose the primal-dual method of multipliers (PDMM) for distributed optimization over a graph. In particular, we optimize a sum of convex functions defined over a graph, where every edge in the graph carries a linear equality constraint. In designing the new algorithm, an augmented primal-dual Lagrangian function is constructed which smoothly captures the graph topology. It is shown that a saddle point of the constructed function provides an optimal solution of the original problem. Further under both the synchronous and asynchronous updating schemes, PDMM has the convergence rate of O(1=K) (where K denotes the iteration index) for general closed, proper and convex functions. Other properties of PDMM such as convergence speeds versus different parametersettings and resilience to transmission failure are also investigated through the experiments of distributed averaging.