A Survey on Some Recent Developments of Alternating Direction Method of Multipliers

doi:10.1007/s40305-021-00368-3

摘要/Abstract

Abstract: Recently, alternating direction method of multipliers (ADMM) attracts much attentions from various fields and there are many variant versions tailored for different models. Moreover, its theoretical studies such as rate of convergence and extensions to nonconvex problems also achieve much progress. In this paper, we give a survey on some recent developments of ADMM and its variants.

Key words: Alternating direction method of multipliers, Global convergence, Rate of convergence, Nonconvex optimization

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 1-52.

De-Ren Han. A Survey on Some Recent Developments of Alternating Direction Method of Multipliers[J]. Journal of the Operations Research Society of China, 2022, 10(1): 1-52.

参考文献

[1] Peng, Y., Ganesh, A., Wright, J., Xu, W., Ma, Y.:RASL:robust alignment by sparse and lowrank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell. 34(11), 2233-2246(2012)
[2] Tao, M., Yuan, X.:Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1), 57-81(2011)
[3] Chandrasekaran,V., Parrilo, P.A.,Willsky, A.S.:Latent variable graphical model selection via convex optimization. Ann. Stat. 40(4), 1935-1967(2012)
[4] McLachlan, G.:Discriminant Analysis and Statistical Pattern Recognition, vol. 544. Wiley (2004)
[5] Li, M., Sun, D., Toh, K.-C.:A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block. Asia-Pac. J. Oper. Res. 32(04), 1550024(2015)
[6] Tibshirani, R.:Regression shrinkage and selection via the lasso. J. Roy. Stat. Soc.:Ser. B (Methodol.) 58(1), 267-288(1996)
[7] Rudin, L.I., Osher, S., Fatemi, E.:Nonlinear total variation based noise removal algorithms. Phys. D 60(1-4), 259-268(1992)
[8] Bruckstein, A.M., Donoho, D.L., Elad, M.:From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1), 34-81(2009)
[9] Huber, P.J.:Robust Statistics. Springer (2011)
[10] Yuan,M., Lin, Y.:Model selection and estimation in regression with grouped variables. J. Roy. Stat. Soc.:Ser. B (Stat. Methodol.) 68(1), 49-67(2006)
[11] Candès, E.J., Recht, B.:Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717-772(2009)
[12] Candès, E.J., Li, X., Ma, Y., Wright, J.:Robust principal component analysis? J. ACM (JACM) 58(3), 1-37(2011)
[13] Donoho, D.L.:De-noising by soft-thresholding. IEEE Trans. Inf. Theory 41(3), 613-627(1995)
[14] Donoho, D.L.:High-dimensional data analysis:the curses and blessings of dimensionality. AMS Math. Chall. Lect. 1-32, 375(2000)
[15] 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-122(2011)
[16] Glowinski, R.:On alternating directionmethods of multipliers:a historical perspective. In:Modeling, Simulation and Optimization for Science and Technology, pp. 59-82. Springer (2014)
[17] Glowinski, R., Marroco, A.:Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires", Revue française d'automatique, informatique, recherche opérationnelle. Analyse numérique 9(R2), 41-76(1975)
[18] Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17-40(1976)
[19] Gabay, D.:Applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299-331(1983)
[20] Eckstein, J., Yao, W.:Understanding the convergence of the alternating direction method of multipliers:theoretical and computational perspectives. Pac. J. Optim. 11(4), 619-644(2015)
[21] Chen, C., He, B., Ye, Y., Yuan, X.:The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1-2), 57-79(2016)
[22] Kurdyka, K.:On gradients of functions definable in o-minimal structures. Annales de l'institut Fourier 48, 769-783(1998)
[23] Lojasiewicz, S.:Une propri ét é topologique des sous-ensembles analytiques r éels, les É quations auxdérivées partielles. Les Éditions aux Dérivées Partielles 117, 87-89(1963)
[24] Hestenes, M.R.:Multiplier and gradient methods. J. Optim. Theory Appl. 4(5), 303-320(1969)
[25] Powell, M.J.:A method for nonlinear constraints in minimization problems. In:Fletcher, R. (ed.) Optimization, pp. 283-298. Academic Press (1969)
[26] Hong, M., Luo, Z.-Q.:On the linear convergence of the alternating direction method of multipliers. Math. Program. 162(1-2), 165-199(2017)
[27] Bertsekas, D.P., Nedi, A., Ozdaglar, A.E.:Convex Analysis and Optimization. Athena Scientific (2003)
[28] Rockafellar, R.T.:Convex Analysis. Princeton University Press (2015)
[29] Zhang, J.,Ge, S., Chang, T.-H., Luo, Z.-Q.:Decentralized non-convex learning with linearly coupled constraints. arXiv:2103.05378(2021)
[30] Eckstein, J., Bertsekas, D.P.:On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1-3), 293-318(1992)
[31] Ryu, E.K., Boyd, S.:Primer on monotone operator methods. Appl. Comput. Math. 15(1), 3-43(2016)
[32] Douglas, J., Rachford, H.:On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82(2), 421-439(1956)
[33] Rockafellar, R.T.:Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14(5), 877-898(1976)
[34] Rockafellar,R.:Monotone operators and augmented Lagrangian methods in nonlinear programming. In:Nonlinear Programming 3, pp. 1-25. Elsevier (1978)
[35] He, B., Yang, H.:Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Oper. Res. Lett. 23(3-5), 151-161(1998)
[36] Kontogiorgis, S., Meyer, R.R.:A variable-penalty alternating directions method for convex optimization. Math. Program. 83(1-3), 29-53(1998)
[37] He, B., Yang, H., Wang, S.:Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106(2), 337-356(2000)
[38] He, B., Liao, L.-Z., Han, D., Yang, H.:A new inexact alternating directions method for monotone variational inequalities. Math. Program. 92(1), 103-118(2002)
[39] Chan, R., Tao, M., Yuan, X.:Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers. SIAM J. Imag. Sci. 6(1), 680-697(2013)
[40] Han, D., He, H., Yang, H., Yuan, X.:A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints. Numer. Math. 127(1), 167-200(2014)
[41] Rockafellar, R.T.:Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97-116(1976)
[42] Eckstein, J., Fukushima, M.:Some reformulations and applications of the alternating direction method of multipliers. In:Large Scale Optimization, pp. 115-134. Springer (1994)
[43] Facchinei, F., Pang, J.S.:Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Science & Business Media, Berlin (2003)
[44] Lin, Z., Liu, R., Su, Z.:Linearized alternating direction method with adaptive penalty for low-rank representation. In:Advances in Neural Information Processing Systems, pp. 612-620(2011)
[45] Xu,M.,Wu, T.:A class of linearized proximal alternating directionmethods. J. Optim. Theory Appl. 151(2), 321-337(2011)
[46] Yang, J., Yuan, X.:Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82(281), 301-329(2013)
[47] Wang, X., Yuan, X.:The linearized alternating direction method of multipliers for Dantzig selector. SIAM J. Sci. Comput. 34(5), A2792-A2811(2012)
[48] Chen, G.,Teboulle, M.:Aproximal-based decompositionmethod for convexminimization problems. Math. Program. 64(1-3), 81-101(1994)
[49] Shefi, R., Teboulle, M.:Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization. SIAM J. Optim. 24(1), 269-297(2014)
[50] Han, D., He, B.:A new accuracy criterion for approximate proximal point algorithms. J.Math. Anal. Appl. 263(2), 343-354(2001)
[51] Solodov, M.V., Svaiter, B.F.:A hybrid projection-proximal point algorithm. J. Convex Anal. 6(1), 59-70(1999)
[52] Solodov, M.V., Svaiter, B.F.:A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal. 7(4), 323-345(1999)
[53] Han, D.:A new hybrid generalized proximal point algorithm for variational inequality problems. J. Global Optim. 26(2), 125-140(2003)
[54] He, B., Yang, Z., Yuan, X.:An approximate proximal-extragradient type method for monotone variational inequalities. J. Math. Anal. Appl. 300(2), 362-374(2004)
[55] Eckstein, J., Silva, P.J.:A practical relative error criterion for augmented Lagrangians. Math. Program. 141(1-2), 319-348(2013)
[56] Eckstein, J., Yao,W.:Approximate ADMM algorithms derived from Lagrangian splitting. Comput. Optim. Appl. 68(2), 363-405(2017)
[57] Eckstein, J.,Yao,W.:Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Math. Program. 170(2), 417-444(2018)
[58] Xie, J.:On inexactADMMswith relative error criteria. Comput.Optim.Appl. 71(3), 743-765(2018)
[59] Nesterov, Y.:Introductory Lectures on Convex Optimization:A Basic Course, vol. 87. Springer Science & Business Media, Berlin (2013)
[60] 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-709(2012)
[61] Monteiro, R.D., Svaiter, B.F.:Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475-507(2013)
[62] Cai, X., Han, D.:O(1/t) complexity analysis of the generalized alternating direction method of multipliers. Sci. China Math. 62(4), 795-808(2019)
[63] Ouyang,Y.,Chen,Y., Lan, G., Pasiliao, E., Jr.:An accelerated linearized alternating directionmethod of multipliers. SIAM J. Imag. Sci. 8(1), 644-681(2015)
[64] He, B., Yuan, X.:On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers. Numer. Math. 130(3), 567-577(2015)
[65] Deng, W., Yin, W.:On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916(2016)
[66] Gao, X., Jiang, B., Zhang, S.:On the information-adaptive variants of the ADMM:an iteration complexity perspective. J. Sci. Comput. 76(1), 327-363(2018)
[67] Gonçalves,M.L., Melo, J.G., Monteiro, R.D.:Improved pointwise iteration-complexity of a regularized ADMM and of a regularized non-Euclidean HPE framework. SIAM J. Optim. 27(1), 379-407(2017)
[68] Lions, P.-L., Mercier, B.:Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979(1979)
[69] Luque, F.J.:Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control. Optim. 22(2), 277-293(1984)
[70] Eckstein, J.:Splitting Methods for Monotone Operators with Applications to Parallel Optimization.PhD thesis, Massachusetts Institute of Technology (1989)
[71] Boley, D.:Local linear convergence of ADMM on quadratic or linear programs. SIAM J. Optim. 23(4), 2183-2207(2013)
[72] Han, D., Yuan, X.:Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numer. Anal. 51(6), 3446-3457(2013)
[73] Luo, Z.-Q., Tseng, P.:Error bounds and convergence analysis of feasible descent methods:a general approach. Ann. Oper. Res. 46(1), 157-178(1993)
[74] Zhu, T., Yu, Z.:A simple proof for some important properties of the projection mapping. Math. Inequal. Appl. 7, 453-456(2004)
[75] Yang, W.H., Han, D.:Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numer. Anal. 54(2), 625-640(2016)
[76] Zheng, X.Y., Ng, K.F.:Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization. SIAM J. Optim. 24(1), 154-174(2014)
[77] Sun, J.:On monotropic piecewise quadratic programming (network, algorithm, convex programming, decomposition method) Ph.D. Dissertation. University of Washington, USA. Order Number:AAI8706680(1986)
[78] Rockafellar, R.T.,Wets, R.J.-B.:Variational Analysis, vol. 317. Springer Science&BusinessMedia, Berlin (2009)
[79] Han, D., Sun, D., Zhang, L.:Linear rate convergence of the alternating directionmethod of multipliers for convex composite programming. Math. Oper. Res. 43(2), 622-637(2017)
[80] Dontchev, A.L., Rockafellar, R.T.:Implicit Functions and Solution Mappings, vol. 543. Springer (2009)
[81] Chang, T.-H., Hong, M., Wang, X.:Multi-agent distributed optimization via inexact consensus ADMM. IEEE Trans. Signal Process. 63(2), 482-497(2014)
[82] Shi,W.,Ling, Q.,Yuan, K.,Wu, G.,Yin,W.:On the linear convergence of theADMMin decentralized consensus optimization. IEEE Trans. Signal Process. 62(7), 1750-1761(2014)
[83] Han, D., Yuan, X.:A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155(1), 227-238(2012)
[84] Chen, C., Shen, Y., You, Y.:On the convergence analysis of the alternating direction method of multipliers with three blocks. Abstr. Appl. Anal. 2013,(2013)
[85] Lin, T., Ma, S., Zhang, S.:On the sublinear convergence rate of multi-block ADMM. J. Oper. Res. Soc. China 3(3), 251-274(2015)
[86] Cai, X., Han, D., Yuan, X.:On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput. Optim. Appl. 66(1), 39-73(2017)
[87] Lin, T.,Ma, S., Zhang, S.:On the global linear convergence of theADMMwith multiblock variables. SIAM J. Optim. 25(3), 1478-1497(2015)
[88] Bauschke, H.H., Combettes, P.L.:Convex Analysis and Monotone Operator Theory in Hilbert Spaces, vol. 408. Springer (2011)
[89] He,B., Tao, M.,Yuan, X.:Alternating directionmethod with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313-340(2012)
[90] Ye,C.,Yuan, X.:Adescentmethod for structuredmonotone variational inequalities.Optim.Methods Softw. 22(2), 329-338(2007)
[91] Han, D., Yuan, X., Zhang, W., Cai, X.:An ADM-based splitting method for separable convex programming. Comput. Optim. Appl. 54(2), 343-369(2013)
[92] Han, D.,Yuan, X., Zhang,W.:An augmented Lagrangian based parallel splittingmethod for separable convex minimization with applications to image processing. Math. Comput. 83(289), 2263-2291(2014)
[93] He, B.:Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities. Comput. Optim. Appl. 42(2), 195-212(2009)
[94] Wang, K., Han, D., Xu, L.:A parallel splitting method for separable convex programs. J. Optim. Theory Appl. 159(1), 138-158(2013)
[95] He, B., Hou, L., Yuan, X.:On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming. SIAM J. Optim. 25(4), 2274-2312(2015)
[96] Deng, W., Lai, M.-J., Peng, Z., Yin, W.:Parallel multi-block ADMM with o(1/k) convergence. J. Sci. Comput. 71(2), 712-736(2017)
[97] He, H., Han, D.:A distributed Douglas-Rachford splitting method for multi-block convex minimization problems. Adv. Comput. Math. 42(1), 27-53(2016)
[98] Cao, C., Han, D., Xu, L.:A new partial splitting augmented Lagrangian method for minimizing the sum of three convex functions. Appl. Math. Comput. 219(10), 5449-5457(2013)
[99] Hou, L., He, H., Yang, J.:A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA. Comput. Optim. Appl. 63(1), 273-303(2016)
[100] Han, D., Kong,W., Zhang,W.:A partial splitting augmented Lagrangian method for low patch-rank image decomposition. J. Math. Imag. Vis. 51(1), 145-160(2015)
[101] Attouch, H., Bolte, J., Redont, P., Soubeyran, A.:Proximal alternating minimization and projection methods for nonconvex problems:an approach based on the Kurdyka-Lojasiewicz inequality.Math. Oper. Res. 35(2), 438-457(2010)
[102] Attouch, H., Bolte, J., Svaiter, B.F.:Convergence of descent methods for semi-algebraic and tame problems:proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137(1-2), 91-129(2013)
[103] Bolte, J., Daniilidis, A., Lewis, A.:The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205-1223(2007)
[104] Bolte, J., Daniilidis, A., Lewis, A., Shiota, M.:Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556-572(2007)
[105] Mordukhovich, B.S.:Variational Analysis and Generalized Differentiation I:Basic Theory, vol. 330. Springer Science & Business Media, Berlin (2006)
[106] Absil, P.-A., Mahony, R., Andrews, B.:Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2), 531-547(2005)
[107] Attouch, H., Bolte, J.:On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1-2), 5-16(2009)
[108] Bolte, J.,Daniilidis, A., Ley, O., Mazet, L.:Characterizations of Lojasiewicz inequalities:subgradient flows, talweg, convexity. Trans. Am. Math. Soc. 362(6), 3319-3363(2010)
[109] Merlet, B., Pierre,M.:Convergence to equilibrium for the backward Euler scheme and applications. Commun. Pure Appl. Anal. 9(3), 685-702(2010)
[110] Noll, D.:Convergence of non-smooth descent methods using the Kurdyka-Lojasiewicz inequality. J. Optim. Theory Appl. 160(2), 553-572(2014)
[111] Chouzenoux, E., Pesquet, J.-C., Repetti, A.:Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J. Optim. Theory Appl. 162(1), 107-132(2014)
[112] Frankel, P., Garrigos, G., Peypouquet, J.:Splitting methods with variable metric for Kurdyka-Lojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3), 874-900(2015)
[113] Li, G., Pong, T.K.:Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4), 2434-2460(2015)
[114] Wang, F., Xu, Z., Xu, H.-K.:Convergence of bregman alternating direction method with multipliers for nonconvex composite problems. arXiv:1410.8625(2014)
[115] Guo, K., Han, D., Wu, T.:Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. Int. J. Comput. Math. 94(8), 1653-1669(2017)
[116] Bolte, J., Sabach, S., Teboulle, M.:Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1-2), 459-494(2014)
[117] Wang, Y., Yin,W., Zeng, J.:Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1), 29-63(2019)
[118] Jia, Z., Gao, X., Cai, X., Han, D.:Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems. J. Optim. Theory Appl. 188, 1-25(2021)
[119] Jiang, B., Lin, T., Ma, S., Zhang, S.:Structured nonconvex and nonsmooth optimization:algorithms and iteration complexity analysis. Comput. Optim. Appl. 72(1), 115-157(2019)
[120] Zhang, J., Luo, Z.-Q.:A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM J. Optim. 30(3), 2272-2302(2020)
[121] Guo, K., Han, D.,Wang, D.Z.,Wu, T.:Convergence ofADMMfor multi-block nonconvex separable optimization models. Front. Math. China 12(5), 1139-1162(2017)
[122] Guo, K., Han, D., Wu, T.:Convergence of ADMM for optimization problems with nonseparable nonconvex objective and linear constraints. Pac. J. Optim. 14(3), 489-506(2018)
[123] Hong, M., Luo, Z.-Q., Razaviyayn, M.:Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1), 337-364(2016)
[124] Bayram, I., Selesnick, I.W.:The Douglas-Rachford algorithm for weakly convex penalties. arXiv preprint arXiv:1511.03920(2015)
[125] Guo, K., Han, D., Yuan, X.:Convergence analysis of Douglas-Rachford splitting method for ‘strongly + weakly’ convex programming. SIAM J. Numer. Anal. 55(4), 1549-1577(2017)
[126] Guo, K., Han, D.:A note on the Douglas-Rachford splitting method for optimization problems involving hypoconvex functions. J. Glob. Optim. 72(3), 431-441(2018)
[127] Bayram, I.:Penalty functions derived from monotone mappings. IEEE Signal Process. Lett. 22(3), 265-269(2014)
[128] Chen, L., Gu, Y.:The convergence guarantees of a non-convex approach for sparse recovery. IEEE Trans. Signal Process. 62(15), 3754-3767(2014)
[129] Selesnick, I.W., Bayram, I.:Sparse signal estimation by maximally sparse convex optimization. IEEE Trans. Signal Process. 62(5), 1078-1092(2014)
[130] Guo, K., Yuan, X., Zeng, S.:Convergence analysis of ISTA and FISTA for ‘strongly + semi’ convex programming (2016)
[131] Fan, J., Li, R.:Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96(456), 1348-1360(2001)
[132] Zhang, C.-H.:Nearly unbiased variable selection under minimax concave penalty. Ann. Stat. 38(2), 894-942(2010)
[133] Li, G., Pong, T.K.:Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159(1-2), 371-401(2016)
[134] Mollenhoff, T., Strekalovskiy, E.,Moeller,M., Cremers, D.:The primal-dual hybrid gradientmethod for semiconvex splittings. SIAM J. Imag. Sci. 8(2), 827-857(2015)
[135] Goldstein, T., O'Donoghue, B., Setzer, S., Baraniuk, R.:Fast alternating direction optimization methods. SIAM J. Imag. Sci. 7(3), 1588-1623(2014)
[136] Tian, W., Yuan, X.:An alternating direction method of multipliers with a worst-case O(1/n²) convergence rate. Math. Comput. 88(318), 1685-1713(2019)