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

Abstract

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

CLC Number:

O221

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.

Trendmd

References 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

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

References 35

Related Articles 15

Metrics

Comments

Recommended 10

[1]	Chen Hongxin,Zhang Xuejun,Zhou Min. Composition Operators on $ \boldsymbol{H^{p,q,s}}({\Bbb D})$ [J]. Acta mathematica scientia,Series A, 2023, 43(1): 1-13.
[2]	Lin Jie, Wang Tianyi. Well-Posedness and Convergence Rates of Three-Dimensional Incompressible Euler Flows in Axisymmetric Nozzles with Symmetric Body [J]. Acta mathematica scientia,Series A, 2023, 43(1): 219-237.
[3]	Yuting Guo,Xuejun Zhang. Composition Operators from Normal Weight General Function Spaces to Bloch Type Spaces [J]. Acta mathematica scientia,Series A, 2022, 42(5): 1306-1319.
[4]	Zhe Jia,Zuodong Yang. Global Boundedness in a Chemotaxis-Haptotaxis Model with Nonlinear Diffusion and Signal Production [J]. Acta mathematica scientia,Series A, 2021, 41(5): 1382-1395.
[5]	Juan Wang,Jie Zhao. Homogenization of the Oscillating Robin Mixed Boundary Value Problems [J]. Acta mathematica scientia,Series A, 2021, 41(1): 81-90.
[6]	Pengcheng Tang,Si Xu,Xuejun Zhang. Bergman Type Operators on Logarithmic Weight General Function Spaces in Cⁿ [J]. Acta mathematica scientia,Series A, 2020, 40(5): 1151-1162.
[7]	Juan Wang,Jie Zhao. Homogenization of Higher-Order Equations with Mixed Boundary Condition [J]. Acta mathematica scientia,Series A, 2020, 40(4): 925-933.
[8]	Yaoyao Han,Kai Zhao. Boundedness of Marcinkiewicz Integral and Its Commutator on Non-Homogeneous Metric Measure Spaces [J]. Acta mathematica scientia,Series A, 2020, 40(3): 597-610.
[9]	Si Xu,Xuejun Zhang. Weighted Composition Operator on the Normal Weight Zygmund Space in the Unit Ball [J]. Acta mathematica scientia,Series A, 2020, 40(2): 288-303.
[10]	Limin Zhang,Haiyan Xu,Chunhua Jin. Global Existence and Stability to a Prey-Taxis Model with Porous Medium Diffusion and Indirect Signal Production [J]. Acta mathematica scientia,Series A, 2019, 39(6): 1381-1404.
[11]	Juan Wang,Jie Zhao. Homogenization of the Neumann Boundary Value Problem: The Sharper W^{1, p} Estimate [J]. Acta mathematica scientia,Series A, 2019, 39(5): 1115-1124.
[12]	Yingjie Fu,Guijie Lan,Shuwen Zhang,Chunjin Wei. Dynamics of a Stochastic Predator-Prey Model with Pulse Input in a Polluted Environment [J]. Acta mathematica scientia,Series A, 2019, 39(3): 674-688.
[13]	Xueping Luo, Mengtian Cui. Solvability of Directional Perturbed Generalized Mixed Variational Inequalities in Reflexive Banach Spaces [J]. Acta mathematica scientia,Series A, 2018, 38(6): 1144-1152.
[14]	Yuting Guo,Qingli Shang,Xuejun Zhang. The Pointwise Multiplier on the Normal Weight Zygmund Space in the Unit Ball [J]. Acta mathematica scientia,Series A, 2018, 38(6): 1041-1048.
[15]	Wang Wansheng, Zhong Peng, Zhao Xinyang. Long-Time Stability of Nonlinear Neutral Differential Equations with Variable Delay [J]. Acta mathematica scientia,Series A, 2018, 38(1): 96-109.