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

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

Abstract

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

CLC Number:

O224

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

Figures/Tables 3

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

References 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]	Xiquan SHAN, Meixia LI, Jinyu LIU. Smoothing Newton method for the tensor stochastic complementarity problem [J]. Operations Research Transactions, 2022, 26(2): 128-136.
[2]	Liyuan CUI, Shouqiang DU. Projected Levenberg-Marquardt method for stochastic R₀ tensor complementarity problems [J]. Operations Research Transactions, 2021, 25(4): 69-79.
[3]	SUN Cong, ZHANG Ya. A brief review on gradient method [J]. Operations Research Transactions, 2021, 25(3): 119-132.
[4]	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.
[5]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[6]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[7]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[8]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[9]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[10]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[11]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.
[12]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[13]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[14]	LIU Yuanyuan, OU Yigui. An ODE-based hybrid method based on the nonmonotone technique [J]. Operations Research Transactions, 2013, 17(3): 11-22.
[15]	DU Shouqiang. Global convergence of the Levenberg-Marquardt method with Goldstein line search [J]. Operations Research Transactions, 2012, 16(4): 105-111.

Modified PRP conjugate gradient method for unconstrained optimization

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 20

Related Articles 15

Recommended Articles

Metrics

Comments