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 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.

References in corpus (3)

• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function

Cited by in corpus (23)

• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions
• A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data
• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Parallel Direction Method of Multipliers
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• On the Sublinear Convergence Rate of Multi-Block ADMM
• Randomized Primal-Dual Proximal Block Coordinate Updates
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
• Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
• Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems
• Two-block vs. Multi-block ADMM: An empirical evaluation of convergence
• Auxiliary Problem Principle of augmented Lagrangian with Varying Core Functions for Large-Scale Structured Convex Problems
• Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models
• Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
• Computing B-Stationary Points of Nonsmooth DC Programs
• UAV Positioning and Power Control for Two-Way Wireless Relaying
• A Generalized Alternating Direction Method of Multipliers with Semi-Proximal Terms for Convex Composite Conic Programming
• A generic coordinate descent solver for nonsmooth convex optimization
• Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity