Function Splitting and Quadratic Approximation of the Primal-Dual Method of Multipliers for Distributed Optimization over Graphs

We propose two algorithms based on the Primal-Dual Method of Multipliers (PDMM) to be used in distributed network optimization: Function Split PDMM (FS-PDMM) and Quadratically Approximated PDMM (QA-PDMM). Our approaches simplify the local subproblems that must be solved for each node, at each update iteration, improving computational efficiency at distributed processors. FS-PDMM allows for simplified updates of distributed problems involving regularized general convex functions, while QA-PDMM allows smooth local cost functions to be approximated quadratically. In both cases, this leads to iterative updates that require mostly simple and analytic computation rather than numerical solutions to more complex subproblems, particularly when using common regularization functions such as the l-1 and l-2 norms. We show that FS-PDMM is theoretically equivalent to performing conventional PDMM on a network twice the size as the physical network, and prove convergence for QA-PDMM for a common class of problems. Experimentally, we demonstrate convergence and reduction in computational complexity for elastic net regularized least squares and ridge regularized logistic regression.