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

doi:10.1007/s40305-022-00417-5

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

CLC Number:

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.

TrendMD

References

[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)