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

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

Abstract

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

CLC Number:

O224

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.

Figures/Tables 7

References 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]	ZHANG Yuru, ZHANG Xue, LAN Ru. A variable metric extrapolation hard threshold algorithm for some linear inverse problem [J]. Operations Research Transactions, 2025, 29(2): 158-174.
[2]	FENG Xudong, JIA Wensheng. An approximation theorem and generic convergence for generalized weakly-mixed vector quasi-equilibrium problem [J]. Operations Research Transactions, 2025, 29(2): 201-213.
[3]	Xiao WANG. Stochastic approximation methods for nonconvex constrained optimization [J]. Operations Research Transactions, 2023, 27(4): 153-165.
[4]	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.
[5]	Jing ZENG, Ruowen DING. Stability of solutions for a class of non-convex vector optimization problems with mapping differences [J]. Operations Research Transactions, 2023, 27(3): 121-128.
[6]	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.
[7]	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.
[8]	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.
[9]	Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization [J]. Operations Research Transactions, 2022, 26(2): 64-72.
[10]	Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem [J]. Operations Research Transactions, 2022, 26(2): 128-136.
[11]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[12]	ZHANG Liwei. Discussion on second-order analysis in augmented Lagrange method [J]. Operations Research Transactions, 2021, 25(3): 1-14.
[13]	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.
[14]	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.
[15]	Hai YU, Wanrong ZHAN. Strongly convergent ball-relaxed CQ algorithm and its application [J]. Operations Research Transactions, 2021, 25(1): 50-60.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 16

Related Articles 15

Recommended Articles

Metrics

Comments