修正PRP共轭梯度方法求解无约束最优化问题

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

摘要/Abstract

摘要：

基于著名的PRP共轭梯度方法，利用CG_DESCENT共轭梯度方法的结构，本文提出了一种求解大规模无约束最优化问题的修正PRP共轭梯度方法。该方法在每一步迭代中均能够产生一个充分下降的搜索方向，且独立于任何线搜索条件。在标准Wolfe线搜索条件下，证明了修正PRP共轭梯度方法的全局收敛性和线性收敛速度。数值结果展示了修正PRP方法对给定的测试问题是非常有效的。

关键词: 无约束最优化, PRP共轭梯度法, Wolfe线搜索, 充分下降性, 全局收敛性

Abstract:

Based on the PRP conjugate gradient method, we propose an efficient modified PRP conjugate gradient method for solving large-scaled unconstrained optimization problems by using the structure of the CG_DESCENT conjugate gradient method. The proposed method generates a sufficient descent direction at each iteration, which is independent of any line search. Its global convergence and linear convergence rate are established under standard Wolfe line search. The numerical results show that the proposed methods is effective for the given test problems.

Key words: unconstrained optimization, PRP conjugate gradient method, Wolfe line search, sufficient descent, global convergence

中图分类号:

O224

张慧玲, 赛·闹尔再, 吴晓云. 修正PRP共轭梯度方法求解无约束最优化问题[J]. 运筹学学报, 2022, 26(2): 64-72.

Huiling ZHANG, Naoerzai SAI, Xiaoyun WU. Modified PRP conjugate gradient method for unconstrained optimization[J]. Operations Research Transactions, 2022, 26(2): 64-72.

图/表 3

表1

PRP方法和MPRP方法的数值结果"

Function	Dim	PRP方法			MPRP方法
Function	Dim	NI	CPU/s		NI	CPU/s
Freudenstein & Roth	3 000	926	2.24		95	0.18
	5 000	354	1.35		17	0.01
Trigonometric	3 000	29	0.07		29	0.07
	5 000	29	0.08		29	0.09
Rosenbrock	3 000	50	0.01		45	0.02
	5 000	46	0.03		44	0.01
Beale	3 000	28	0.01		37	0.02
	5 000	19	0.02		37	0.01
Perturbed Quadratic	3 000	545	0.18		542	0.17
	5 000	859	0.47		970	0.52
Diagonal 2	3 000	10 001	17.55		552	0.51
	5 000	10 001	28.48		512	0.88
Diagonal 3	3 000	5 529	102.89		4 924	98
	5 000	10 001	353.97		2 391	30.28
Hager	3 000	1 110	17.95		1 066	18.26
	5 000	1 318	35.17		1 653	44.5
Extended Tridiagonal 1	3 000	19	0.01		27	0.02
	5 000	41	0.04		31	0.01
Generalized Tridiagonal 2	3 000	73	0.03		86	0.03
	5 000	62	0.04		70	0.05
Generalized PSC1	3 000	10 001	20.88		876	1.07
	5 000	10 001	35.81		2 079	3.93
Extended Powell	3 000	142	0.03		514	0.14
	5 000	283	0.14		137	0.08
Extended Maratos	3 000	98	0.03		162	0.05
	5 000	100	0.06		150	0.06
Extended Cliff	3 000	44	0.03		40	0.03
	5 000	17	0.03		17	0.03
Quadratic Diagonal Perturbed	3 000	723	0.25		486	0.17
	5 000	584	0.36		579	0.38
Extended Wood	3 000	78	0.02		34	0.01
	5 000	40	0.03		224	0.11
Quadratic QF1	3 000	596	0.17		580	0.22
	5 000	1 039	0.55		859	0.48
Extended Quadratic Penalty QP1	3 000	4 281	11.32		28	0.04
	5 000	1 337	5.83		1 090	5.75
Extended Quadratic Penalty QP2	3 000	65	0.1		52	0.08
	5 000	56	0.12		46	0.12
Quadratic QF2	3 000	653	0.22		831	0.26
	5 000	10 001	913.13		870	0.52
TRIDIA (CUTE)	3 000	4 246	1.34		3 734	1.16
	5 000	2 628	1.47		4 237	2.26
ARWHEAD (CUTE)	3 000	77	0.12		33	0.02
	5 000	10 001	23.69		17	0.03
NONDQUAR (CUTE)	3 000	10 001	14.48		3 092	1.36
	5 000	10 001	24		3 777	2.72
DIXMAANE (CUTE)	3 000	482	0.38		434	0.32
	5 000	10 001	26.56		606	0.78
Partial Perturbed Quadratic	3 000	414	27.12		332	21.55
	5 000	119	23.61		129	24.93
Broyden Tridiagonal	3 000	63	0.02		72	0.01
	5 000	65	0.04		68	0.05
Almost Perturbed Quadratic	3 000	651	0.21		685	0.22
	5 000	991	0.48		776	0.37
Tridiagonal Perturbed Quadratic	3 000	627	0.22		641	0.22
	5 000	886	0.52		881	0.51
EDENSCH (CUTE)	3 000	74	0.17		59	0.15
	5 000	91	0.36		64	0.21
LIARWHD (CUTE)	3 000	56	0.03		63	0.04
	5 000	43	0.04		29	0.01
DIXMAANG (CUTE)	3 000	10 001	16.91		680	1.35
	5 000	10 001	28.36		705	2.15
DIXMAANH (CUTE)	3 000	10 001	24.61		643	2.15
	5 000	10 001	48.65		779	3.3
DIXMAANI (CUTE)	3 000	10 001	16.28	433	0.34
	5 000	10 001	26.97	641	0.94
DIXMAANJ (CUTE)	3 000	10 001	16.46	534	1.08
	5 000	10 001	27.37	1 449	5.2
DIXMAANK (CUTE)	3 000	10 001	17.61	1 200	5.32
	5 000	10 001	28	1 766	6.7

表1

图1

图2

参考文献 20

1	Polak E , Ribire G . Note sur la xonvergence de directions conjugees[J]. Rev Francaise informat Recherche Operatinelle 3e Annee, 1969, 16, 35- 43.
2	Polyak B T . The conjugate gradient method in extreme problems[J]. USSR Computational Mathematics and Mathematical Physics, 1969, 9, 94- 112. doi: 10.1016/0041-5553(69)90035-4
3	Powell M J D . Convergence properties of algorithms for nonlinear optimization[J]. SIAM Review, 1986, 28, 487- 500. doi: 10.1137/1028154
4	Gilbert J C , Nocedal J . Global convergence properties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992, 2, 21- 42. doi: 10.1137/0802003
5	Hestenes M R , Stiefel E L . Methods of conjugate gradients for solving linear systems[J]. Journal of Research of the National Bureau of Standards, 1952, 5, 409- 432.
6	Hager W W , Zhang H . A new conjugate gradient method with guaranteed descent and an efficient line search[J]. SIAM Journal on Optimization, 2005, 16, 170- 192. doi: 10.1137/030601880
7	Liu J K . A new nonlinear conjugate gradient method and its global convergence[J]. 数学杂志, 2013, 33, 1036- 1042.
8	赛·闹尔再, 张慧玲. 修正LS共轭梯度方法及其收敛性[J]. 西南师范大学学报(自然科学版), 2016, 41, 20- 26.
9	刘金魁, 张春涛. 三项修正LS共轭梯度方法及其收敛性研究[J]. 应用数学学报, 2017, 40, 862- 873.
10	Saman B K , Reza G . A class of adaptive Dai-Liao conjugate gradient methods based on the scaled memoryless BFGS update[J]. 4OR-A Quarterly Journal of Operations Research, 2017, 15, 85- 92. doi: 10.1007/s10288-016-0323-1
11	Dong X L , Han D R , Dai Z F , et al. An accelerated three-term conjugate gradient method with sufficient descent condition and conjugacy condition[J]. Journal of Optimization Theory and Applications, 2018, 179, 944- 961. doi: 10.1007/s10957-018-1377-3
12	Jian J B , Yang L , Jiang X Z , et al. A spectral conjugate gradient method with descent property[J]. Mathematics, 2020, 8, 280. doi: 10.3390/math8020280
13	Liu M X , Yin J H , Ma G D . Two new conjugate gradient methods for unconstrained optimization[J]. Complexity, 2020, 2020.
14	Awwal A M , Kumam P , Abubakar A B . Spectral modified Polak-Ribiére-Polyak projection conjugate gradient method for solving monotone systems of nonlinear equations[J]. Applied Numerical Mathematics, 2019, 362, 124514.
15	Yuan G L , Li T T , Hu W J . A conjugate gradient algorithm for large-scale nonlinear equations and image restoration problems[J]. Applied Numerical Mathematics, 2020, 147, 129- 141. doi: 10.1016/j.apnum.2019.08.022
16	Zoutendijk G . Nonlinear programming, computational methods[J]. Integer and Nonlinear Programming, 1970, 37- 86.
17	Liu J K , Feng Y M , Zou L M . Some three-term conjugate gradient methods with the inexact line search condition[J]. Calcolo, 2018, 55, 16. doi: 10.1007/s10092-018-0258-3
18	Bongartz I , Conn A R , Gould N I M , et al. CUTE: constrained and unconstrained testing environments[J]. ACM Transactions on Mathematical Software, 1995, 21, 123- 160. doi: 10.1145/200979.201043
19	Andrei N . An unconstrained optimization test functions collection[J]. Advanced Modeling and Optimization, 2008, 10, 147- 161.
20	Dolan E D , Moré J J . Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2002, 91, 201- 213. doi: 10.1007/s101070100263

[1]	单锡泉, 李梅霞, 刘瑾瑜. 求解张量随机互补问题的光滑牛顿算法[J]. 运筹学学报, 2022, 26(2): 128-136.
[2]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[3]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[4]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[5]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[6]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[7]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[8]	赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.
[9]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[10]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.