非凸复合优化问题的黄金比率邻近交替线性化算法

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

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 80-94.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.006

非凸复合优化问题的黄金比率邻近交替线性化算法

曾康¹, 龙宪军¹^,*()

1. 重庆工商大学数学与统计学院, 重庆 400067

收稿日期:2024-07-21 出版日期:2025-06-15 发布日期:2025-06-12
通讯作者: 龙宪军 E-mail:xianjunlong@ctbu.edu.cn
基金资助:
重庆市自然科学基金(CSTB2024NSCQ-MSX1282);重庆市研究生导师团队建设项目(yds223010);重庆工商大学研究生创新型科研项目(yjscxx2025-269-238)

A golden ratio proximal alternating linearized algorithm for nonconvex composite optimization problems

Kang ZENG¹, Xianjun LONG¹^,*()

1. School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067, China

Received:2024-07-21 Online:2025-06-15 Published:2025-06-12
Contact: Xianjun LONG E-mail:xianjunlong@ctbu.edu.cn

摘要/Abstract

摘要：

本文考虑一类完全非凸的复合优化问题, 其目标函数由如下两部分组成: 关于全局变量不可分的连续可微非凸函数, 与两个关于独立变量的正常下半连续非凸函数。本文提出一种求解该问题的新型黄金比率邻近交替线性化极小化算法。在Kurdyka-Lojasiewicz (简记KL)性质假设下, 证明了由算法产生的迭代序列收敛到问题的稳定点。最后将新算法应用于求解稀疏信号恢复问题, 数值实验验证了新算法的有效性与优越性。

关键词: 非凸复合优化问题, 黄金比率邻近交替线性化算法, KL性质, 收敛性

Abstract:

In this paper, we consider a class of nonconvex composite optimization problems, whose objective function is the sum of a continuous differentiable bifunction of the entire variables, and two proper lower semi-continuous nonconvex function of their private variables. We propose a new golden ratio proximal alternating linearized algorithm to solve this problem. Under the assumption of Kurdyka-Lojasiewicz (in short: KL) property, we prove the iterative sequence generated by the algorithm converges to the critical point of the problem. Finally, numerical results on sparse signal recovery illustrate the efficiency and superiority of the proposed algorithm.

Key words: nonconvex composite optimization problem, golden ration proximal alternating linearized algorithm, KL property, convergence

中图分类号:

O224

曾康, 龙宪军. 非凸复合优化问题的黄金比率邻近交替线性化算法[J]. 运筹学学报（中英文）, 2025, 29(2): 80-94.

Kang ZENG, Xianjun LONG. A golden ratio proximal alternating linearized algorithm for nonconvex composite optimization problems[J]. Operations Research Transactions, 2025, 29(2): 80-94.

图/表 7

表1

表2

图1

图2

图3

图4

表3

参考文献 16

4	Donoho D L . Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52, 1289- 1306. doi: 10.1109/TIT.2006.871582
5	Beck A . On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes[J]. SIAM Journal on Optimization, 2013, 25, 185- 209.
6	Ochs P , Brox T , Pock T . IPiasco: Inertial proximal algorithm for strongly convex optimization[J]. Journal of Mathematical Imaging and Vision, 2015, 53, 171- 181. doi: 10.1007/s10851-015-0565-0
7	Gao X , Cai X J , Han D R . A Gauss-Seidel type inertial proximal alternating linearized minimization for a class of nonconvex optimization problems[J]. Journal of Global Optimization, 2020, 76, 863- 887. doi: 10.1007/s10898-019-00819-5
8	Wang Q S , Han D R . A generalized inertial proximal alternating linearized minimization method for nonconvex nonsmooth problems[J]. Applied Numerical Mathematics, 2023, 189, 66- 87. doi: 10.1016/j.apnum.2023.03.014
9	Gao X , Cai X J , Wang X F , et al. An alternative structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant[J]. Journal of Global Optimization, 2023, 87, 277- 300. doi: 10.1007/s10898-023-01300-0
10	Chao M T , Nong F F , Zhao M Y . An inertial alternating minimization with Bregman distance for a class of nonconvex and nonsmooth problems[J]. Journal of Applied Mathematics and Computing, 2023, 69, 1559- 1581. doi: 10.1007/s12190-022-01799-8
11	Zhao J , Dong Q L , Rassias M T , et al. Two-step inertial Bregman proximal alternating minimization for nonconvex and nonsmooth problems[J]. Journal of Global Optimization, 2022, 84, 941- 966. doi: 10.1007/s10898-022-01176-6
12	Yang X , Xu L L . Some accelerated alternating proximal gradient algorithms for a class of nonconvex nonsmooth problems[J]. Journal of Global Optimization, 2023, 87, 939- 964. doi: 10.1007/s10898-022-01214-3
13	Malitsky Y . Golden ratio algorithms for variational inequalities[J]. Mathematical Programming, 2020, 184, 383- 410. doi: 10.1007/s10107-019-01416-w
14	Rockafellar R T , Wets R J B . Variational Analysis[M]. Berlin: Springer, 2009.
1	Attouch H , Bolte J , Redont P , et al. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality[J]. Mathematics of Operations Research, 2010, 35, 438- 457. doi: 10.1287/moor.1100.0449
2	Bolte J , Sabach S , Teboulle M . Proximal alternating linearized minimization for nonconvex and nonsmooth problems[J]. Mathematical Programming, 2014, 146, 459- 494. doi: 10.1007/s10107-013-0701-9
3	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[J]. Mathematical Programming, 2013, 137, 91- 129. doi: 10.1007/s10107-011-0484-9
15	Bolte J , Daniilidis A , Lewis A S , et al. Clark subgradients of stratifiable functions[J]. SIAM Journal on Optimization, 2007, 18, 556- 572. doi: 10.1137/060670080
16	Xu Z B , Chang X Y , Xu F M , 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, 1013- 27. doi: 10.1109/TNNLS.2012.2197412

算法	iter=500		iter=1 000		iter=1 500
算法	Time/s	res	Time/s	res	Time/s	res
算法1	18.259 4	0.245 0	36.343 8	0.225 0	54.802 5	0.222 8
GiPALM	18.406 3	0.982 6	36.703 1	0.983 9	54.921 9	0.984 4
PALM	18.546 9	1.045 5	37.312 5	0.983 8	56.283 1	0.993 6
NiPALM	18.781 3	1.731 7	36.656 3	1.701 3	56.375 0	1.701 3

算法	err=10^-3		err=10^-4		err=10^-5
算法	Time/s	res	Time/s	res	Time/s	res
算法1	18.259 4	0.245 0	18.012 0	0.245 0	18.000 0	0.236 5
GiPALM	18.406 3	0.982 6	18.156 3	0.982 6	18.493 8	0.982 6
PALM	18.546 9	1.045 5	18.593 8	1.045 5	18.546 9	1.045 5
NiPALM	18.781 3	1.731 7	19.140 6	1.731 7	19.171 9	1.632 0

算法	err=10^-3		err=10^-4		err=10^-5		err=10^-6
算法	Time/s	Iter	Time/s	Iter	Time/s	Iter	Time/s	Iter
算法1	2.125 0	56	3.468 8	92	5.281 3	130	6.328 1	170
PG	13.812 5	386	18.125 0	347	27.609 4	832	36.390 6	1 004
FPG	8.062 5	262	10.609 4	508	11.265 6	370	18.734 4	542

[1]	王晓. 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023, 27(4): 153-165.
[2]	彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.
[3]	刘鹏杰, 江羡珍, 宋丹. 一类具有充分下降性的谱共轭梯度法[J]. 运筹学学报, 2022, 26(4): 87-97.
[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]	周雪玲, 李梅霞, 车海涛. 多集分裂等式问题的逐次松弛投影算法[J]. 运筹学学报, 2021, 25(2): 93-103.
[8]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[9]	潘少华, 文再文. 低秩稀疏矩阵优化问题的模型与算法[J]. 运筹学学报, 2020, 24(3): 1-26.
[10]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[11]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[12]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[13]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[14]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[15]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.

非凸复合优化问题的黄金比率邻近交替线性化算法

A golden ratio proximal alternating linearized algorithm for nonconvex composite optimization problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 16

相关文章 15

编辑推荐

Metrics

本文评价