We initially establish the O(1/K2) (K represents the number of iterations) ergodic convergence rate of the alternating direction method of multipliers (ADMM) with dual step size from 0 to 2 and dynamically updating the penalty parameter. The convergence rate is derived under the assumption that the two objective functions involved are linear and strongly convex, respectively. In contrast, there is no convergence rate analysis for ADMM with dual step size ranging from 0 to 2 and dynamically updating the penalty parameter. Furthermore, we analyze the convergence to the solution.
Tao Zhang
. On the O(1/K2) Ergodic Convergence of ADMM with Dual Step Size from 0 to 2[J]. Journal of the Operations Research Society of China, 2026
, 14(2)
: 521
-532
.
DOI: 10.1007/s40305-024-00568-7
[1] Boyd, S., Parikh, N., Chu, E., Peleato, B.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122(2011)
[2] Candés, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Thoery 52(2), 489–509(2006)
[3] Chen, L., Li, X., Sun, D., Toh, K.: On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. Math. Program. 185, 111–161(2021)
[4] Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318(1992)
[5] Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pacific J. Optim. 11(4), 619–644(2015)
[6] Fortin, M., Glowinski, R.: On Decomposition-coordination Methods Using an Augmented Lagrangian. Elsevier, New York (1983)
[7] 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)
[8] 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. Esaim-Math. Model. Num. 9(R2), 41–76(1975)
[9] He, B., Ma, F., Yuan, X.: Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imaging Sci. 9(3), 1467–1501(2016)
[10] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4(5), 303–320(1969)
[11] Kang, M., Kang, M., Jung, M.: Inexact accelerated augmented Lagrangian methods. Comput. Optim. App. 62(2), 373–404(2015)
[12] Ouyang, Y., Chen, Y., Lan, G., Pasiliao, E., Jr.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644–681(2015)
[13] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. Optimization, 283–298(1969)
[14] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116(1976)
[15] Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3), 1459–1484(2017)
[16] Yang, J., Zhang, Y., Yin, W.: A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data. IEEE J. Selec. Topics Sign. Proc. 2(4), 619–644(2015)
[17] Yin, W.: Analysis and generalizations of the linearized Bregman method. SIAM J. Imag. Sci. 3(4), 856–877(2010)
[18] Zhang, T., Xia, Y., Li, S.: Lagrangian-based methods in convex optimization: prediction- correction frameworks with ergodic convergence rates (2023). arXiv:2206.05088
