Paper Info
Title
A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization.
Abstract
Consider the problem of minimizing the sum of a smooth convex function and a separable nonsmooth convex function subject to linear coupling constraints. Problems of this form arise in many contemporary applications, including signal processing, wireless networking, and smart grid provisioning. Motivated by the huge size of these applications, we propose a new class of first-order primal-dual algorithms called the block successive upper-bound minimization method of multipliers (BSUM-M) to solve this family of problems. The BSUM-M updates the primal variable blocks successively by minimizing locally tight upper bounds of the augmented Lagrangian of the original problem, followed by a gradient-type update for the dual variable in closed form. We show that under certain regularity conditions, and when the primal block variables are updated in either a deterministic or a random fashion, the BSUM-M converges to a point in the set of optimal solutions. Moreover, in the absence of linear constraints and under similar conditions as in the previous result, we show that the randomized BSUM-M (which reduces to the randomized block successive upper-bound minimization method) converges at an asymptotically linear rate without relying on strong convexity.
Year
DOI
Venue
2020
10.1287/moor.2019.1010
MATHEMATICS OF OPERATIONS RESEARCH
Keywords
DocType
Volume
block successive upper-bound minimization,alternating direction method of multipliers,randomized block coordinate descent
Journal
45
Issue
ISSN
Citations 
3
0364-765X
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Mingyi Hong1153391.29
Tsung-Hui Chang2114272.18
Xiangfeng Wang328021.75
Meisam Razaviyayn422.40
Shiqian Ma5106863.48
Zhi-Quan Luo600.34