{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T11:04:19Z","timestamp":1770548659681,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T00:00:00Z","timestamp":1566345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T00:00:00Z","timestamp":1566345600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1719549"],"award-info":[{"award-number":["DMS-1719549"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s10107-019-01425-9","type":"journal-article","created":{"date-parts":[[2019,8,21]],"date-time":"2019-08-21T13:02:55Z","timestamp":1566392575000},"page":"199-244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":53,"title":["Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming"],"prefix":"10.1007","volume":"185","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4163-3723","authenticated-orcid":false,"given":"Yangyang","family":"Xu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,21]]},"reference":[{"key":"1425_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/0471787779","volume-title":"Nonlinear Programming: Theory and Algorithms","author":"MS Bazaraa","year":"2006","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (2006)"},{"issue":"1","key":"1425_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"issue":"2","key":"1425_CR3","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/S1052623493259215","volume":"7","author":"A Ben-Tal","year":"1997","unstructured":"Ben-Tal, A., Zibulevsky, M.: Penalty\/barrier multiplier methods for convex programming problems. SIAM J. Optim. 7(2), 347\u2013366 (1997)","journal-title":"SIAM J. Optim."},{"key":"1425_CR4","doi-asserted-by":"crossref","unstructured":"Bertsekas, D.P.: Convergence rate of penalty and multiplier methods. In: 1973 IEEE Conference on Decision and Control Including the 12th Symposium on Adaptive Processes, vol. 12, pp. 260\u2013264. IEEE (1973)","DOI":"10.1109\/CDC.1973.269172"},{"key":"1425_CR5","volume-title":"Nonlinear Programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)"},{"key":"1425_CR6","volume-title":"Constrained Optimization and Lagrange Multiplier Methods","author":"DP Bertsekas","year":"2014","unstructured":"Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic press, London (2014)"},{"issue":"1","key":"1425_CR7","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10589-005-1066-7","volume":"31","author":"EG Birgin","year":"2005","unstructured":"Birgin, E.G., Castillo, R., Mart\u00ednez, J.M.: Numerical comparison of augmented lagrangian algorithms for nonconvex problems. Comput. Optim. Appl. 31(1), 31\u201355 (2005)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1425_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach Learn."},{"key":"1425_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"3","key":"1425_CR10","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1007\/s10915-015-0048-x","volume":"66","author":"W Deng","year":"2016","unstructured":"Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889\u2013916 (2016)","journal-title":"J. Sci. Comput."},{"issue":"2","key":"1425_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s40305-018-0232-4","volume":"7","author":"X Gao","year":"2019","unstructured":"Gao, X., Xu, Y., Zhang, S.: Randomized primal-dual proximal block coordinate updates. J. Oper. Res. Soc. China 7(2), 205\u2013250 (2019)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1425_CR12","doi-asserted-by":"crossref","unstructured":"Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. In: Fitzgibbon, W., Kuznetsov, Y., Neittaanm\u00e4ki, P., Pironneau, O. (eds.) Modeling, Simulation and Optimization for Science and Technology. Computational Methods in Applied Sciences, vol. 34. Springer, Dordrecht (2014)","DOI":"10.1007\/978-94-017-9054-3_4"},{"key":"1425_CR13","unstructured":"Grant, M., Boyd, S., Ye, Y.: CVX: Matlab Software for Disciplined Convex Programming (2008)"},{"issue":"2","key":"1425_CR14","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0329022","volume":"29","author":"O G\u00fcler","year":"1991","unstructured":"G\u00fcler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29(2), 403\u2013419 (1991)","journal-title":"SIAM J. Control Optim."},{"issue":"4","key":"1425_CR15","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1137\/0802032","volume":"2","author":"O G\u00fcler","year":"1992","unstructured":"G\u00fcler, O.: New proximal point algorithms for convex minimization. SIAM J. Optim. 2(4), 649\u2013664 (1992)","journal-title":"SIAM J. Optim."},{"key":"1425_CR16","unstructured":"Hamedani, E.Y., Aybat, N.S.: A primal-dual algorithm for general convex-concave saddle point problems. arXiv preprint arXiv:1803.01401 (2018)"},{"key":"1425_CR17","unstructured":"He, B., Yuan, X.: On the acceleration of augmented Lagrangian method for linearly constrained optimization. Optimization Online (2010)"},{"issue":"2","key":"1425_CR18","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110836936","volume":"50","author":"B He","year":"2012","unstructured":"He, B., Yuan, X.: On the $${O}(1\/n)$$ convergence rate of the douglas-rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700\u2013709 (2012)","journal-title":"SIAM J. Numer. Anal."},{"issue":"5","key":"1425_CR19","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF00927673","volume":"4","author":"MR Hestenes","year":"1969","unstructured":"Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4(5), 303\u2013320 (1969)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"1425_CR20","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s10589-015-9742-8","volume":"62","author":"M Kang","year":"2015","unstructured":"Kang, M., Kang, M., Jung, M.: Inexact accelerated augmented Lagrangian methods. Comput. Optim. Appl. 62(2), 373\u2013404 (2015)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1425_CR21","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s10915-013-9686-z","volume":"56","author":"M Kang","year":"2013","unstructured":"Kang, M., Yun, S., Woo, H., Kang, M.: Accelerated bregman method for linearly constrained $$\\ell _1$$-$$\\ell _2$$ minimization. J. Sci. Comput. 56(3), 515\u2013534 (2013)","journal-title":"J. Sci. Comput."},{"issue":"1\u20132","key":"1425_CR22","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-015-0861-x","volume":"155","author":"G Lan","year":"2016","unstructured":"Lan, G., Monteiro, R.D.: Iteration-complexity of first-order augmented lagrangian methods for convex programming. Math. Program. 155(1\u20132), 511\u2013547 (2016)","journal-title":"Math. Program."},{"key":"1425_CR23","unstructured":"Li, Z., Xu, Y.: First-order inexact augmented lagrangian methods for convex and nonconvex programs: nonergodic convergence and iteration complexity. Preprint (2019)"},{"issue":"1","key":"1425_CR24","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/s10915-016-0182-0","volume":"69","author":"T Lin","year":"2016","unstructured":"Lin, T., Ma, S., Zhang, S.: Iteration complexity analysis of multi-block admm for a family of convex minimization without strong convexity. J. Sci. Comput. 69(1), 52\u201381 (2016)","journal-title":"J. Sci. Comput."},{"issue":"2","key":"1425_CR25","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1287\/moor.2018.0939","volume":"44","author":"Y-F Liu","year":"2019","unstructured":"Liu, Y.-F., Liu, X., Ma, S.: On the non-ergodic convergence rate of an inexact augmented lagrangian framework for composite convex programming. Math. Oper. Res. 44(2), 632\u2013650 (2019)","journal-title":"Math. Oper. Res."},{"key":"1425_CR26","unstructured":"Lu, Z., Zhou, Z.: Iteration-complexity of first-order augmented lagrangian methods for convex conic programming. ArXiv preprint arXiv:1803.09941 (2018)"},{"issue":"2","key":"1425_CR27","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1137\/110849468","volume":"23","author":"RD Monteiro","year":"2013","unstructured":"Monteiro, R.D., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(2), 475\u2013507 (2013)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"1425_CR28","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1109\/TAC.2013.2294614","volume":"59","author":"I Necoara","year":"2014","unstructured":"Necoara, I., Nedelcu, V.: Rate analysis of inexact dual first-order methods application to dual decomposition. IEEE Trans. Autom. Control 59(5), 1232\u20131243 (2014)","journal-title":"IEEE Trans. Autom. Control"},{"issue":"5","key":"1425_CR29","doi-asserted-by":"publisher","first-page":"3109","DOI":"10.1137\/120897547","volume":"52","author":"V Nedelcu","year":"2014","unstructured":"Nedelcu, V., Necoara, I., Tran-Dinh, Q.: Computational complexity of inexact gradient augmented lagrangian methods: application to constrained mpc. SIAM J. Control Optim. 52(5), 3109\u20133134 (2014)","journal-title":"SIAM J. Control Optim."},{"issue":"4","key":"1425_CR30","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1137\/070708111","volume":"19","author":"A Nedi\u0107","year":"2009","unstructured":"Nedi\u0107, A., Ozdaglar, A.: Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J. Optim. 19(4), 1757\u20131780 (2009)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1425_CR31","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s10957-009-9522-7","volume":"142","author":"A Nedi\u0107","year":"2009","unstructured":"Nedi\u0107, A., Ozdaglar, A.: Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142(1), 205\u2013228 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"1425_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publisher, Norwell (2004)"},{"issue":"1","key":"1425_CR33","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013)","journal-title":"Math. Program."},{"issue":"1","key":"1425_CR34","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1137\/14095697X","volume":"8","author":"Y Ouyang","year":"2015","unstructured":"Ouyang, Y., Chen, Y., Lan, G., Pasiliao Jr., E.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644\u2013681 (2015)","journal-title":"SIAM J. Imaging Sci."},{"key":"1425_CR35","doi-asserted-by":"crossref","unstructured":"Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. ArXiv preprint arXiv:1808.02901 (2018)","DOI":"10.1007\/s10107-019-01420-0"},{"key":"1425_CR36","volume-title":"Optimization","author":"MJ Powell","year":"1969","unstructured":"Powell, M.J.: A method for non-linear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization. Academic Press, New York (1969)"},{"issue":"1","key":"1425_CR37","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF01580138","volume":"5","author":"RT Rockafellar","year":"1973","unstructured":"Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5(1), 354\u2013373 (1973)","journal-title":"Math. Program."},{"issue":"6","key":"1425_CR38","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF00934777","volume":"12","author":"RT Rockafellar","year":"1973","unstructured":"Rockafellar, R.T.: The multiplier method of hestenes and powell applied to convex programming. J. Optim. Theory Appl. 12(6), 555\u2013562 (1973)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"1425_CR39","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/moor.1.2.97","volume":"1","author":"RT Rockafellar","year":"1976","unstructured":"Rockafellar, R.T.: Augmented lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97\u2013116 (1976)","journal-title":"Math. Oper. Res."},{"key":"1425_CR40","unstructured":"Schmidt, M., Roux, N.L., Bach, F.R.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Advances in Neural Information Processing Systems, pp. 1458\u20131466 (2011)"},{"issue":"1","key":"1425_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580598","volume":"60","author":"P Tseng","year":"1993","unstructured":"Tseng, P., Bertsekas, D.P.: On the convergence of the exponential multiplier method for convex programming. Math. Program. 60(1), 1\u201319 (1993)","journal-title":"Math. Program."},{"issue":"3","key":"1425_CR42","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1137\/16M1082305","volume":"27","author":"Y Xu","year":"2017","unstructured":"Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3), 1459\u20131484 (2017)","journal-title":"SIAM J. Optim."},{"key":"1425_CR43","unstructured":"Xu, Y.: Primal-dual stochastic gradient method for convex programs with many functional constraints. ArXiv preprint arXiv:1802.02724 (2018)"},{"issue":"1","key":"1425_CR44","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10589-018-0037-8","volume":"72","author":"Y Xu","year":"2019","unstructured":"Xu, Y.: Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs. Comput. Optim. Appl. 72(1), 87\u2013113 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1425_CR45","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1137\/120887795","volume":"6","author":"Y Xu","year":"2013","unstructured":"Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758\u20131789 (2013)","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"1425_CR46","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10589-017-9972-z","volume":"70","author":"Y Xu","year":"2018","unstructured":"Xu, Y., Zhang, S.: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70(1), 91\u2013128 (2018)","journal-title":"Comput. Optim. Appl."},{"key":"1425_CR47","doi-asserted-by":"crossref","unstructured":"Yu, H., Neely, M.J.: A primal-dual type algorithm with the $${O} (1\/t)$$ convergence rate for large scale constrained convex programs. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1900\u20131905. IEEE (2016)","DOI":"10.1109\/CDC.2016.7798542"},{"issue":"2","key":"1425_CR48","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/16M1059011","volume":"27","author":"H Yu","year":"2017","unstructured":"Yu, H., Neely, M.J.: A simple parallel algorithm with an $${O}(1\/t)$$ convergence rate for general convex programs. SIAM J. Optim. 27(2), 759\u2013783 (2017)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01425-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01425-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01425-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,26]],"date-time":"2022-09-26T01:43:22Z","timestamp":1664156602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01425-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,21]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["1425"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01425-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,21]]},"assertion":[{"value":"24 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}