A proximal gradient algorithm for decentralized nondifferentiable optimization

In this paper, we focus on solving the decentralized consensus optimization problem defined over a networked multi-agent system. All the agents shall cooperatively find a common minimizer of the overall objective while each agent holds its own local objective and can only communicate with its neighbors. Motivated by many applications in which the local objective is the sum of a differentiable part and a nondifferentiable part, this paper proposes a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the separable problem structure. Here, “exact” means this decentralized algorithm yields an exact consensus minimizer using a fixed step size. When the nondifferentiable part vanishes, PG-EXTRA reduces to EXTRA, an existing decentralized optimization algorithm. When the differentiable part vanishes, PG-EXTRA finds its special case P-EXTRA, a proximal algorithm. We prove convergence and rate of convergence for PG-EXTRA. Numerical experiments on a decentralized compressive sensing problem validates the theoretical results.