A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization

This paper considers a convex optimization problem with a globally coupled linear equality constraint and local polyhedron constraints and develops efficient distributed optimization methods. The considered problem has many engineering applications. Due to the polyhedron constraints, agents in the existing methods have to deal with polyhedron constrained subproblems at each iteration. One of the key challenges is that projection onto a polyhedron set is not trivial, which prohibits the agents from solving these subproblems efficiently. In this paper, based on the alternating direction method of multipliers (ADMM), we propose a new distributed optimization method, called proximal dual consensus ADMM (PDC-ADMM). The PDC-ADMM transforms the polyhedron constraints as quadratic penalty terms in the subproblems, making the subproblems efficiently solvable and consequently reducing the overall computational overhead of the agents. In addition, we propose a randomized PDC-ADMM which can deal with time-varying networks with randomly ON/OFF agents and communication errors, and an inexact (randomized) PDC-ADMM for low-complexity computations. We show that the proposed distributed methods converge to the optimal solution set almost surely and have a O(1/k) ergodic convergence rate in the mean. Numerical results show that the proposed methods offer significantly lower computation time than the existing distributed ADMM method in solving a linearly constrained LASSO problem.