On the O(1/K2) Ergodic Convergence of ADMM with Dual Step Size from 0 to 2

doi:10.1007/s40305-024-00568-7

Abstract

Abstract: We initially establish the O(1/K²) (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.

Key words: Strongly convex, Alternating direction method of multipliers, Convergence rate

CLC Number:

Tao Zhang. On the O(1/K²) 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.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00568-7

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/521

References

[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

On the O(1/K²) Ergodic Convergence of ADMM with Dual Step Size from 0 to 2

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Bo-Wen Li, Bin Shi, Ya-Xiang Yuan. Linear Convergence of ISTA and FISTA [J]. Journal of the Operations Research Society of China, 2026, 14(2): 345-363.
[2]	Feng Xue. On the Metric Resolvent: Nonexpansiveness, Convergence Rates and Applications [J]. Journal of the Operations Research Society of China, 2025, 13(4): 966-988.
[3]	Jin-Bao Jian, Guo-Dong Ma, Xiao Xu, Dao-Lan Han. Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications [J]. Journal of the Operations Research Society of China, 2025, 13(1): 114-141.
[4]	Xue Zhang, Xiao-Qun Zhang. A Variable Metric Extrapolation Proximal Iterative Hard Thresholding Method [J]. Journal of the Operations Research Society of China, 2025, 13(1): 161-183.
[5]	Ke-Xin Sun, Zhong-Ming Wu, Neng Wan. A General Framework for Nonconvex Sparse Mean-CVaR Portfolio Optimization Via ADMM [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1022-1047.
[6]	Jie Jiang, Zhi-Ping Chen. Discrete Approximation and Convergence Analysis for a Class of Decision-Dependent Two-Stage Stochastic Linear Programs [J]. Journal of the Operations Research Society of China, 2024, 12(3): 649-679.
[7]	Peng-Jie Liu, Jin-Bao Jian, Hu Shao, Xiao-Quan Wang, Jia-Wei Xu, Xiao-Yu Wu. A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting: Convergence and Rate Analyses [J]. Journal of the Operations Research Society of China, 2024, 12(2): 298-340.
[8]	Peng-Jie Liu, Jin-Bao Jian, Bo He, Xian-Zhen Jiang. Convergence of Bregman Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization [J]. Journal of the Operations Research Society of China, 2023, 11(4): 707-733.
[9]	Xin-Xin Li, Xiao-Ya Zhang. A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers [J]. Journal of the Operations Research Society of China, 2023, 11(4): 941-955.
[10]	Hong-Mei Chen, Xing-Ju Cai, Ling-Ling Xu. Approximate Customized Proximal Point Algorithms for Separable Convex Optimization [J]. Journal of the Operations Research Society of China, 2023, 11(2): 383-408.
[11]	Ying Cui, Chao Ding, Xu-Dong Li, Xin-Yuan Zhao. Augmented Lagrangian Methods for Convex Matrix Optimization Problems [J]. Journal of the Operations Research Society of China, 2022, 10(2): 305-342.
[12]	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.
[13]	Jun-Feng Yang, Yin Zhang. Local Linear Convergence of an ADMM-Type Splitting Framework for Equality Constrained Optimization [J]. Journal of the Operations Research Society of China, 2021, 9(2): 308-319.
[14]	Zhong-Ming Wu, Min Li. An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes [J]. Journal of the Operations Research Society of China, 2019, 7(2): 365-383.
[15]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.