{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T08:45:47Z","timestamp":1789721147036,"version":"4.0.1"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of $N$ convex functions whose variables are linked by some linear constraints. While the convergence of the ADMM for $N=2$ was well established in the literature, it remained an open problem for a long time whether the ADMM for $N \\ge 3$ is still convergent. Recently, it was shown in [Chen et al., Math. Program. (2014), DOI 10.1007\/s10107-014-0826-5.] that without additional conditions the ADMM for $N\\ge 3$ generally fails to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when $N\\geq 3$ can still be ensured, which is important since the ADMM is a popular method for solving large-scale multiblock optimization models and is known to perform very well in practice even when $N\\ge 3$. Our study aims to offer an explanation for this phenomenon.<\/jats:p>","DOI":"10.1137\/140971178","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T14:52:09Z","timestamp":1438267929000},"page":"1478-1497","source":"Crossref","is-referenced-by-count":121,"title":["On the Global Linear Convergence of the ADMM  with MultiBlock Variables"],"prefix":"10.1137","volume":"25","author":[{"given":"Tianyi","family":"Lin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shiqian","family":"Ma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,30]]},"reference":[{"key":"atypb1","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis,\n                      Parallel and Distributed Computation: Numerical Methods\n                      , Prentice-Hall, Upper Saddle River, NJ, 1989."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/120878951"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb4","unstructured":"X. Cai, D. Han, and X. Yuan,\n                      The Direct Extension of ADMM for Three-Block Separable Convex Minimization Models Is Convergent When One Function Is Strongly Convex\n                      , preprint, http:\/\/www.optimization-online.org\/DB_HTML\/2014\/11\/4644.html (2014)."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"C. Chen, B. He, Y. Ye, and X. Yuan,\n                      The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent\n                      , Math. Program. (2014), DOI 10.1007\/s10107-014-0826-5.","DOI":"10.1007\/s10107-014-0826-5"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"C. Chen, Y. Shen, and Y. You,\n                      On the convergence analysis of the alternating direction method of multipliers with three blocks\n                      , Abstract Appl. Anal. (2013), 183961.","DOI":"10.1155\/2013\/183961"},{"key":"atypb7","unstructured":"D. Davis and W. Yin,\n                      Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM under Regularity Assumptions\n                      , CAM Report 14-58, UCLA, 2014."},{"key":"atypb8","unstructured":"D. Davis and W. Yin,\n                      A Three-Operator Splitting Scheme and Its Optimization Applications\n                      , Technical report, CAM Report 15-13, UCLA, 2015."},{"key":"atypb9","unstructured":"W. Deng, M. Lai, Z. Peng, and W. Yin,\n                      Parallel Multi-Block ADMM with $o(1\/k)$ Convergence\n                      , Technical report, CAM Report 13-64, UCLA, 2013."},{"key":"atypb10","doi-asserted-by":"publisher","unstructured":"W. Deng and W. Yin,\n                      On the global and linear convergence of the generalized alternating direction method of multipliers\n                      , J. Sci. Comput. (2015), DOI:10.1007\/s10915-015-0048-x.","DOI":"10.1007\/s10915-015-0048-x"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0084194-4"},{"key":"atypb12","unstructured":"J. Eckstein,\n                      Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results\n                      , preprint, http:\/\/www.optimization-online.org\/DB_HTML\/2012\/12\/3704.html (2012)."},{"key":"atypb13","unstructured":"J. Eckstein and D. P. Bertsekas,\n                      An Alternating Direction Method for Linear Programming\n                      , Technical report, MIT Laboratory for Information and Decision Systems, 1990."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"},{"key":"atypb15","unstructured":"D. Gabay,\n                      Applications of the method of multipliers to variational inequalities\n                      , in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, M. Fortin and R. Glowinski, eds., North-Holland, Amsterdam, 1983."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. Glowinski and A. Marrocco,\n                      Sur l'approximation par e\u0301le\u0301ments finis et la re\u0301solution par pe\u0301nalisation-dualite\u0301 d'une classe de proble\u0300mes de Dirichlet non line\u0301aires\n                      , RAIRO, R2, (1975), pp. 41-76.","DOI":"10.1051\/m2an\/197509R200411"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/090780705"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-012-0003-z"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/120886753"},{"key":"atypb21","unstructured":"B. He, L. Hou, and X. Yuan,\n                      On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming\n                      , preprint, http:\/\/www.optimization-online.org\/DB_HTML\/2013\/05\/3894.html (2013)."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/110822347"},{"key":"atypb23","unstructured":"B. He, M. Tao, and X. Yuan,\n                      Convergence Rate and Iteration Complexity on the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming\n                      , preprint, http:\/\/www.optimization-online.org\/DB_FILE\/2012\/09\/3611.pdf (2013)."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-014-0673-6"},{"key":"atypb26","unstructured":"M. Hong and Z. Luo,\n                      On the Linear Convergence of the Alternating Direction Method of Multipliers\n                      , arXiv:1208.3922, 2012."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500244"},{"key":"atypb28","doi-asserted-by":"publisher","unstructured":"T. Lin, S. Ma, and S. Zhang,\n                      On the sublinear convergence rate of multi-block ADMM\n                      , J. Oper. Res. Soc. China (2015), DOI:10.1007\/s40305-015-0092-0.","DOI":"10.1007\/s40305-015-0092-0"},{"key":"atypb29","unstructured":"T. Lin, S. Ma, and S. Zhang,\n                      Global Convergence of Unmodified\n                      3\n                      -Block ADMM for a Class of Convex Minimization Problems\n                      , arXiv:1505.04252, 2015."},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"T. Lin, S. Ma, and S. Zhang,\n                      Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization Without Strong Convexity\n                      , arXiv:1504.03087, 2015.","DOI":"10.1007\/s10915-016-0182-0"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0802004"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"atypb34","unstructured":"The MOSEK Optimization Tools\n                      , Version 6, MOSEK ApS, Copenhagen, 2009."},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"P. Samadi, A. Mohsenian-Rad, R. Schober, V. W. S. Wong, and J. Jatskevich,\n                      Optimal real-time pricing algorithm based on utility maximization for smart grid\n                      , in Proceedings of the IEEE International Conference on Smart Grid Communications, 2010.","DOI":"10.1109\/SMARTGRID.2010.5622077"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/140964357"},{"key":"atypb37","unstructured":"R. Sun, Z.Q. Luo, and Y. Ye,\n                      On the Expected Convergence of Randomly Permuted ADMM\n                      , arXiv:1503.06387, 2015."},{"key":"atypb38","unstructured":"X. Wang, M. Hong, S. Ma, and Z.Q. Luo,\n                      Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers\n                      , arXiv:1308.5294, 2013."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/090777761"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140971178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:12Z","timestamp":1787336112000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140971178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140971178"],"URL":"https:\/\/doi.org\/10.1137\/140971178","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}