A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
From MaRDI portal
Publication:3387904
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.
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
Cites work
- scientific article; zbMATH DE number 6378119 (Why is no real title available?)
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1321699 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- scientific article; zbMATH DE number 6253925 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A coordinate gradient descent method for nonsmooth separable minimization
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints
- A unified convergence analysis of block successive minimization methods for nonsmooth optimization
- A unified primal-dual algorithm framework based on Bregman iteration
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction method with Gaussian back substitution for separable convex programming
- Alternating proximal gradient method for convex minimization
- An Efficient TVL1 Algorithm for Deblurring Multichannel Images Corrupted by Impulsive Noise
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Atomic Decomposition by Basis Pursuit
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Coordinate descent algorithms
- Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Equilibrium Pricing of Interference in Cognitive Radio Networks
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Fast alternating direction optimization methods
- Fast alternating linearization methods for minimizing the sum of two convex functions
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- Iteration complexity analysis of block coordinate descent methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- 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
- MIMO Cognitive Radio: A Game Theoretical Approach
- Multi-Agent Distributed Optimization via Inexact Consensus ADMM
- On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
- On the Convergence of Constrained Parallel Variable Distribution Algorithms
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
- On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the convergence of block coordinate descent type methods
- On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
- On the convergence of the coordinate descent method for convex differentiable minimization
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems
- On the linear convergence of the alternating direction method of multipliers
- On the linear convergence of the approximate proximal splitting method for non-smooth convex optimization
- Proximal splitting methods in signal processing
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- Sparse Reconstruction by Separable Approximation
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
Cited in
(23)- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- 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
- On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions
- Majorized iPADMM for Nonseparable Convex Minimization Models with Quadratic Coupling Terms
- 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
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)
