非凸多分块优化的 Bregman ADMM 的收敛率研究

数学物理学报 ›› 2024, Vol. 44 ›› Issue (1): 195-208.

非凸多分块优化的 Bregman ADMM 的收敛率研究

陈建华(),彭建文^*()

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

收稿日期:2022-06-09 修回日期:2023-08-16 出版日期:2024-02-26 发布日期:2024-01-10
通讯作者: 彭建文, E-mail:jwpeng168@hotmail.com
作者简介:陈建华, E-mail:1224888402@qq.com
基金资助:
国家自然科学基金(12271071);国家自然科学基金(11991024);重庆英才·创新创业领军人才·创新创业示范团队项目(CQYC20210309536);重庆英才计划"包干制"项目(cstc2022ycjh-bgzxm0147);重庆市高校创新研究群体项目(CXQT20-014);重庆市自然科学基金项目(cstc2021jcyj-msxmX0300)

Research on the Convergence Rate of Bregman ADMM for Nonconvex Multiblock Optimization

Chen Jianhua(),Peng Jianwen()

College of Mathematical Sciences; Chongqing Normal University, Chongqing 401331

Received:2022-06-09 Revised:2023-08-16 Online:2024-02-26 Published:2024-01-10
Supported by:
National Natural Science Foundation of China(12271071);National Natural Science Foundation of China(11991024);Team Project of Innovation Leading Talent in Chongqing(CQYC20210309536);Chongqing Talent Plan contract system project(cstc2022ycjh-bgzxm0147);Chongqing University Innovation Research Group Project(CXQT20-014);Basic and Advanced Research Project of Chongqing(cstc2021jcyj-msxmX0300)

摘要/Abstract

摘要：

Wang 等提出了求解带线性约束的多块可分非凸优化问题的带 Bregman 距离的交替方向乘子法 (Bregman ADMM), 并证明了其收敛性. 该文将进一步研究求解带线性约束的多块可分非凸优化问题的 Bregman ADMM 的收敛率, 以及算法产生的迭代点列有界的充分条件. 在效益函数的 Kurdyka-Łojasiewicz (KŁ) 性质下, 该文建立了值和迭代的收敛速率, 证明了与目标函数相关的各种 KŁ 指数值可获得 Bregman ADMM 的三种不同收敛速度. 更确切地说, 该文证明了如下结果:如果效益函数的 KŁ 指数$\theta=0$, 那么由 Bregman ADMM 生成的序列经过有限次迭代后收敛; 如果$\theta \in \left (0, \frac{1}{2}\right ]$, 那么Bregman ADMM是线性收敛的;如果$\theta \in \left ( \frac{1}{2}, 1\right )$, 那么 Bregman ADMM 是次线性收敛的.

关键词: 非凸优化问题, 交替方向乘子法, Kurdyka-Łojasiewicz 性质, Bregman 距离, 收敛率, 有界性

Abstract:

Wang et al proposed the alternating direction method of multipliers with Bregman distance (Bregman ADMM) for solving multi-block separable nonconvex optimization problems with linear constraints, and proved its convergence.In this paper, we will further study the convergence rate of Bregman ADMM for solving multi-block separable nonconvex optimization problems with linear constraints, and the sufficient conditions for the boundedness of the iterative point sequence generated by the algorithm.Under the Kurdyka-Łojasiewicz property of benefit function, this paper establish the convergence rates for the values and iterates, and we show that various values of KŁ-exponent associated with the objective function can obtain Bregman ADMM with three different convergence rates. More precisely, this paper proves the following results:if the(KŁ) exponent of the benefit function$\theta=0$, then the sequence generated by Bregman ADMM converges in a finite numbers of iterations; if$\theta \in \left (0, \frac{1}{2}\right ]$, then Bregman ADMM is linearly convergent; if$\theta \in \left ( \frac{1}{2}, 1\right )$, then Bregman ADMM is sublinear convergent.

Key words: Nonconvex optimization problem, The alternating direction method of multipliers, Kurdyka-Łojasiewicz property, Bregman distance, Convergence rates, Boundedness

中图分类号:

O221

陈建华, 彭建文. 非凸多分块优化的 Bregman ADMM 的收敛率研究[J]. 数学物理学报, 2024, 44(1): 195-208.

Chen Jianhua, Peng Jianwen. Research on the Convergence Rate of Bregman ADMM for Nonconvex Multiblock Optimization[J]. Acta mathematica scientia,Series A, 2024, 44(1): 195-208.

参考文献 35

[1]	Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3: 1-122 doi: 10.1561/2200000016
[2]	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 Equine Veterinary Science, 1975, 2: 41-76
[3]	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: 17-40 doi: 10.1016/0898-1221(76)90003-1
[4]	Bertsekas D, Tsitsiklis J. Numerical Methods for Nonlinear Variational Problems. Berlin: Springer Series in Computational Physics, Springer, 1984
[5]	何炳生. 乘子交替方向法的一些收敛性质. 高等学校计算数学学报, 2017, 39: 81-96
	He B S. Some convergence properties of the alternating direction method of multipliers. Numerical Mathematics A Journal of Chinese Universities, 2017, 39: 81-96
[6]	Yang W H, Han D R. Linear Convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM Journal on Numerical Analysis, 2016, 54: 625-640 doi: 10.1137/140974237
[7]	He B S, Ma F, Yuan X M. Convergence study on the symmetric version of ADMM with larger step sizes. SIAM Journal on Imaging Sciences, 2016, 9: 1467-1501 doi: 10.1137/15M1044448
[8]	Fazel M, Pong T K, Sun D F, et al. Hankel matrix rank minimization with applications to system identification and realization. SIAM Journal on Matrix Analysis and Applications, 2013, 34: 946-977 doi: 10.1137/110853996
[9]	Li M, Sun D F, Toh K C. A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM Journal on Optimization, 2016, 26: 922-950 doi: 10.1137/140999025
[10]	Zhang L, Wu J, Zhang L W. A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications. Mathematics of Computation, 2020, 89(324): 1867-1894 doi: 10.1090/mcom/2020-89-324
[11]	Wang H H, Banerjee A. Bregman alternating direction method of multipliers. Arxiv: 1306.3203v3, 2014
[12]	Wang F, Xu Z B, Xu H K. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. https://arXiv preprint arXiv: 1410.8625, 2014
[13]	Guo K, Han 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: 1653-1669 doi: 10.1080/00207160.2016.1227432
[14]	Wu Z M, Li M, Wang D, et al. A symmetric alternating direction method of multipliers for separable nonconvex minimization problems. Asia Pacific Journal of Operation Research, 2017, 34(06): 1750030 doi: 10.1142/S0217595917500300
[15]	Jian J B, Zhang Y, Chao M T. A regularized alternating direction method of multiplier for a class of nonconvex problems. Journal of Inequalities and Applications, 2019, 2019: 1-16 doi: 10.1186/s13660-019-1955-4
[16]	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. Journal of Optimization Theory and Applications, 2021, 188: 1-25 doi: 10.1007/s10957-020-01782-y
[17]	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
[18]	Han D R, Yuan X M. A note on the alternating direction method of multipliers. Journal of Optimization Theory and Applications, 2012, 155: 227-238 doi: 10.1007/s10957-012-0003-z
[19]	Lin T Y, Ma S Q, Zhang S Z. Global convergence of unmodified 3-block ADMM for a class of convex minimization problems. Journal of Scientific Computing, 2018, 76: 69-88 doi: 10.1007/s10915-017-0612-7
[20]	He B S. Parallel splitting augmented lagrangian methods for monotone structured variational inequalities. Computational Optimization and Applications, 2009, 42: 195-212 doi: 10.1007/s10589-007-9109-x
[21]	He B S, Tao M, Yuan X M. Alternating direction method with Gaussian back substitution for separable convex programming. SIAM Journal on Optimization, 2012, 22: 313-340 doi: 10.1137/110822347
[22]	Chen L, Li X D, Sun D F, et al. On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. Mathematical Programming, 2021, 185: 111-161 doi: 10.1007/s10107-019-01423-x
[23]	Deng W, Lai M J, Peng Z M, et al. Parallel multi-block ADMM with$o(1/k)$convergence. Journal of Scientific Computing, 2017, 71 : 712-736 doi: 10.1007/s10915-016-0318-2
[24]	Hong M Y, Luo Z Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization, 2016, 26: 337-364 doi: 10.1137/140990309
[25]	Guo K, Han D R, David W W, et al. Convergence of ADMM for multi-block nonconvex separable optimization mobels. Front. Math. China, 2017, 12: 1139-1162 doi: 10.1007/s11464-017-0631-6
[26]	Jiang B, Lin T Y, Ma S Q, et al. Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis. Computational Optimization and Applications, 2019, 72: 115-157 doi: 10.1007/s10589-018-0034-y
[27]	Yashtinin M. Multi-block nonconvex nonsmooth proximal ADMM: Convergence and rates under Kurdyka-Łojasiewicz property. Journal of Optimization Theory and Applications, 2021, 190: 966-998 doi: 10.1007/s10957-021-01919-7
[28]	简金宝, 刘鹏杰, 江羡珍. 非凸多分块优化部分对称正则化交替方向乘子法. 数学学报, 2021, 64A(6): 1005-1026
	Jian J B, Liu P J, Jiang X Z. A partially symmetric regularized alternating direction method of multipliers for nonconvex Multi-block optimization. Acta Mathematica Sinica (Chinese Series), 2021, 64A(6): 1005-1026
[29]	Wang F H, Cao W F, Xu Z B. Convergence of multi-block Bregman ADMM for nonconvex problems. Science China Information Sciences, 2018, 61: 1-12
[30]	Frankel P, Garrigos G, Peypouquet J. Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. Journal of Optimization Theory and Applications, 2015, 165: 874-900 doi: 10.1007/s10957-014-0642-3
[31]	Rockafellar R T, Wets R J B. Variational Analysis. Berlin: Springer Science and Business Media, 2009
[32]	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. Mathematical Programming, 2013, 137: 91-129 doi: 10.1007/s10107-011-0484-9
[33]	Si S, Tao D C, Geng B. Bregman divergence-based regularization for transfer subspace learning. IEEE Transactions on Knowledge and Data Engineering, 2010, 22: 929-942 doi: 10.1109/TKDE.2009.126
[34]	Xu Z B, Chang X Y, Xu F M, et al. $L_{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
[35]	Bolte J, Daniilidis A, Lewis A. $L_{1/2}$The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 2007, 17: 1205-1223 doi: 10.1137/050644641