A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
From MaRDI portal
Publication:3387904
DOI10.1287/MOOR.2019.1010zbMATH Open1456.90124arXiv1401.7079OpenAlexW3034770799MaRDI QIDQ3387904FDOQ3387904
Authors: Mingyi Hong, Tsung-Hui Chang, Meisam Razaviyayn, Zhi-Quan Luo, Xiangfeng Wang, Shiqian Ma 
Publication date: 8 January 2021
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.7079
Recommendations
- A proximal block minimization method of multipliers with a substitution procedure
- Block-coordinate primal-dual method for nonsmooth minimization over linear constraints
- Randomized primal-dual proximal block coordinate updates
- Projective method of multipliers for linearly constrained convex minimization
- First-order algorithms for convex optimization with nonseparable objective and coupled constraints
alternating direction method of multipliersrandomized block coordinate descentblock successive upper-bound minimization
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Title not available (Why is that?)
- Atomic Decomposition by Basis Pursuit
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the global and linear convergence of the generalized alternating direction method of multipliers
- A unified convergence analysis of block successive minimization methods for nonsmooth optimization
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- Fast alternating linearization methods for minimizing the sum of two convex functions
- A coordinate gradient descent method for nonsmooth separable minimization
- Title not available (Why is that?)
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Fast alternating direction optimization methods
- Proximal splitting methods in signal processing
- Sparse Reconstruction by Separable Approximation
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Title not available (Why is that?)
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Title not available (Why is that?)
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- A unified primal-dual algorithm framework based on Bregman iteration
- Alternating proximal gradient method for convex minimization
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Title not available (Why is that?)
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- Title not available (Why is that?)
- Alternating direction method with Gaussian back substitution for separable convex programming
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Title not available (Why is that?)
- Coordinate descent algorithms
- On the convergence of block coordinate descent type methods
- An Efficient TVL1 Algorithm for Deblurring Multichannel Images Corrupted by Impulsive Noise
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Error bounds and convergence analysis of feasible descent methods: A general approach
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- On the linear convergence of the alternating direction method of multipliers
- On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
- On the convergence of the coordinate descent method for convex differentiable minimization
- On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems
- On the Convergence of Constrained Parallel Variable Distribution Algorithms
- On the linear convergence of the approximate proximal splitting method for non-smooth convex optimization
- Iteration complexity analysis of block coordinate descent methods
- Title not available (Why is that?)
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- Equilibrium Pricing of Interference in Cognitive Radio Networks
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- MIMO Cognitive Radio: A Game Theoretical Approach
Cited In (23)
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- A generic coordinate descent solver for non-smooth convex optimisation
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- Convergence of Bregman Peaceman-Rachford splitting method for nonconvex nonseparable optimization
- Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights
- A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
- First-order algorithms for convex optimization with nonseparable objective and coupled constraints
- An inertial ADMM for a class of nonconvex composite optimization with nonlinear coupling constraints
- A proximal alternating direction method for multi-block coupled convex optimization
- Randomized primal-dual proximal block coordinate updates
- Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- Block-coordinate primal-dual method for nonsmooth minimization over linear constraints
- An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
- Alternating proximal gradient method for convex minimization
- Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
- A proximal block minimization method of multipliers with a substitution procedure
- On the sublinear convergence rate of multi-block ADMM
- Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications
- Inertial alternating direction method of multipliers for non-convex non-smooth optimization
- A PARAMETRIC SUCCESSIVE UNDERESTIMATION METHOD FOR CONVEX PROGRAMMING PROBLEMS WITH AN ADDITIONAL CONVEX MULTIPLICATIVE CONSTRAINT
- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
Uses Software
This page was built for publication: A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387904)
