The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
On the linear convergence of the alternating direction method of multipliers
Open accessAbstract
We analyze the convergence rate of the alternating direction method of multipliers (ADMM) for minimizing the sum of two or more nonsmooth convex separable functions subject to linear constraints. Previous analysis of the ADMM typically assumes that the objective function is the sum of only two convex functions defined on two separable blocks of variables even though the algorithm works well in numerical experiments for three or more blocks. Moreover, there has been no rate of convergence analysis for the ADMM without strong convexity in the objective function. In this paper we establish the global R-linear convergence of the ADMM for minimizing the sum of any number of convex separable functions, assuming that a certain error bound condition holds true and the dual stepsize is sufficiently small. Such an error bound condition is satisfied for example when the feasible set is a compact polyhedron and the objective function consists of a smooth strictly convex function composed with a linear mapping, and a nonsmooth ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document} regularizer. This result implies the linear convergence of the ADMM for contemporary applications such as LASSO without assuming strong convexity of the objective function.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Model Selection and Estimation in Regression with Grouped Variables
Yuan, M., & Lin, Y. (2006) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00532.x · Cited by 7,261
Iterative Solution of Nonlinear Equations in Several Variables
Ortega, J. M., & Rheinboldt, W. C. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719468 · Cited by 6,860
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Iterative Solution of Nonlinear Equations in Several Variables
I., E., Ortega, J. M., & Rheinboldt, W. C. (1971) · Mathematics of Computation · doi:10.2307/2004942 · Cited by 4,408
Eckstein, J., & Bertsekas, D. P. (1992) · Mathematical Programming · doi:10.1007/bf01581204 · Cited by 2,791
Bregman, L. M. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90040-7 · Cited by 2,618
A dual algorithm for the solution of nonlinear variational problems via finite element approximation
Gabay, D., & Mercier, B. (1976) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(76)90003-1 · Cited by 2,514
Splitting Algorithms for the Sum of Two Nonlinear Operators
Lions, P. L., & Mercier, B. (1979) · SIAM Journal on Numerical Analysis · doi:10.1137/0716071 · Cited by 1,972
On the numerical solution of heat conduction problems in two and three space variables
Douglas, J., & Rachford, H. H. (1956) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1956-0084194-4 · Cited by 1,744
Parlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
Numerical Methods for Nonlinear Variational Problems
Glowinski, R. (1984) · Springer eBooks · doi:10.1007/978-3-662-12613-4 · Cited by 1,728
Numerical Methods for Nonlinear Variational Problems
Glowinski, R., & Oden, J. T. (1985) · Journal of Applied Mechanics · doi:10.1115/1.3169136 · Cited by 1,541
Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
Yang, J., & Zhang, Y. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/090777761 · Cited by 1,201
Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics
Glowinski, R., & Tallec, P. L. (1989) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970838 · Cited by 1,015
Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics.
Oden, J. T., Glowinski, R., & Tallec, P. L. (1992) · Mathematics of Computation · doi:10.2307/2153048 · Cited by 972
On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction Method
He, B., & Yuan, X. (2012) · SIAM Journal on Numerical Analysis · doi:10.1137/110836936 · Cited by 881
Constrained minimization methods
Levitin, E. S., & Polyak, B. T. (1966) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(66)90114-5 · Cited by 846
Fast Alternating Direction Optimization Methods
Goldstein, T., O'Donoghue, B., Setzer, S., & Baraniuk, R. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/120896219 · Cited by 785
Chen, C., He, B., Ye, Y., & Yuan, X. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0826-5 · Cited by 719
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers
Deng, W., & Yin, W. (2016) · Journal of Scientific Computing · doi:10.1007/s10915-015-0048-x · Cited by 650
Convex programming in Hilbert space
Goldstein, A. A. (1964) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1964-11178-2 · Cited by 633
On the convergence of the coordinate descent method for convex differentiable minimization
Luo, Z. Q., & Tseng, P. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00939948 · Cited by 502
Self-citationRecovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
Tao, M., & Yuan, X. (2011) · SIAM Journal on Optimization · doi:10.1137/100781894 · Cited by 453
Chapter IX Applications of the Method of Multipliers to Variational Inequalities
Gabay, D. (1983) · Studies in mathematics and its applications · doi:10.1016/s0168-2024(08)70034-1 · Cited by 422
Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
He, B., Tao, M., & Yuan, X. (2012) · SIAM Journal on Optimization · doi:10.1137/110822347 · Cited by 360
Projection methods for variational inequalities with application to the traffic assignment problem
Bertsekas, D. P., & Gafni, E. M. (1982) · Mathematical Programming Studies · doi:10.1007/bfb0120965 · Cited by 333
Splitting methods for monotone operators with applications to parallel optimization
Eckstein, J. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 250
Fast alternating linearization methods for minimizing the sum of two convex functions
Goldfarb, D., Ma, S., & Scheinberg, K. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0530-2 · Cited by 246
Approximation accuracy, gradient methods, and error bound for structured convex optimization
Tseng, P. (2010) · Mathematical Programming · doi:10.1007/s10107-010-0394-2 · Cited by 224
On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
Luo, Z.-Q., & Tseng, P. (1992) · SIAM Journal on Control and Optimization · doi:10.1137/0330025 · Cited by 190
Self-citationMonteiro, R. D. C., & Svaiter, B. F. (2013) · SIAM Journal on Optimization · doi:10.1137/110849468 · Cited by 188
Boley, D. L. (2013) · SIAM Journal on Optimization · doi:10.1137/120878951 · Cited by 150
A variable-penalty alternating directions method for convex optimization
Kontogiorgis, S. A., & Meyer, R. R. (1998) · Mathematical Programming · doi:10.1007/bf02680549 · Cited by 144
The Linearized Alternating Direction Method of Multipliers for Dantzig Selector
Wang, X., & Yuan, X. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/110833543 · Cited by 123
Iterative Methods for Large Convex Quadratic Programs: A Survey
Lin, Y., & Pang, J. (1987) · SIAM Journal on Control and Optimization · doi:10.1137/0325023 · Cited by 123
General Projective Splitting Methods for Sums of Maximal Monotone Operators
Eckstein, J., & Svaiter, B. F. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/070698816 · Cited by 94
Fast Multiple-Splitting Algorithms for Convex Optimization
Goldfarb, D., & Ma, S. (2012) · SIAM Journal on Optimization · doi:10.1137/090780705 · Cited by 90
Alternating Proximal Gradient Method for Convex Minimization
Ma, S. (2015) · Journal of Scientific Computing · doi:10.1007/s10915-015-0150-0 · Cited by 76
On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
Luo, Z.-Q. T., & Tseng, P. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.4.846 · Cited by 74
Self-citation
Cited by
LIME: Low-Light Image Enhancement via Illumination Map Estimation
Guo, X., Li, Y., & Ling, H. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2639450 · Cited by 2,998
On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
Shi, W., Ling, Q., Yuan, K., Wu, G., & Yin, W. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2304432 · Cited by 820
Fast Alternating Direction Optimization Methods
Goldstein, T., O'Donoghue, B., Setzer, S., & Baraniuk, R. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/120896219 · Cited by 785
Robust Multi-View Spectral Clustering via Low-Rank and Sparse Decomposition
Xia, R., Pan, Y., Du, L., & Yin, J. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8950 · Cited by 713
On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers
Deng, W., & Yin, W. (2016) · Journal of Scientific Computing · doi:10.1007/s10915-015-0048-x · Cited by 650
Metadata
- Authors
- Hong, M., & Luo, Z.-Q.
- Venue
- Mathematical Programming
- Published
- 2016-07-06
- Volume
- 162
- Issue
- 1-2
- Pages
- 165-199
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2105693192
- Cited by
- 690
- References
- 43
- FWCI
- 75.62
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.