Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity

DOI10.1007/S10915-016-0182-0zbMATH Open1348.90522arXiv1504.03087OpenAlexW783438975MaRDI QIDQ334319FDOQ334319

Authors: Tian-Yi Lin, Shiqian Ma, Shuzhong Zhang 

Publication date: 1 November 2016

Published in: Journal of Scientific Computing (Search for Journal in Brave)

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 $N$ $(Ngeq3)$ convex functions with $N$ 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 $N$-block $(Ngeq3)$ convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an $epsilon$-optimal solution within $O(1/epsilo{n}^2)$ iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an $epsilon$-optimal solution within $O(1/epsilon)$ 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.

Full work available at URL: https://arxiv.org/abs/1504.03087

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

zbMATH Keywords

regularizationconvex optimizationconvergence ratealternating direction method of multipliers (ADMM)[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Kurdyka-%EF%BF%BD%EF%BF%BDojasiewicz+property&go=Go Kurdyka-��ojasiewicz property]

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30)

Cites Work

• Distributed optimization and statistical learning via the alternating direction method of multipliers
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• 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
• On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
• Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
• A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
• The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
• 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
• 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
• Title not available (Why is that?)
• Alternating direction method with Gaussian back substitution for separable convex programming
• Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• A note on the alternating direction method of multipliers
• On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
• A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers
• Global convergence of unmodified 3-block ADMM for a class of convex minimization problems
• On the convergence analysis of the alternating direction method of multipliers with three blocks
• A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block
• On the Global Linear Convergence of the ADMM with MultiBlock Variables
• On the sublinear convergence rate of multi-block ADMM

Cited In (24)

• 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
• An Efficient Inexact Gauss–Seidel-Based Algorithm for Image Restoration with Mixed Noise
• Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property
• Multi-block relaxed-dual linear inertial ADMM algorithm for nonconvex and nonsmooth problems with nonseparable structures
• An extended proximal ADMM algorithm for three-block nonconvex optimization problems
• A two-level distributed algorithm for nonconvex constrained optimization
• Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
• Estimation of graphical models through structured norm minimization
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Two symmetrized coordinate descent methods can be \(O(n^2)\) times slower than the randomized version

Uses Software

• RASL

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)