非凸两分块优化问题的一类惯性对称正则化交替方向乘子法

doi:10.15960/j.cnki.issn.1007-6093.2023.03.003

Abstract

Abstract:

The alternating direction method of multipliers(ADMM) is an valid method for solving separable convex optimization problems, nevertheless, when the objective function has a nonconvex function, ADMM may not converge. This paper proposes an inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization problem with linear equality constraints. Under the appropriate hypothesis conditions, the global convergence of the algorithm is established. Secondly, When the benefit function satisfies the Kurdyka-Łojasiewicz(KL) property, the strong convergence of the algorithm is established. Finally, numerical experiments are performed on the algorithm, and the results show that the algorithm is an effective method.

Key words: the alternating direction method of multipliers, nonconvex optimization problem, Kurdyka-Łojasiewicz property, convergence

CLC Number:

O221.6

Jianwen PENG, Hongwang LEI. A class of inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization[J]. Operations Research Transactions, 2023, 27(3): 37-52.

Figures/Tables 3

References 31

1	AlexanderG J,RachfordH H.On the numerical solution of the heat conduction problem in 2 and 3 space variables[J].Transations of the American Mathematical Society,1956,82(2):421-439. doi: 10.1090/S0002-9947-1956-0084194-4
2	ChaoM T,ChenC Z,ZhangH B.A linearized alternating direction method of multipliers with substitution procedure[J].Asia Pacific Journal of Operational Research,2015,32(3):1550011. doi: 10.1142/S0217595915500116
3	GlowinskiR.Numerical Methods for Nonlinear Variational Problems[M].New York:Springer-Verlag,1984.
4	Gu Y, Jiang B, Han D R. A semi-proximal-based strictly contractive Peaceman-Rachford splitting method[J]. 2015, arXiv: 1506.02221.
5	HanD R,YuanX M.A not on the alternating direction method of multipliers[J].SIAM Journal on Numerical Analysis,2013,51(6):3446-3457. doi: 10.1137/120886753
6	HeB S,MaF,YuanX M.Convergence study on the symmetric version of ADMM with larger step sizes[J].SIAM Journal on Imaging Sciences,2016,9(3):1467-1501. doi: 10.1137/15M1044448
7	YangW H,HanD R.Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems[J].SIAM Journal on Numerical Analysis,2016,54(2):625-640. doi: 10.1137/140974237
8	LionP,MercierB.Splitting algorithms for the sum of two nonlinear operators[J].SIAM Journal on Numerical Analysis,1979,16(6):964-979. doi: 10.1137/0716071
9	PeacemanD W,RachfordH H.The numerical solution of parabolic and elliptic differential equations[J].Journal of the Society for Industrial and Applied Mathematics,1955,3(1):28-41. doi: 10.1137/0103003
10	Bai J C, Liang J L, Guo K, et al. Accelerated symmetric ADMM and its applications in signal processing[J]. 2019, arXiv: 1906.12015.
11	GuoK,HanD R,WuT T.Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints[J].International Journal of Computer Mathematics,2017,94(8):1653-1669. doi: 10.1080/00207160.2016.1227432
12	Wang F, Xu Z B, Xu H K. Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems[J]. 2014, arXiv: 1410.8625.
13	LiuM X,JianJ B.An ADMM-based SQP method for separably smooth nonconvex optimization[J].Journal of Inequalities and Applications,2020,2020(1):1-17. doi: 10.1186/s13660-019-2265-6
14	JianJ B,ZhangY,ChaoM T.A regularized alternating direction method of multiplier for a class of nonconvex problems[J].Journal of Inequalities and Applications,2019,2019(1):1-16. doi: 10.1186/s13660-019-1955-4
15	BotR I,NguyenD K.The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates[J].Mathematics of Operation Research,2018,45(2):1-13.
16	WuZ M,LiM,WangD,et al.A symmetric alternating direction method of multipliers for separable nonconvex minimization problems[J].Asia Pacific Journal of Operational Research,2017,34(6):1750030. doi: 10.1142/S0217595917500300
17	WangY,YinW T,ZengJ S.Global convergence of ADMM in nonconvex nonsmooth optimization[J].Journal of Scientific Computing,2018,2018,1-35. doi: 10.7561/SACS.2018.1.1
18	简金宝,刘鹏杰,江羡珍.非凸多分块优化部分对称正则化交替方向乘子法[J].数学学报,2021,64(6):1005-1026.
19	BotR I,CsetnekE R,LaszloS C.An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions[J].Euro Journal on Computational Optimization,2016,4(1):3-25. doi: 10.1007/s13675-015-0045-8
20	AlvarezF.Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space[J].SIAM Journal on Optimization,2004,14(3):773-782. doi: 10.1137/S1052623403427859
21	MoudafiA,ElizabethE.Approximate inertial proximal methods using the enlargement of maximal monotone operators[J].International Journal of Pure and Applied Mathematics,2003,5(3):283-299.
22	WuZ M,LiC,LiM.Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems[J].Journal of Global Optimization,2020,2020(6):1-28.
23	ChaoM T,ZhangY,JianJ B.An inertial proximal alternating direction method of multipliers for nonconvex optimization[J].International Journal of Computer Mathematics,2021,98(6):1199-1217. doi: 10.1080/00207160.2020.1812585
24	AlvarezF.On the minimizing property of a second order dissipative system in Hilbert space[J].SIAM Journal on Control and Optimization,2000,38(4):1102-1119. doi: 10.1137/S0363012998335802
25	XuZ B,ChangX,XuF,et al.$l$-$1/2$ regularization: a thresholding representation theory and a fast solver[J].IEEE Transactions on Neural Networks and Learning Systems,2012,23(7):1013-1027. doi: 10.1109/TNNLS.2012.2197412
26	ZengJ,FangJ,XuZ B.Sparse SAR imaging based on $l$-$1/2$ regularization[J].Science China Information Sciences,2012,55(8):39-59.
27	Arunachalam S, Saranya R, Sangeetha N. Hybrid artificial bee colony algorithm and simulated annealing algorithm for combined economic and emission dispatch including valve point effect[C]// International Conference on Swarm, Evolutionary, and Memetic Computing, 2013: 1-32.
28	RockafellarR T,WetsR J B.Variational Analysis[M].Berlin:Springer Science and Business Media,2009.
29	AttouchH,BolteJ,SvaiterB F.Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting and regularized Gauss-Seidel methods[J].Mathematical Programming,2013,137(1/2):91-129.
30	WangF H,CaoW F,XuZ B.Convergence of multi-block Bregman ADMM for nonconvex composite problems[J].Science China Information Sciences,2018,61(12):1-12.
31	NesterovY.Introductory Lectures on Convex Optimization: A Basic Course[M].New York:Springer,2004.

		ISRADMM		PSRADMM
$ m $	$ n $	iter(k)	Time/s	iter(k)	Time/s
500	600	100	1.180 8	114	1.534 5
600	700	97	1.679 5	114	2.216 4
700	800	96	2.468 8	114	3.301 1
800	900	94	3.278 6	115	4.410 8
900	1 000	93	4.284 4	115	5.716 4

[1]	ZENG Jing, DING Ruowen. Stability of solutions for a class of non-convex vector optimization problems with mapping differences [J]. Operations Research Transactions, 2023, 27(3): 121-128.
[2]	Maoran WANG, Xingju CAI, Zhongming WU, Deren HAN. First-order splitting algorithm for multi-model traffic equilibrium problems [J]. Operations Research Transactions, 2023, 27(2): 63-78.
[3]	LIU Pengjie, JIANG Xianzhen, SONG Dan. A class of spectral conjugate gradient method with sufficient descent property [J]. Operations Research Transactions, 2022, 26(4): 87-97.
[4]	Jiahao LYU, Honglin LUO, Zehua YANG, Jianwen PENG. A stochastic Bregman ADMM with its application in training sparse structure SVMs [J]. Operations Research Transactions, 2022, 26(2): 16-30.
[5]	Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization [J]. Operations Research Transactions, 2022, 26(2): 64-72.
[6]	Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem [J]. Operations Research Transactions, 2022, 26(2): 128-136.
[7]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[8]	ZHANG Liwei. Discussion on second-order analysis in augmented Lagrange method [J]. Operations Research Transactions, 2021, 25(3): 1-14.
[9]	Xueling ZHOU, Meixia LI, Haitao CHE. Successive relaxed projection algorithm for multiple-sets split equality problem [J]. Operations Research Transactions, 2021, 25(2): 93-103.
[10]	Biao QU, Wei XU, Xinyan WANG. A remark on the convergence of the two-subgradient extragradient algorithm for the variational inequality problem [J]. Operations Research Transactions, 2021, 25(2): 144-148.
[11]	Hai YU, Wanrong ZHAN. Strongly convergent ball-relaxed CQ algorithm and its application [J]. Operations Research Transactions, 2021, 25(1): 50-60.
[12]	Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems [J]. Operations Research Transactions, 2021, 25(1): 61-72.
[13]	PAN Shaohua, WEN Zaiwen. Models and algorithms for low-rank and sparse matrix optimization problems [J]. Operations Research Transactions, 2020, 24(3): 1-26.
[14]	MIAO Xiaonan, GU Jian, XIAO Xiantao. A cubic regularization method for solving nonsmooth equations [J]. Operations Research Transactions, 2019, 23(2): 17-30.
[15]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.

A class of inertial symmetric regularization alternating direction method of multipliers for nonconvex two-block optimization

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 31

Related Articles 15

Recommended Articles

Metrics

Comments