A block coordinate descent method of multipliers: Convergence analysis and applications

In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.