On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method

DOI10.1137/110836936zbMath1245.90084OpenAlexW1986080131MaRDI QIDQ2903008

Xiao-Ming Yuan, Bing-sheng He

Publication date: 23 August 2012

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/110836936

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Related Items

On inexact stochastic splitting methods for a class of nonconvex composite optimization problems with relative error, A rank-two relaxed parallel splitting version of the augmented Lagrangian method with step size in (0,2) for separable convex programming, Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss, A General Inertial Proximal Point Algorithm for Mixed Variational Inequality Problem, Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit, A new accelerated positive-indefinite proximal ADMM for constrained separable convex optimization problems, Approximation Schemes for Materials with Discontinuities, Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers, Asymptotic behaviour of a nonautonomous evolution equation governed by a quasi-nonexpansive operator, On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming, Convergence Study on the Symmetric Version of ADMM with Larger Step Sizes, A proximal block minimization method of multipliers with a substitution procedure, Faster Lagrangian-Based Methods in Convex Optimization, Structured Sparsity: Discrete and Convex Approaches, GMRES-Accelerated ADMM for Quadratic Objectives, Unnamed Item, Local Linear Convergence of the ADMM/Douglas--Rachford Algorithms without Strong Convexity and Application to Statistical Imaging, A Strictly Contractive Peaceman-Rachford Splitting Method with Logarithmic-Quadratic Proximal Regularization for Convex Programming, Iterative positive thresholding algorithm for non-negative sparse optimization, Stable Camera Motion Estimation Using Convex Programming, A Proximal Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming with Applications to Imaging, Unnamed Item, A dual split Bregman method for fast $\ell ^1$ minimization, A Generalized Primal-Dual Algorithm with Improved Convergence Condition for Saddle Point Problems, Nonexpansiveness of a linearized augmented Lagrangian operator for hierarchical convex optimization, Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis, ALADIN‐—An open‐source MATLAB toolbox for distributed non‐convex optimization, Unnamed Item, A golden ratio proximal alternating direction method of multipliers for separable convex optimization, ADMM for Penalized Quantile Regression in Big Data, Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping, A proximal fully parallel splitting method with a relaxation factor for separable convex programming, A variable projection method for large-scale inverse problems with \(\ell^1\) regularization, On convergence rates of proximal alternating direction method of multipliers, A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP, Complexity analysis of a stochastic variant of generalized alternating direction method of multipliers, A revisit of Chen-Teboulle's proximal-based decomposition method, A randomized progressive hedging algorithm for stochastic variational inequality, Approximate customized proximal point algorithms for separable convex optimization, Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems, Faster first-order primal-dual methods for linear programming using restarts and sharpness, Resolvent splitting for sums of monotone operators with minimal lifting, A two-stage numerical approach for the sparse initial source identification of a diffusion–advection equation ^*, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, A Flexible Space-Variant Anisotropic Regularization for Image Restoration with Automated Parameter Selection, PCA Sparsified, Fisher markets with linear constraints: equilibrium properties and efficient distributed algorithms, The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis, A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems, Improved Pointwise Iteration-Complexity of A Regularized ADMM and of a Regularized Non-Euclidean HPE Framework, Hybrid Jacobian and Gauss--Seidel Proximal Block Coordinate Update Methods for Linearly Constrained Convex Programming, An accelerated primal-dual iterative scheme for the L ² -TV regularized model of linear inverse problems, An alternating direction method of multipliers with a worst-case $O(1/n^2)$ convergence rate, Fixed Point Analysis of Douglas--Rachford Splitting for Ptychography and Phase Retrieval, An Alternating Direction Method of Multipliers for Optimal Control Problems Constrained with Elliptic Equations, FOM – a MATLAB toolbox of first-order methods for solving convex optimization problems, Learning partial differential equations via data discovery and sparse optimization, An Alternating Direction Method of Multipliers for the Optimization Problem Constrained with a Stationary Maxwell System, Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity, A Simple Parallel Algorithm with an $O(1/t)$ Convergence Rate for General Convex Programs, Median filtering‐based methods for static background extraction from surveillance video, Alternating Direction Method of Multipliers for Linear Inverse Problems, A gradient method for the monotone fused least absolute shrinkage and selection operator, ON THE CONVERGENCE RATE OF THE ALTERNATING DIRECTION METHOD OF MULTIPLIERS IN A COMPLEX DOMAIN, Implementing the Alternating Direction Method of Multipliers for Big Datasets: A Case Study of Least Absolute Shrinkage and Selection Operator, Lattice-Based Patterned Fabric Inspection by Using Total Variation with Sparsity and Low-Rank Representations, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA, Block-wise Alternating Direction Method of Multipliers for Multiple-block Convex Programming and Beyond, The augmented Lagrangian method with full Jacobian decomposition and logarithmic-quadratic proximal regularization for multiple-block separable convex programming, On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM, A Block Successive Upper-Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization, Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, Solving Fused Penalty Estimation Problems via Block Splitting Algorithms, A partial PPA block-wise ADMM for multi-block linearly constrained separable convex optimization, Iteration complexity on the generalized Peaceman–Rachford splitting method for separable convex programming, SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD, An alternate minimization method beyond positive definite proximal regularization: convergence and complexity, On the Global Linear Convergence of the ADMM with MultiBlock Variables, An ADMM-Newton-CNN numerical approach to a TV model for identifying discontinuous diffusion coefficients in elliptic equations: convex case with gradient observations, An Accelerated Linearized Alternating Direction Method of Multipliers, Minimization of $\ell_{1-2}$ for Compressed Sensing, LOW-RANK AND SPARSE MATRIX RECOVERY FROM NOISY OBSERVATIONS VIA 3-BLOCK ADMM ALGORITHM, Truncated $l_{1-2}$ Models for Sparse Recovery and Rank Minimization, LINEARIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR SEPARABLE CONVEX OPTIMIZATION OF REAL FUNCTIONS IN COMPLEX DOMAIN, On the Convergence Rate of Inexact Majorized sGS ADMM with Indefinite Proximal Terms for Convex Composite Programming, A Stochastic Variance Reduced Primal Dual Fixed Point Method for Linearly Constrained Separable Optimization, A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance, On Alternating Direction Methods of Multipliers: A Historical Perspective, Application of the Alternating Direction Method of Multipliers to Control Constrained Parabolic Optimal Control Problems and Beyond, An accelerated majorization-minimization algorithm with convergence guarantee for non-Lipschitz wavelet synthesis model ^*, Dual–primal proximal point algorithms for extended convex programming, Convergence analysis on a modified generalized alternating direction method of multipliers, Local R-linear convergence of ADMM-based algorithm for \(\ell_1\)-norm minimization with linear and box constraints, Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization, Linearized alternating direction method of multipliers for sparse group and fused Lasso models, Bounding duality gap for separable problems with linear constraints, Rigorous convergence analysis of alternating variable minimization with multiplier methods for quadratic programming problems with equality constraints, Conic optimization via operator splitting and homogeneous self-dual embedding, Solving total-variation image super-resolution problems via proximal symmetric alternating direction methods, On the ergodic convergence rates of a first-order primal-dual algorithm, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, An algorithm twisted from generalized ADMM for multi-block separable convex minimization models, Certifying numerical estimates of spectral gaps, Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity, Spatially dependent regularization parameter selection for total generalized variation-based image denoising, Sparse approximate solution of fitting surface to scattered points by MLASSO model, Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems, Alternating direction method of multipliers for separable convex optimization of real functions in complex variables, Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, Convergence analysis of primal-dual based methods for total variation minimization with finite element approximation, On the information-adaptive variants of the ADMM: an iteration complexity perspective, A partially isochronous splitting algorithm for three-block separable convex minimization problems, On the \(O(1/t)\) convergence rate of the parallel descent-like method and parallel splitting augmented Lagrangian method for solving a class of variational inequalities, An improved first-order primal-dual algorithm with a new correction step, Two-stage stochastic variational inequalities: an ERM-solution procedure, On the sublinear convergence rate of multi-block ADMM, On the convergence rate of a class of proximal-based decomposition methods for monotone variational inequalities, Tight global linear convergence rate bounds for Douglas-Rachford splitting, iPiasco: inertial proximal algorithm for strongly convex optimization, A proximal alternating linearization method for minimizing the sum of two convex functions, Sparse and low-rank matrix regularization for learning time-varying Markov networks, Convergence of ADMM for multi-block nonconvex separable optimization models, Alternating split Bregman method for the bilaterally constrained image deblurring problem, An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems, Parallel multi-block ADMM with \(o(1/k)\) convergence, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, First-order algorithms for convex optimization with nonseparable objective and coupled constraints, A homotopy alternating direction method of multipliers for linearly constrained separable convex optimization, Simultaneous image fusion and denoising by using fractional-order gradient information, A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming, Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights, Sensitivity analysis of the proximal-based parallel decomposition methods, Preconditioned ADMM for a class of bilinear programming problems, Modified alternating direction methods for the modified multiple-sets split feasibility problems, An implementable first-order primal-dual algorithm for structured convex optimization, A phase model for point spread function estimation in ground-based astronomy, Distributed adaptive dynamic programming for data-driven optimal control, Two-step methods for image zooming using duality strategies, Proximal alternating penalty algorithms for nonsmooth constrained convex optimization, Convergence of the augmented decomposition algorithm, Global convergence of ADMM in nonconvex nonsmooth optimization, Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization, A distributed quantile estimation algorithm of heavy-tailed distribution with massive datasets, The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex, The Glowinski-Le Tallec splitting method revisited: a general convergence and convergence rate analysis, An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization, The convergence rate of the proximal alternating direction method of multipliers with indefinite proximal regularization, On the \(O(1/t)\) convergence rate of Ye-Yuan's modified alternating direction method of multipliers, Second order total generalized variation for Speckle reduction in ultrasound images, On the linear convergence of the alternating direction method of multipliers, A convex optimization model and algorithm for retinex, An efficient alternating direction method of multipliers for optimal control problems constrained by random Helmholtz equations, Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization, Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization, Generalized symmetric ADMM for separable convex optimization, An extragradient-based alternating direction method for convex minimization, A symmetric version of the generalized alternating direction method of multipliers for two-block separable convex programming, A new globally convergent algorithm for non-Lipschitz \(\ell_{p}-\ell_q\) minimization, Total variation with overlapping group sparsity for deblurring images under Cauchy noise, Nonsymmetric proximal point algorithm with moving proximal centers for variational inequalities: convergence analysis, Learning latent variable Gaussian graphical model for biomolecular network with low sample complexity, On the convergence analysis of the alternating direction method of multipliers with three blocks, Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis, A faster generalized ADMM-based algorithm using a sequential updating scheme with relaxed step sizes for multiple-block linearly constrained separable convex programming, Dynamic stochastic approximation for multi-stage stochastic optimization, General splitting methods with linearization for the split feasibility problem, The distance between convex sets with Minkowski sum structure: application to collision detection, Convergence rates for an inexact ADMM applied to separable convex optimization, A survey on conic relaxations of optimal power flow problem, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Convergence study on strictly contractive peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms, A class of ADMM-based algorithms for three-block separable convex programming, Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers, Alternating direction method of multipliers with difference of convex functions, Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization, Selective linearization for multi-block statistical learning, Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers, On preconditioned and relaxed AVMM methods for quadratic programming problems with equality constraints, Tensor train rank minimization with nonlocal self-similarity for tensor completion, An extended proximal ADMM algorithm for three-block nonconvex optimization problems, Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach, A proximal augmented method for semidefinite programming problems, On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM, On the convergence rate of Douglas-Rachford operator splitting method, A parallel splitting ALM-based algorithm for separable convex programming, A fundamental proof of convergence of alternating direction method of multipliers for weakly convex optimization, Stochastic primal dual fixed point method for composite optimization, Two new customized proximal point algorithms without relaxation for linearly constrained convex optimization, Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems, A multi-mode expansion method for boundary optimal control problems constrained by random Poisson equations, PPA-like contraction methods for convex optimization: a framework using variational inequality approach, An alternating direction method of multipliers for elliptic equation constrained optimization problem, On non-ergodic convergence rate of the operator splitting method for a class of variational inequalities, Peridynamics enabled learning partial differential equations, Efficient iterative method for SOAV minimization problem with linear equality and box constraints and its linear convergence, The symmetric ADMM with indefinite proximal regularization and its application, A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm, A survey on some recent developments of alternating direction method of multipliers, On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming, Primal-dual algorithms for total variation based image restoration under Poisson noise, Fast and stable nonconvex constrained distributed optimization: the ELLADA algorithm, Performance of first- and second-order methods for \(\ell_1\)-regularized least squares problems, Constrained TV\(_p\)-\(\ell_2\) model for image restoration, Accelerated gradient sliding for structured convex optimization, Iteration-complexity analysis of a generalized alternating direction method of multipliers, A proximal Peaceman-Rachford splitting method for compressive sensing, Proportional-integral projected gradient method for conic optimization, On the global and linear convergence of the generalized alternating direction method of multipliers, Non-convex split Feasibility problems: models, algorithms and theory, Alternating proximal gradient method for convex minimization, The springback penalty for robust signal recovery, Novel alternating update method for low rank approximation of structured matrices, On the convergence of recursive SURE for total variation minimization, Convergence analysis of positive-indefinite proximal ADMM with a Glowinski's relaxation factor, Inertial generalized proximal Peaceman-Rachford splitting method for separable convex programming, Distributed Model Predictive Control of linear discrete-time systems with local and global constraints, A proximal ADMM with the Broyden family for convex optimization problems, A spatially adaptive hybrid total variation model for image restoration under Gaussian plus impulse noise, An accelerated proximal augmented Lagrangian method and its application in compressive sensing, A generalized inexact Uzawa method for stable principal component pursuit problem with nonnegative constraints, Alternating direction method of multipliers for nonconvex fused regression problems, Inexact alternating direction methods of multipliers for separable convex optimization, Projective method of multipliers for linearly constrained convex minimization, An improved total variation regularized RPCA for moving object detection with dynamic background, Customized alternating direction methods of multipliers for generalized multi-facility Weber problem, Block-wise ADMM with a relaxation factor for multiple-block convex programming, \(O(1/t)\) complexity analysis of the generalized alternating direction method of multipliers, Robust multicategory support matrix machines, Efficient iterative solution of finite element discretized nonsmooth minimization problems, A generalized forward-backward splitting operator: degenerate analysis and applications, Robust regularized extreme learning machine for regression with non-convex loss function via DC program, Convergence study on the proximal alternating direction method with larger step size, Convergence analysis of the generalized Douglas-Rachford splitting method under Hölder subregularity assumptions, Image restoration based on the minimized surface regularization, Inexact alternating direction methods of multipliers with logarithmic-quadratic proximal regularization, A two-level distributed algorithm for nonconvex constrained optimization, Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints, A dual-primal balanced augmented Lagrangian method for linearly constrained convex programming, A proximal point algorithm revisit on the alternating direction method of multipliers, Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems, Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming, An adaptive primal-dual framework for nonsmooth convex minimization, A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints, Bregman reweighted alternating minimization and its application to image deblurring, A QCQP-based splitting SQP algorithm for two-block nonconvex constrained optimization problems with application, An incremental aggregated proximal ADMM for linearly constrained nonconvex optimization with application to sparse logistic regression problems, A linearized Peaceman-Rachford splitting method for structured convex optimization with application to stable principal component pursuit, A partially proximal S-ADMM for separable convex optimization with linear constraints, Douglas-Rachford splitting algorithm for solving state-dependent maximal monotone inclusions, Multi-block nonconvex nonsmooth proximal ADMM: convergence and rates under Kurdyka-Łojasiewicz property, Local linear convergence of an ADMM-type splitting framework for equality constrained optimization, An alternating direction method of multipliers for tensor complementarity problems, A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization, Convergence analysis of the generalized alternating direction method of multipliers with logarithmic-quadratic proximal regularization, Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems, A parallel primal-dual splitting method for image restoration, Linear Convergence of the Alternating Direction Method of Multipliers for a Class of Convex Optimization Problems, A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization, Generalized alternating direction method of multipliers: new theoretical insights and applications, An $\mathcal O(1/{k})$ Convergence Rate for the Variable Stepsize Bregman Operator Splitting Algorithm, Semisupervised data classification via the Mumford-Shah-Potts-type model, On Convergence Rates of Linearized Proximal Algorithms for Convex Composite Optimization with Applications, Communication-efficient algorithms for decentralized and stochastic optimization, Optimally linearizing the alternating direction method of multipliers for convex programming, Inertial proximal strictly contractive peaceman-Rachford splitting method with an indefinite term for convex optimization, A regularization parameter selection model for total variation based image noise removal, A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems, An ADMM numerical approach to linear parabolic state constrained optimal control problems, A sequential updating scheme of the Lagrange multiplier for separable convex programming, Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis, Randomized primal-dual proximal block coordinate updates, An LQP-based symmetric alternating direction method of multipliers with larger step sizes, Strictly contractive Peaceman-Rachford splitting method to recover the corrupted low rank matrix, A regularized alternating direction method of multipliers for a class of nonconvex problems, An ADMM-based SQP method for separably smooth nonconvex optimization, Phase Retrieval from Incomplete Magnitude Information via Total Variation Regularization, A partially inexact proximal alternating direction method of multipliers and its iteration-complexity analysis, New regularization models for image denoising with a spatially dependent regularization parameter, A prediction-correction dynamic method for large-scale generalized eigenvalue problems, Convergence analysis of the relaxed proximal point algorithm, On the optimal proximal parameter of an ADMM-like splitting method for separable convex programming, Sparsest piecewise-linear regression of one-dimensional data, Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence, An indefinite proximal Peaceman-Rachford splitting method with substitution procedure for convex programming, A superlinearly convergent splitting feasible sequential quadratic optimization method for two-block large-scale smooth optimization, Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization, On the pointwise iteration-complexity of a dynamic regularized ADMM with over-relaxation stepsize, On the nonexpansive operators based on arbitrary metric: a degenerate analysis, A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning