  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 parameter- settings and resilience to transmission failure are also
investigated through the experiments of distributed averaging.
