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

Mingyi Hong, Tsung-Hui Chang, Xiangfeng Wang, Meisam Razaviyayn, Shiqian Ma, Zhi-Quan LuoICASSP 2014 · OpenReview

Abstract

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.
BibTeX
@inproceedings{hong2014block,
  author = {Mingyi Hong and Tsung-Hui Chang and Xiangfeng Wang and Meisam Razaviyayn and Shiqian Ma and Zhi-Quan Luo},
  title = {{A block coordinate descent method of multipliers: Convergence analysis and applications}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=mQXbhG1NoJc},
}

Loading related content...

Figure