A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting: Convergence and Rate Analyses

doi:10.1007/s40305-023-00535-8

Abstract

Abstract: This work explores a family of two-block nonconvex optimization problems subject to linear constraints. We first introduce a simple but universal Bregman-style improved alternating direction method of multipliers (ADMM) based on the iteration framework of ADMM and the Bregman distance. Then, we utilize the smooth performance of one of the components to develop a linearized version of it. Compared to the traditional ADMM, both proposed methods integrate a convex combination strategy into the multiplier update step. For each proposed method, we demonstrate the convergence of the entire iteration sequence to a unique critical point of the augmented Lagrangian function utilizing the powerful Kurdyka–Łojasiewicz property, and we also derive convergence rates for both the sequence of merit function values and the iteration sequence. Finally, some numerical results show that the proposedmethods are effective and encouraging for the Lasso model.

Key words: Nonconvex optimization, Alternating direction method of multipliers, Kurdyka–Łojasiewicz property, Convergence rate

CLC Number:

90C26
90C30

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.

TrendMD

References

[1] Yang, L.F., Luo, J.Y., Xu, Y., Zhang, Z.R., Dong, Z.Y.:A distributed dual consensus ADMM based on partition for DC-DOPF with carbon emission trading. IEEE Trans. Industr. Inform. 16(3), 1858-1872(2020)
[2] Yang, L.F., Yang, Y., Chen, G., Dong, Z.Y.:Distributionally robust framework and its approximations based on vector and region split for self-scheduling of generation companies. IEEE Trans. Industr. Inform. 18(8), 5231-5241(2022)
[3] Jian, J.B., Zhang, C., Yin, J.H., Yang, L.F., Ma, G.D.:Monotone splitting sequential quadratic optimization algorithm with applications in electric power systems. J. Optim. Theory Appl. 186, 226-247(2020)
[4] Fan, Y.R., Buccini, A., Donatelli, M., Huang, T.Z.:A non-convex regularization approach for compressive sensing. Adv. Comput. Math. 45, 563-588(2019)
[5] Zeng, J.S., Xu, Z.B., Zhang, B.C., Hong, W., Wu, Y.R.:Accelerated L_1/2 regularization based SAR imaging via BCR and reduced Newton skills. Signal Process. 93, 1831-1844(2013)
[6] Xu, Z.B., Chang, X.Y., Xu, F.M., Zhang, H.:L_1/2 regularization:a thresholding representation theory and a fast solver. IEEE Trans. Neural Netw. Learn. Syst. 23(7), 1013-1027(2012)
[7] Liu, Z.Y., Chen, X.Y., Hu, J.T., Wang, S.A., Zhang, K., Zhang, H.G.:An alternating direction method of multipliers for solving user equilibrium problem. Eur. J. Oper. Res. 310(3), 1072-1084(2023)
[8] Shao, H., Lam,W.H.K., Tam,M.L.:Areliability-based stochastic traffic assignmentmodelfor network with multiple user classes under uncertainty in demand. Netw. Spat. Econ. 6(3-4), 173-204(2006)
[9] 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. Anal. Num. 9(R2), 41-76(1975)
[10] 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)
[11] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.:Distributed optimization and statistical learning with the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1-122(2011)
[12] Glowinski, R.:On Alternating Direction Methods of Multipliers:A Historical Perspective. Springer, Dordrecht (2014)
[13] Han, D.R.:A survey on some recent developments of alternating direction method of multipliers. J. Oper. Res. Soc. China 10, 1-52(2022)
[14] Han, D.R., Sun, D.F., Zhang, L.W.:Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2), 622-637(2017)
[15] Han, D.R., Yuan, X.M.:A note on the alternating direction method of multipliers. J. Optim. Theory Appl. 155, 227-238(2012)
[16] Chen, C.H., Chan, R.H., Ma, S.Q., Yang, J.F.:Inertial proximal ADMM for linearly constrained separable convex optimization. SIAM J. Imaging Sci. 8(4), 2239-2267(2015)
[17] Chen, C.H., Li, M., Yuan, X.M.:Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization. J. Optim. Theory Appl. 166, 906-929(2015)
[18] Chen, C.H., Li, M., Liu, X., Ye, Y.Y.:Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms:Convergence analysis and insights. Math. Program. 173, 37-77(2019)
[19] Li, P.X., Shen, Y., Jiang, S.H., Liu, Z.H., Chen, C.H.:Convergence study on strictly contractive Peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms. Comput. Optim. Appl. 78, 87-124(2021)
[20] Deng, W., Yin, W.T.:On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66, 889-916(2015)
[21] Hager, W.W., Yashtini, M., Zhang, H.:An O (1/k) convergence rate for the variable Stepsize Bregman operator splitting algorithm. SIAM J. Numer. Anal. 53, 1535-1556(2016)
[22] Hong, M.Y., Luo, Z.Q.:On the linear convergence of the alternating direction method of multipliers. Math. Program. 162, 165-199(2017)
[23] Gu, Y., Jiang, B., Han, D.R.:An indefinite-proximal-based strictly contractive Peaceman-Rachford splitting method. J. Comput. Math. 41, 1017-1040(2022)
[24] Lin, T.Y., Ma, S.Q., Zhang, S.Z.:On the sublinear convergence rate of multi-block ADMM. J. Oper. Res. Soc. China 3, 251-274(2015)
[25] Wu, Z.M., Li, M.:An LQP-based symmetric alternating direction method of multipliers with larger step sizes. J. Oper. Res. Soc. China 7, 365-383(2019)
[26] Gao, X., Zhang, S.Z.:First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5, 131-159(2017)
[27] Gao, X., Zhang, S.Z., Xu, Y.Y.:Randomized primal-dual proximal block coordinate updates. J. Oper. Res. Soc. China 7, 205-250(2019)
[28] Lin, T.Y., Ma, S.Q., Zhang, S.Z.:On the global linear convergence of the ADMM with multiblock variables. SIAM J. Optim. 25(3), 1249-1963(2015)
[29] Ling, Q., Shi, W., Wu, G., Ribeiro, A.:DLM:Decentralized linearized alternating direction method of multipliers. IEEE Trans. Signal Process. 63(15), 4051-4064(2015)
[30] Ouyang, Y.Y., Chen, Y.M., Lan, G.H., Pasiliao, E., Jr.:An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644-681(2015)
[31] Qiao, L.B., Zhang, B.F., Su, J.S., Lu, X.C.:Linearized alternating direction method of multipliers for constrained nonconvex regularized optimization. Proc. 8th Asian Conf. Mach. Learn. 63, 97-109(2016)
[32] Guo, K., Han, D.R., Wu, T.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)
[33] Yashtini, M.:Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization. J. Glob. Optim. 84, 913-939(2022)
[34] Liu, P.J., Jian, J.B., Xu, J.W., Ma, G.D.:A linear approximation Bregman-type Peaceman-Rachford splitting method for nonconvex nonseparable optimization (in Chinese). Acta. Math. Sin. 66(01), 75-94(2023)
[35] Jia, Z.H., Gao, X., Cai, X.J., Han, D.R.:Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems. J. Optim. Theory Appl. 188, 1-25(2021)
[36] Jia, Z.H., Gao, X., Cai, X.J., Han, D.R.:The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. J. Ind. Manag. Optim. 17(4), 1943-1971(2021)
[37] Bartz, S., Campoy, R., Phan, H.M.:An adaptive alternating direction method of multipliers. J. Optim. Theory Appl. 195, 1019-1055(2022)
[38] Dao, M.N., Phan, H.M.:Adaptive Douglas-Rachford splitting algorithm for the sum of two operators. SIAM J. Optim. 29(4), 2697-2724(2019)
[39] Bartz, S., Dao, M.N., Phan, H.M.:Conical averagedness and convergence analysis of fixed point algorithms. J. Glob. Optim. 82(2), 351-373(2022)
[40] Li, G.Y., Pong, T.K.:Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4), 2434-2460(2015)
[41] Liu, P.J., Jian, J.B., He, B., Jiang, X.Z.:Convergence of Bregman Peaceman-Rachford splittingmethod for nonconvex nonseparable optimization. J. Oper. Res. Soc. China 11(4), 707-733(2022)
[42] Wang, F.H., Cao, W.F., Xu, Z.B.:Convergence of multi-block Bregman ADMM for nonconvex composite problems. Sci. China Inf. Sci. 61(12), 122101(2018)
[43] Wang, F.H., Xu, Z.B., Xu, H.K.:Convergence of Bregman Alternating Direction Method with Multipliers for Nonconvex Composite Problems. arXiv:1410.8625(2014)
[44] Liu, P.J., Jian, J.B., Ma, G.D.:A Bregman-style partially symmetric alternating direction method of multipliers for nonconvex multi-block optimization. Acta Math. Appl. Sin. Eng. Ser. 39(2), 354-380(2023)
[45] Xu, J.W., Chao, M.T.:An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization. J. Appl. Math. Comput. 68, 1-27(2022)
[46] Jian, J.B., Ma, G.D., Liu, P.J., Xu, J.W.:Convergence analysis of an improved Bregman-type Peaceman-Rachford splitting algorithm for nonconvex nonseparable linearly constrained optimization problems. J. Comput. Appl. Math. 426, 115086(2023)
[47] Bot, R.I., Nguyen, D.K.:The proximal alternating direction method of multipliers in the nonconvex setting:convergence analysis and rates. Math. Oper. Res. 45(2), 682-712(2020)
[48] Wu, Z.M., Li, M., Wang, D.Z.W., Han, D.R.:A symmetric alternating direction method of multipliers for separable nonconvex minimization problems. Asia Pac. J. Oper. Res. 34(6), 1750030(2017)
[49] Themelis, A., Patrinos, P.:Douglas-Rachford splitting and ADMM for nonconvex optimization:Tight convergence results. SIAM J. Optim. 30(1), 149-181(2020)
[50] Goncalves, M.L.N., Melo, J.G., Monteiro, R.D.C.:Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems. Pac. J. Optim. 15(3), 379-398(2019)
[51] Yashtini, M.:Multi-block nonconvex nonsmooth proximal ADMM:Convergence and rates under Kurdyka-Łojasiewicz property. J. Optim. Theory Appl. 190, 966-998(2021)
[52] Liu, P.J., Shao, H., Wang, Y., Wu, X.Y.:Local linear convergrnce rate analysis of a symmetric ADMM with relaxation-step for nonconvex optimization. J. Sys. Sci. Math. Sci. 43(1), 78-93(2023)(in Chinese)
[53] Bai, J.C., Guo, K., Liang, J.L., Jing, Y., So, H.C.:Accelerated symmetric ADMM and its applications in large-scale signal processing. J. Comput. Math.(2023). https://doi.org/10.4208/jcm.2305-m2021-0107
[54] Barzilai, J., Borwein, J.M.:Two point step size gradient method. IMA J. Numer. Anal. 8, 141-148(1988)
[55] Rockafellar, R., Wets, R.:Variational Analysis. Springer-Verlag, Berlin Heidelberg (1998)
[56] Nesterov, Y.:Introduction Lectures on Convex Optimization:A Basic Course. Springer Science&Business Media, Berlin (2013)
[57] Attouch, H., Bolte, J., Redont, P., Soubeyran, A.:Proximal alternating minimization and projection methods for nonconvex problems:An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35, 438-457(2010)
[58] 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)
[59] Bolte, J., Sabach, S., Teboulle, M.:Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program. 146(1-2), 459-494(2014)