Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
From MaRDI portal
(Redirected from Publication:334319)
Abstract: The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of convex functions with block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we present convergence and convergence rate results for the multi-block ADMM applied to solve certain -block convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an -optimal solution within iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an -optimal solution within iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz property, which essentially covers most convex optimization models except for some pathological cases.
Recommendations
- Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Convergence of ADMM for multi-block nonconvex separable optimization models
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Block-wise ADMM with a relaxation factor for multiple-block convex programming
- On the sublinear convergence rate of multi-block ADMM
- Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond
- Convergence analysis of L-ADMM for multi-block linear-constrained separable convex minimization problem
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- Iteration-complexity analysis of a generalized alternating direction method of multipliers
Cites work
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
- A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- A note on the alternating direction method of multipliers
- Alternating direction method with Gaussian back substitution for separable convex programming
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
- 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
- On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
- On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the convergence analysis of the alternating direction method of multipliers with three blocks
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the sublinear convergence rate of multi-block ADMM
- Parallel multi-block ADMM with \(o(1/k)\) convergence
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
- Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
Cited in
(24)- Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
- On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming
- 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
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- Randomized primal-dual proximal block coordinate updates
- Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers
- On unifying multi-view self-representations for clustering by tensor multi-rank minimization
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- Some notes on the divergence example for multi-block alternating direction method of multipliers
- On the sublinear convergence rate of multi-block ADMM
- Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
- Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
- An Efficient Inexact Gauss–Seidel-Based Algorithm for Image Restoration with Mixed Noise
- An extended proximal ADMM algorithm for three-block nonconvex optimization problems
- Multi-block relaxed-dual linear inertial ADMM algorithm for nonconvex and nonsmooth problems with nonseparable structures
- A two-level distributed algorithm for nonconvex constrained optimization
- Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
- Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
- Estimation of graphical models through structured norm minimization
This page was built for publication: Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334319)
