A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers

doi:10.1007/s40305-022-00417-5

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 941-955.doi: 10.1007/s40305-022-00417-5

收稿日期:2021-06-12 修回日期:2022-03-13 出版日期:2023-12-30 发布日期:2023-12-26
通讯作者: Xin-Xin Li, Xiao-Ya Zhang E-mail:xinxinli@jlu.edu.cn;xiaoyaz19@mails.jlu.edu.cn

A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers

Xin-Xin Li, Xiao-Ya Zhang

School of Mathematics, Jilin University, Changchun, 130012, Jilin, China

Received:2021-06-12 Revised:2022-03-13 Online:2023-12-30 Published:2023-12-26
Contact: Xin-Xin Li, Xiao-Ya Zhang E-mail:xinxinli@jlu.edu.cn;xiaoyaz19@mails.jlu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (Nos.11601183 and 61872162).

摘要/Abstract

Abstract: In this paper, we propose a new stopping criterion for Eckstein and Bertsekas’s generalized alternating direction method of multipliers. The stopping criterion is easy to verify, and the computational cost is much less than the classical stopping criterion in the highly influential paper by Boyd et al. (Found Trends Mach Learn 3(1):1-122, 2011).

Key words: Convex optimization, Generalized alternating direction method of multipliers, Proximal point algorithm, Stopping criterion

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2023, 11(4): 941-955.

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.

参考文献

[1] Glowinski, R., Marroco, A.: Sur läpproximation, par éléments finis dördre un, et la résolution, par pénalisation-dualité düne classe de problèmes de dirichlet non linéaires. Rev. Franc. Däutom., Inf., Rech. Opér. 9(R-2), 41-76 (1975)
[2] 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)
[3] Gabay, D.: Chapter IX applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15(C), 299-331 (1983)
[4] Eckstein, J., Bertsekas, D.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1-3), 293-318 (1992)
[5] Chen, L., Sun, D., Toh, K.: A note on the convergence of ADMM for linearly constrained convex optimization problems. Comput. Optim. Appl. 66, 327-343 (2017)
[6] 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 (2010)
[7] Eckstein, J., Wang, Y.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11(4), 619-644 (2015)
[8] Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. Comput. Methods Appl. Sci. 34, 59-82 (2014)
[9] Han, D.: A survey on some recent developments of alternating direction method of multipliers. J. Oper. Res. Soc. China (2022). https://doi.org/10.1007/s40305-021-00368-3
[10] Forero, P., Cano, A., Giannakis, G.B.: Consensus-based distributed support vector machines. J. Mach. Learn. Res. 11, 1663-1707 (2010)
[11] Figueiredo, M.A.T., Bioucas-Dias, J.M.: Restoration of Poissonian images using alternating direction optimization. IEEE Trans. Image Process. 19(12), 3133-3145 (2010)
[12] Ng, M., Weiss, P., Yuan, X.: Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods. SIAM J. Sci. Comput. 32(5), 2710-2736 (2010). https://doi.org/10.1137/090774823
[13] He, B., Xu, M., Yuan, X.: Solving large-scale least squares covariance matrix problems by alternating direction methods. SIAM J. Matrix Anal. Appl. 32(1), 136-152 (2011)
[14] Ng, M., Wang, F., Yuan, X.: Inexact alternating direction methods for image recovery. SIAM J. Sci. Comput. 33(4), 1643-1668 (2011). https://doi.org/10.1137/100807697
[15] Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. UCLA CAM Rep. 9, 31 (2009)
[16] Zhang, X., Burger, M., Osher, S.: A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1), 20-46 (2011). https://doi.org/10.1007/s10915-010-9408-8
[17] Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imag. Sci. 3(4), 1015-1046 (2010)
[18] Chen, C., Chan, R., Ma, S., Yang, J.: Inertial proximal ADMM for linearly constrained separable convex optimization. SIAM J. Imag. Sci. 8(4), 2239-2267 (2015)
[19] Ouyang, Y., Chen, Y., Lan, G., Pasiliao, E.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imag. Sci. 8(1), 644-681 (2015). https://doi.org/10.1137/14095697X
[20] Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Progr. 155(1-2), 57-79 (2016)
[21] Bot, R., Csetnek, E.: An inertial alternating direction method of multipliers. Minim. Theory Appl. 1(2), 29-49 (2016)
[22] 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)
[23] Yang, W., Han, D.: Linear convergence of alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numer. Anal. 54(2), 625-640 (2016)
[24] Han, D., Sun, D., Zhang, L.: Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2), 622-637 (2018)
[25] Liu, Y., Yuan, X., Zeng, S., Zhang, J.: Partial error bound conditions and the linear convergence rate of the alternating direction method of multipliers. SIAM J. Numer. Anal. 56(4), 2095-2123 (2018)
[26] Yuan, X.: Alternating direction method for covariance selection models. J. Sci. Comput. 51(2), 261-273 (2012)
[27] Fang, E., He, B., Liu, H., Yuan, X.: Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Progr. Comput. 7(2), 149-187 (2015)
[28] Xu, Z., Taylor, G., Li, H., Figueiredo, M.A., Yuan, X.M., Goldstein, T.: Adaptive consensus ADMM for distributed optimization. PMLR 70, 3841-3850 (2017)
[29] Chan, R., Yang, J., Yuan, X.: Alternating direction method for image inpainting in wavelet domains. SIAM J. Imag. Sci. 4(4), 807-826 (2011)
[30] Yang, J., Zhang, Y., Yin, W.: A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data. IEEE J. Sel. Top. Signal Process. 4(2), 288-297 (2010)
[31] Li, X., Pong, T., Sun, H., Wolkowicz, H.: A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem. Comput. Optim. Appl. 78(3), 853-891 (2021). https://doi.org/10.1007/s10589-020-00261-4
[32] Han, D., Yuan, X.: A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155(1), 227-238 (2012)
[33] 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)
[34] Martinet, B.: Régularisation inéquations variationnelles par approximations successives. Rev. Franc. Däutom., Inf., Rech. Opér. 4, 154-159 (1970)
[35] Rockafellar, R.T.: Monotone operatores and proximal point algorithm. SIAM J. Control. Optim. 14, 877-898 (1976)
[36] Eckstein, J.: Parallel alternating direction multiplier decomposition of convex programs. J. Optim. Theory Appl. 80, 39-62 (1994)
[37] Rockafellar, R.: Convex Analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)

A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价