A Linear Approximate Bregman-type Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization

Peng Jie LIU, Jin Bao JIAN, Guo Dong MA, Jia Wei XU

Acta Mathematica Sinica, Chinese Series ›› 2023, Vol. 66 ›› Issue (1) : 75-94.

PDF(643 KB)
中国科学院数学与系统科学研究院期刊网
PDF(643 KB)
Acta Mathematica Sinica, Chinese Series ›› 2023, Vol. 66 ›› Issue (1) : 75-94. DOI: 10.12386/A20210081

A Linear Approximate Bregman-type Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization

  • Peng Jie LIU1, Jin Bao JIAN2, Guo Dong MA4, Jia Wei XU3
Author information +
History +

Abstract

Based on the Peaceman-Rachford splitting method, combined with the linear approximate technique and Bregman distance, in this paper, we present a linear approximation Bregman-type Peaceman-Rachford splitting method for solving the nonconvex nonseparable optimization problem with linear constraints. Under the conventional assumptions, we get the global convergence of the proposed algorithm. On the premise that the merit function satisfies the Kurdyka-Ƚojasiewicz property, the strong convergence of the proposed algorithm is proved. When the associated Kurdyka-Ƚojasiewicz property function has a special structure, the convergence rate results of the proposed algorithm are analyzed and obtained. Finally, some preliminary numerical results show that the proposed algorithm has numerical validity.

Key words

nonconvex nonseparable optimization / linear approximate technique / Peaceman-Rachford splitting method / Kurdyka-Ƚojasiewicz property / convergence rate

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
Peng Jie LIU, Jin Bao JIAN, Guo Dong MA, Jia Wei XU. A Linear Approximate Bregman-type Peaceman-Rachford Splitting Method for Nonconvex Nonseparable Optimization. Acta Mathematica Sinica, Chinese Series, 2023, 66(1): 75-94 https://doi.org/10.12386/A20210081

References

[1] Attouch H., Bolte J., Redont P., et al., Proximal alternating minimization and projection methods for nonconvex problems:an approach based on the Kurdyka-Ƚojasiewicz inequality, Math. Oper. Res., 2010, 35:438-457.
[2] Attouch H., Bolte J., Svaiter B., Convergence of descent methods for semi-algebraic and tame problems:proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 2013, 137:91-129.
[3] Bolte J., Sabach S., Teboulle M., Proximal alternating linearized minimization or nonconvex and nonsmooth problems, Math. Program, 2014, 146:459-494.
[4] Chao M. T., Cheng C. Z., Liang D. Y., A proximal block minimization method of multipliers with a substitution procedure, Optim. Methods Soft., 2015, 30(4):825-842.
[5] Chao M. T., Deng Z., Jian J. B., Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, Complexity, 2020, 2020:Article ID 6237942, 14 pp.
[6] Chao M. T., Zhang Y., Jian J. B., An inertial proximal alternating direction method of multipliers for nonconvex optimization, Int. J. Comput. Math., 2021, 98(6):1199-1217.
[7] 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., 2021, 14(2):438-460.
[8] Chen C. H., Li M., Liu X., et al., Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms:convergence analysis and insights, Math. Program., 2019, 173:37-77.
[9] Chen M. X., Inertial Splitting Methods for Nonconvex and Nonsmooth Problems (in Chinese), Guangxi University, Nanning, 2020.
[10] Cui Y., Li X. D., Sun D. F., et al., 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., 2016, 169:1013-1041.
[11] Gabay D., Chapter IX applications of the method of multipliers to variational inequalities, Stud. Math. Appl., 1983, 15:299-331.
[12] Gabay D., Mercier B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 1976, 2(1):17-40.
[13] Gao X., Cai X. J., Han D. R., A Gauss-Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems, J. Global Optim., 2020, 76:863-887.
[14] Gao X., Zhang S. Z., First-order algorithms for convex optimization with nonseparable objective and coupled constraints, J. Oper. Res. Soc. China, 2017, 5:131-159.
[15] 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., 1975, 9:41- 76.
[16] 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., 2017, 94:1653-1669.
[17] Guo K., Han D. R., Wu T. T., Convergence analysis for optimization problems with nonseparable nonconvex objective and linear constraints, Pac. J. Optim., 2018, 14:489-506.
[18] Guo K., Wang X., Convergence of generalized alternating direction method of multipliers for nonseparable nonconvex objective with linear constraints, J. Math. Res. Appl., 2018, 38(5):523-540.
[19] Fan J. Q., Comments on 'Wavelets in statistics:a review' by A. Antoniadis, J. Italian Statis. Soc., 1997, 6:131-138.
[20] Hien L., Phan D., Gillis N., A framework of inertial alternating direction method of multipliers for non-convex non-smooth optimization, arXiv:2102.05433, 2021.
[21] Hong M. Y., Luo Z. Q., Razaviyayn M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 2016, 26:337-364.
[22] Jia Z. H., Gao X., Cai X. J., et al., The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems, J. Ind. Manag. Optim., 2021, 17(4):1943-1971.
[23] Jia Z. H., Gao X., Cai X. J., et al., Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, J. Optim. Theory Appl., 2021, 188:1-25.
[24] Jian J. B., Liu P. J., Jiang X. Z., A partially symmetric regularized alternating direction method of multipliers for nonconvex multi-block optimization (in Chinese), Acta Math. Sin. Chin. Ser., 2021, 64(6):1005-1026.
[25] Jiang B., Lin T. Y., Ma S. Q., et al., Structured nonconvex and nonsmooth optimization:algorithms and iteration complexity analysis, Comput. Optim. Appl., 2019, 72:115-157.
[26] Li G. Y., Pong T. K., Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 2015, 25:2434-2460.
[27] Li P. X., Shen Y., Jiang S. H., et al., Convergence study on strictly contractive Peaceman-Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms, Comput. Optim. Appl., 2021, 78:87-124.
[28] Liu M. X., Jian J. B., An ADMM-based SQP method for separably smooth nonconvex optimization, J. Inequal. Appl., 2020, No.81, 17 pp.
[29] Liu F. X., Xu L. L., Sun Y. H., et al., A proximal alternating direction method for multi-block coupled convex optimization, J. Ind. Manage. Optim., 2019, 15:723-737.
[30] Liu Q. H., Shen X. Y., Gu Y. T., Linearized ADMM for nonconvex nonsmooth optimization with convergence analysis, IEEE Access, 2019, 7:76131-76144.
[31] Nesterov Y., Introductory Lectures on Convex Optimization:A Basic Course, Springer Science & Business Media, Boston, 2013.
[32] Peaceman D., Rachford H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 1955, 3(1):28-41.
[33] Pock T., Sabach S., Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems, SIAM J. Imag. Sci., 2017, 9:1756-1787.
[34] Rockafellar R., Wets R., Variational Analysis, Springer Science & Business Media, Berlin, 2009.
[35] Wang H. H., Banerjee A., Bregman alternating direction method of multipliers, Proceedings of Advances in Neural Information Processing Systems (NIPS), 2014:2816-2824.
[36] Wang F. H., Cao W. F., Xu Z. B., Convergence of multi-block Bregman ADMM for nonconvex composite problems, Sci. China Inform. Sci., 2018, 61(12):122101, 12 pp.
[37] 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.
[38] Xu J. W., Chao M. T., An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization, J. Appl. Math. Comput., https://doi.org/10.1007/s12190-021-01590-1,2021.
[39] Wu Z. M., Li M., General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Comput. Optim. Appl., 2019, 73:129-158.
[40] Wu Z., Li M., Wang D., et al., A symmetric alternating direction method of multipliers for separable nonconvex minimization problems, Asia Pac. J. Oper. Res., 2017, 34(06):1750030, 27 pp.
[41] Xu Y. Y., Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming, SIAM J. Optim., 2018, 28:646-670.
[42] Zeng L. M., Xie J., Group variable selection via SCAD-l2, Statistics, 2014, 48:49-66.
[43] Zhang Y. X., He S. N., Inertial proximal alternating minimization for nonconvex and nonsmooth problems, J. Inequal. Appl., 2017, No. 232:13 pp.
PDF(643 KB)

460

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉