具有线性化技术的三块非凸不可分优化问题Bregman ADMM收敛性分析

Abstract

Abstract:

Alternating direction multiplier method is an effective method to solve two separable convex optimization problems, but the convergence of alternating direction multiplier method may not be guaranteed for three nonseparable nonconvex optimization problems. This paper mainly studies the convergence analysis of the linearized generalized Bregman alternating direction multiplier method (L-G-BADMM) for solving the nonconvex minimization problem whose objective function is three indivisible blocks. Under appropriate assumptions, we solve the subproblem of the algorithm and construct a benefit function satisfying Kurdyka-Lojasiewicz property. The convergence of the algorithm can be obtained through theoretical proof.

Key words: Bregman divergence, ADMM, Kurdyka-Lojasiewicz property, Linearization

CLC Number:

O221.2

Liu Fuqin, Peng Jianwen, Luo Honglin. Convergence Analysis of Bregman ADMM for Three-Block Nonconvex Indivisible Optimization Problems with Linearization Technique[J].Acta mathematica scientia,Series A, 2023, 43(1): 291-304.

Trendmd

References 27

[1]	Banerjee A, Merugu S, Dhillon I, Ghosh J. Clustering with bregman divergences. Journal of Machine Learning Research, 2005, 6: 1705-1749
[2]	Bolte J, Daniilidis A, Ley O, et al. Characterizations of Lojasiewicz inequalities and applications: subgradient flows, talweg, convexity. Transactions of the American Mathematical Society, 2010, 362(6): 3319-3363 doi: 10.1090/S0002-9947-09-05048-X
[3]	Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations Trends in Machine Learning, 2010, 3(1): 1-122 doi: 10.1561/2200000016
[4]	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 Computational Mathematics and Mathematical Physics, 1967, 7(3): 200-217
[5]	Chao M T, Cheng C Z, Zhang H B. A linearized alternating direction method of multipliers with substitution procedure. Asia-Pacific Journal of Operational Research, 2015, 32(3): 1550011 doi: 10.1142/S0217595915500116
[6]	Chao M T, Deng Z, Jian J B. Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure. Complexity, 2020, 2020: Art ID 6237942
[7]	Chao M T, Zhang Y, Jian J B. An inertial proximal alternating direction method of multipliers for nonconvex optimization. International Journal of Computer Mathematics, 2021, 98(6): 1199-1217 doi: 10.1080/00207160.2020.1812585
[8]	Chen C H, He B S, Ye Y Y, et al. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Mathematical Programming, 2016, 155: 57-79 doi: 10.1007/s10107-014-0826-5
[9]	Deng W, Yin W T. On the global and linear convergence of the generalized alternating direction method of multipliers. Journal of Scientific Computing, 2016, 66(3): 889-916 doi: 10.1007/s10915-015-0048-x
[10]	Feng J K, Zhang H B, Cheng C Z, et al. Convergence analysis of L-ADMM for multi-block linear-constrained separable convex minimization problem. Journal of the Operations Research Society of China, 2015, 3(4): 563-579 doi: 10.1007/s40305-015-0084-0
[11]	Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications, 1976, 2(1): 17-40 doi: 10.1016/0898-1221(76)90003-1
[12]	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. Journal of E-quine Veterinary Science, 1975, 2(2): 41-76
[13]	Guo K, Han D R, Wang D Z W, et al. Convergence of ADMM for multi-block nonconvex separable optimization models. Frontiers of Mathematics in China, 2017, 12(5): 1139-1162 doi: 10.1007/s11464-017-0631-6
[14]	Guo K, Hand D R, Wu T T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. International Journal of Computer Mathematics, 2017, 94(8): 1653-1669 doi: 10.1080/00207160.2016.1227432
[15]	Guo K, Wang X. Convergence of generalized alternating direction method of multipliers for nonseparable nonconvex objective with linear constraints. Journal of Mathematical Research with Applications, 2018, 38(5): 523-540
[16]	Hong M Y, Lou Z Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 2016, 26(1): 337-364 doi: 10.1137/140990309
[17]	Li M, Sun D F, Toh K C. A convergent 3-blocksemi-proximal ADMM for convex minimization problems with one strongly convex block. Asia-Pacific Journal of Operational Research, 2015, 32(4): 1550024 doi: 10.1142/S0217595915500244
[18]	Rockafellar R T, Wets R J B. Variational Analysis. Berlin: Springer Science and Business Media, 2009
[19]	Wang F H, Cao W F, Xu Z B. Convergence of multi-block Bregman ADMM for nonconvex composite problems. Science China Information Sciences, 2018, 61(12): 1-12
[20]	Wang F H, Xu Z B, Xu H K. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. arXiv: 1410.8625
[21]	Wang H H, Banerjee A. Bregman alternating direction method of multipliers//Ghahramani Z, Welling M, Cortes C, et al. Advances in Neural Information Processing Systems, 2014: 2816-2824
[22]	Xu Z B, Chang X Y, Xu F M, Zhang H. $L_\frac{1}{2}$ regularization: a thresholding representation theory and a fast solver. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23: 1013-1027 doi: 10.1109/TNNLS.2012.2197412
[23]	Yang W H, Han D. Linear Convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM Journal on Numerical Analysis, 2016, 54(2): 625-640 doi: 10.1137/140974237
[24]	Yashtini M. Multi-block nonconvex nonsmooth proximal ADMM: Convergence and rates Under Kurdyka-ojasiewicz property. Journal of Optimization Theory and Applications, 2021, 190(3): 966-998 doi: 10.1007/s10957-021-01919-7
[25]	Zeng J S, Fang J, Xu Z B. Sparse SAR imaging based on $L_\frac{1}{2}$ regularization. Sci China Infor Sci, 2012, 55: 1755-1775
[26]	Zeng J S, Lin S B, Wang Y, et al. $L_\frac{1}{2}$ Regularization: Convergence of iterative half thresholding algorithm. IEEE Transactions on Signal Processing, 2014, 62(9): 2317-2329 doi: 10.1109/TSP.2014.2309076
[27]	Zeng J S, Xu Z B, Zhang B, et al. Accelerated $L_\frac{1}{2}$ regularization based SAR imaging via BCR and reduced Newton skills. Signal Processing, 2013, 93: 1831-184 doi: 10.1016/j.sigpro.2012.12.017

Convergence Analysis of Bregman ADMM for Three-Block Nonconvex Indivisible Optimization Problems with Linearization Technique

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

References 27

Related Articles 6

Metrics

Comments

Recommended 10

[1]	Wei Hanyu, Xia Tiecheng. Quasi-Periodic Solution of the Generalized Broer-Kaup-Kupershmidt Soliton Equation [J]. Acta mathematica scientia,Series A, 2016, 36(2): 317-327.
[2]	ZHANG Ling, ZHU Hong-Ling. The Bargmann Symmetry Constraint and Binary Nonlinearization of the Super Li System [J]. Acta mathematica scientia,Series A, 2014, 34(5): 1287-1295.
[3]	Wang Qinlong; Liu Yirong. Isochronous Center for a Class of Quintic System [J]. Acta mathematica scientia,Series A, 2007, 27(6): 1044-1053.
[4]	Shen Peiping;Yang Changsen. Algorithm of Global Optimization for Generalized Geometric Programming [J]. Acta mathematica scientia,Series A, 2006, 26(3): 382-386.
[5]	XU Xi-Xiang, WANG Shi-Fan. A Hierarchy of Discrete Generalized Hamiltonian Systems and a New Integrable Symplectic Map [J]. Acta mathematica scientia,Series A, 2003, 23(3): 298-305.
[6]	Zhou Ruguang. A Method to Seek the Finite-Band Solution of Soliton Equation [J]. Acta mathematica scientia,Series A, 1998, 18(2): 228-234.