Convergence of Bregman Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization

doi:10.1007/s40305-022-00411-x

Abstract

Abstract: This work is about a splitting method for solving a nonconvex nonseparable optimization problem with linear constraints, where the objective function consists of two separable functions and a coupled term. First, based on the ideas from Bregman distance and Peaceman-Rachford splitting method, the Bregman Peaceman-Rachford splitting method with different relaxation factors for the multiplier is proposed. Second, the global and strong convergence of the proposed algorithm are proved under general conditions including the region of the two relaxation factors as well as the crucial Kurdyka-Łojasiewicz property. Third, when the associated Kurdyka-Łojasiewicz property function has a special structure, the sublinear and linear convergence rates of the proposed algorithm are guaranteed. Furthermore, some preliminary numerical results are shown to indicate the effectiveness of the proposed algorithm.

Key words: Nonconvex nonseparable optimization, Peaceman-Rachford splitting method, Bregman distance, Kurdyka-?ojasiewicz inequality, Convergence rate

CLC Number:

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.

TrendMD

References

[1] Shen, Y., Wen, Z., Zhang, Y.: Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw. 29(2), 239-263 (2014)
[2] Xu, Y.: Alternating proximal gradient method for sparse nonnegative Tucker decomposition. Math. Program. Comput. 7(1), 39-70 (2015)
[3] 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. Ind. Inform. 16(3), 1858-1872 (2020)
[4] Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421-439 (1956)
[5] Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964-979 (1979)
[6] Peaceman, D.W., Rachford, H.H., Jr.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Indust. Appl. Math. 3, 28-41 (1955)
[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., Marrocco, A.: Sur l’approximation, par elements finis d’ordre un, et la resolution, par penalisation-dualit’e, d’une classe de problems de Dirichlet non lineares. Ann. Math. Stat. 9, 41-76 (1975)
[9] Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168-1200 (2005)
[10] Corman, E., Yuan, X.: A generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4), 1614-1638 (2014)
[11] Gabay, D.: Chapter IX applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299-331 (1983)
[12] He, B., Liu, H., Wang, Z., Yuan, X.: A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J. Optim. 24(3), 1011-1040 (2014)
[13] He, B., Ma, F., Yuan, X.: Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imaging Sci. 9, 1467-1501 (2016)
[14] Wu, Z., Li, M.: An LQP-based symmetric alternating direction method of multipliers with larger step sizes. J. Oper. Res. Soc. China 7, 365-383 (2019)
[15] Sun, M., Wang, Y., Liu, J.: Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA. Calcolo 54(1), 77-94 (2017)
[16] Deng, Z., Liu, S.: Generalized Peaceman-Rachford splitting method with substitution for convex programming. Optim. Lett. 14, 1781-1802 (2020)
[17] Deng, Z., Liu, S.: Inertial proximal strictly contractive Peaceman-Rachford splitting method with an indefinite term for convex optimization. J. Comput. Appl. Math. 374, 112772 (2020)
[18] Li, X., Yuan, X.: A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging. SIAM J. Imaging Sci. 8(2), 1332-1365 (2015)
[19] Dou, M.Y., Li, H.Y., Liu, X.W.: An inertial proximal Peaceman-Rachford splitting method (in Chinese). Sci. Sin. Math. 47(2), 333-348 (2017)
[20] Lu, S., Hong, M., Wang, Z.: A nonconvex splitting method for symmetric nonnegative matrix factorization: convergence analysis and optimality. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing 2572-2576 (2017)
[21] Olshausen, B.A., Field, D.J.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381(6583), 607-609 (1996)
[22] Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24(3), 035020 (2008)
[23] Li, G., Pong, T.K.: Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159(1-2), 371-401 (2016)
[24] Chao, M.T., Han, D.R., Cai, X.J.: Convergence of the Peaceman-Rachford splitting method for a class of nonconvex programs. Numer. Math. Theory Methods Appl. 14(2), 438-460 (2021)
[25] Wu, Z., Li, M., Wang, D., Han, D.: A symmetric alternating direction method of multipliers for separable nonconvex minimization problems. Asia Pac. J. Oper. Res. 34(06), 1750030 (2017)
[26] Bai, J., Liang, J., Guo, K., Jing, Y.: Accelerated symmetric ADMM and its applications in signal processing (2019). arXiv:1906.12015
[27] Hong, M., Luo, Z., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26, 337-364 (2016)
[28] Gao, X., Xu, Y., Zhang, S.: Randomized primal-dual proximal block coordinate updates. J. Oper. Res. Soc. China 7, 205-250 (2019)
[29] Hong, M., Chang, T., Wang, X., Razaviyayn, M., Ma, S., Luo, Z.: A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. Math. Oper. Res. 45(3), 797-1192 (2020)
[30] Chao, M.T., Cheng, C.Z., Liang, D.Y.: A proximal block minimization method of multipliers with a substitution procedure. Optim. Methods Soft. 30(4), 825-842 (2015)
[31] Gao, X., Zhang, S.: First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5, 131-159 (2017)
[32] Cui, Y., Li, X., Sun, D., Toh, K.: On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169, 1013-1041 (2016)
[33] Chen, C., Li, M., Liu, X., Ye, Y.: Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights. Math. Program. 173, 37-77 (2019)
[34] Liu, F., Xu, L., Sun, Y., Han, D.: A proximal alternating direction method for multi-block coupled convex optimization. J. Ind. Manag. Optim. 15, 723-737 (2018)
[35] Guo, K., Han, D., Wu, T.: Convergence analysis for optimization problems with nonseparable nonconvex objective and linear constraints. Pac. J. Optim. 14, 489-506 (2018)
[36] Guo, K., Wang, X.: Convergence of generalized alternating direction method of multipliers for nonseparable nonconvex objective with linear constraints. J. Math. Res. Appl. 38, 523-540 (2018)
[37] Chao, M., Deng, Z., Jian, J.: Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure. Complexity 2020, 1-14 (2020)
[38] Jiang, B., Lin, T., Ma, S., Zhang, S.: Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis. Comput. Optim. Appl. 72, 115-157 (2019)
[39] Liu, Q., Shen, X., Gu, Y.: Linearized ADMM for nonconvex nonsmooth optimization with convergence analysis. IEEE Access 7, 76131-76144 (2019)
[40] Wang, H., Banerjee, A.: Bregman alternating direction method of multipliers. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), 2816-2824 (2014)
[41] Li, G., Pong, T.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25, 2434-2460 (2015)
[42] Wang, F., Xu, Z., Xu, H.: Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems (2014). arXiv:1410.8625
[43] Wang, F., Cao, W., Xu, Z.: Convergence of multi-block Bregman ADMM for nonconvex composite problems. Sci. China Inform. Sci. 61, 122101 (2018)
[44] Xu, J., Chao, M.: An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization. J. Appl. Math. Comput. (2021). https://doi.org/10.1007/s12190-021-01590-1
[45] Rockafellar, R., Wets, R.: Variational Analysis. Springer Science & Business Media, Berlin (2009)
[46] 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)
[47] Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program. 146, 459-494 (2014)
[48] Nesterov, Y.: Introduction Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, Berlin (2013)
[49] Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 200-217 (1967)
[50] Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116, 5-16 (2009)
[51] Zeng, L., Xie, J.: Group variable selection via SCAD l₂. Statistics 48, 49-66 (2014)
[52] Wu, Z., Li, M.: General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems. Comput. Optim. Appl. 73, 129-158 (2019)
[53] Fan, J.: Comments on ‘Wavelets in statistics: A review’ by A. Antoniadis. J. Ital. Stat. Soc. 6, 131-138 (1997)