DECENTRALIZED LINEARIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS

This paper develops a decentralized linearized alternating direction method of multipliers (LADMM) that minimizes the sum of local cost functions in a multi-agent network. Through linearizing the local cost functions agents can obtain their local solutions with simple algebraic operations and gradient descent steps. We prove that the algorithm linearly converges to the optimal solution given that the local cost functions are strongly convex and have Lipschitz gradients. The decentralized LADMM has similar computations as the distributed (sub) gradient method but outperforms the latter, which is unable to achieve linear rate of convergence and convergence to the exact optimal solution simultaneously. Compared to its non-linearized counterpart that suffers from high computation burden, the decentralized LADMM has a comparable rate of convergence according to both theoretical analysis and numerical experiments.