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

数学物理学报 ›› 2023, Vol. 43 ›› Issue (1): 291-304.

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

刘富勤,彭建文^*(),罗洪林

重庆师范大学数学科学学院重庆401331

收稿日期:2022-03-31 修回日期:2022-08-05 出版日期:2023-02-26 发布日期:2023-03-07
通讯作者: ^*彭建文, E-mail: jwpeng168@hotmail.com
基金资助:
国家自然科学基金重大项目(11991024);国家自然科学基金面上项目(12271071);重庆英才$\cdot$ 创新创业领军人才$\cdot$ 创新创业示范团队项目(CQYC20210309536);重庆英才计划包干制项目(cstc2022ycjh-bgzxm0147);重庆市高校创新研究群体项目(CXQT20014);重庆市自然科学基金项目(cstc2021jcyj-msxmX0300)

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

Liu Fuqin,Peng Jianwen^*(),Luo Honglin

School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331

Received:2022-03-31 Revised:2022-08-05 Online:2023-02-26 Published:2023-03-07
Supported by:
The NSFC(11991024);The NSFC(12271071);Team Project of Innovation Leading Talent in Chongqing(CQYC20210309536);Contract System Project of Chongqing Talent Plan(cstc2022ycjh-bgzxm0147);Chongqing University Innovation Research Group Project(CXQT20014);Chongqing Natural Science Foundation Project(cstc2021jcyj-msxmX0300)

摘要/Abstract

摘要：

交替方向乘子法是求解两块可分离凸优化问题的有效方法, 但是对于三块不可分的非凸优化问题的交替方向乘子法的收敛性可能无法保证. 该文主要研究的是用线性化广义Bregman交替方向乘子法(L-G-BADMM)求解目标函数是三块不可分的非凸极小化问题的收敛性分析. 在适当假设条件下, 对算法中子问题进行求解并构建满足Kurdyka-Lojasiewicz性质的效益函数, 经过理论证明可以得到该算法的收敛性.

关键词: Bregman散度, 交替方向乘子法, Kurdyka-?ojasiewicz性质, 线性化

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

中图分类号:

O221.2

刘富勤, 彭建文, 罗洪林. 具有线性化技术的三块非凸不可分优化问题Bregman ADMM收敛性分析[J]. 数学物理学报, 2023, 43(1): 291-304.

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.

参考文献 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