# A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization

arXiv: https://arxiv.org/abs/1401.7079 · HTML: https://mlsanity.com/paper/1401.7079/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2014.

## Built on by (most cited first, 3 of 3)

- [A Framework of Inertial Alternating Direction Method of Multipliers for Non-Convex Non-Smooth Optimization](https://mlsanity.com/paper/2102.05433/) (2021)
- [Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models](https://mlsanity.com/paper/2105.05953/) (2021)
- [Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints](https://mlsanity.com/paper/2201.07657/) (2022)

## Abstract (arXiv)

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 the set of optimal solutions. Moreover, in the absence of linear constraints, we show that the BSUM-M, which reduces to the block successive upper-bound minimization (BSUM) method, is capable of linear convergence without strong convexity.