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

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

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 37-52.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.003

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

彭建文¹^,*(), 雷宏旺¹

1. 重庆师范大学数学科学学院, 重庆 401331

收稿日期:2021-04-21 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 彭建文 E-mail:jwpeng168@hotmail.com
作者简介:彭建文, E-mail: jwpeng168@hotmail.com
基金资助:
国家自然科学基金重大项目(11991024);国家自然科学基金面上项目(12271071);重庆英才·创新创业领军人才·创新创业示范团队项目(CQYC20210309536);重庆市高校创新研究群体项目(CXQT20014);重庆市自然科学基金(cstc2021jcyj-msxmX0300)

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

Jianwen PENG¹^,*(), Hongwang LEI¹

1. College of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China

Received:2021-04-21 Online:2023-09-15 Published:2023-09-14
Contact: Jianwen PENG E-mail:jwpeng168@hotmail.com

摘要/Abstract

摘要：

交替方向乘子法(ADMM)是一个求解可分离凸优化问题的的有效方法，然而，当目标函数存在非凸函数时，ADMM或许不收敛。本文提出一类带线性等式约束的非凸两分块优化问题的惯性对称正则化交替方向乘子法。在适当的假设条件下，建立了算法的全局收敛性。其次，在效益函数满足Kurdyka-Łojasiewicz (KL)性质时，建立了算法的强收敛性。最后，对算法进行了数值实验，结果说明算法是一种有效的方法。

关键词: 交替方向乘子法, 非凸优化问题, Kurdyka-Łojasiewicz (KL)性质, 收敛性

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

中图分类号:

O221.6

彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.

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.

图/表 3

参考文献 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]	王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.
[2]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[3]	谢文蕙, 凌晨, 潘晨健. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用[J]. 运筹学学报, 2022, 26(3): 31-43.
[4]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[5]	张慧玲, 赛·闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.
[6]	单锡泉, 李梅霞, 刘瑾瑜. 求解张量随机互补问题的光滑牛顿算法[J]. 运筹学学报, 2022, 26(2): 128-136.
[7]	王双月, 罗自炎. 一类基于L_0/1软间隔损失函数的低秩支持张量机[J]. 运筹学学报, 2021, 25(3): 160-172.
[8]	周雪玲, 李梅霞, 车海涛. 多集分裂等式问题的逐次松弛投影算法[J]. 运筹学学报, 2021, 25(2): 93-103.
[9]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[10]	潘少华, 文再文. 低秩稀疏矩阵优化问题的模型与算法[J]. 运筹学学报, 2020, 24(3): 1-26.
[11]	陈彩华. 多块交替方向乘子法不收敛反例的几点注记[J]. 运筹学学报, 2019, 23(3): 135-140.
[12]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[13]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[14]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[15]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 31

相关文章 15

编辑推荐

Metrics

本文评价