Behavior of the combination of PRP and HZ methods for unconstrained optimization

Sarra Delladji; Mohammed Belloufi; Badreddine Sellami

doi:10.3934/naco.2020032

Article Contents

2021, Volume 11, Issue 3: 377-389. Doi: 10.3934/naco.2020032

This issue Previous Article Optimal control of viral infection model with saturated infection rate Next Article Dynamics of a stage structure prey-predator model with ratio-dependent functional response and anti-predator behavior of adult prey

Behavior of the combination of PRP and HZ methods for unconstrained optimization

Laboratory Informatics and Mathematics (LiM), Mohamed Cherif Messaadia University, Souk Ahras, 41000, Algeria

^* Corresponding author
^* Corresponding author

Received: January 2020

Revised: April 2020

Early access: May 2020

Published: September 2021

Abstract Full Text(HTML) Figure(2) / Table(1) Related Papers Cited by

Abstract

To achieve a conjugate gradient method which is strong in theory and efficient in practice for solving unconstrained optimization problem, we propose a hybridization of the Hager and Zhang (HZ) and Polak-Ribière and Polyak (PRP) conjugate gradient methods which possesses an important property of the well known PRP method: the tendency to turn towards the steepest descent direction if a small step is generated away from the solution, averting a sequence of tiny steps from happening, the new scalar $ \beta_k $ is obtained by convex combination of PRP and HZ under the wolfe line search we prove the sufficient descent and the global convergence. Numerical results are reported to show the effectiveness of our procedure.

Keywords:

Mathematics Subject Classification: 49M07; 49M10; 90C06; 65K05; 90C26; 65H10.

Citation:

Full Text(HTML)

Figure 1.

Download: Full-size image PowerPoint slide

Figure 2.

Download: Full-size image PowerPoint slide

Table 1.

Problems	n	hPRPHZ		PRP		HZ
		time	iter	time	iter	time	iter
FLETCHCR	5000	95.6800	34677	123.9500	456454	84.2000	40000
CURLY30	1000	8.8600	15122	8.8700	15401	NaN	NaN
CURLY20	1000	10.9100	15084	6.9600	15797	NaN	NaN
DIXMAANI	6000	9.4300	2661	9.0600	2261	13.9800	4720
EIGENBLS	420	3.5500	4978	10.1100	5440	14.9300	9714
TRIDIA	10 000	7.3200	1116	3.1900	1116	3.8900	2231
NONDQUAR	5000	4.2400	5099	7.5000	5058	9.4700	10058
CURLY10	1000	4.2700	14406	4.0600	13659	NaN	NaN
EIGENCLS	462	4.2500	1802	4.1000	1883	5.9900	3312
SPARSINE	1000	2.5700	4516	4.3200	4483	6.5900	8793
EIGENALS	420	3.9700	1344	2.4900	1306	4.7400	2998
FLETCHCR	1000	6.0300	7479	4.9300	9139	3.5700	8986
GENHUMPS	1000	2.2400	3555	5.8400	3435	7.5500	5807
FMINSURF	5625	1.0000	492	3.4700	669	3.3900	949
TRIDIA	5000	1.0900	783	1.0700	783	1.3100	1565
DIXMAANE	6000	1.2200	303	1.2600	306	2.1300	620
DIXMAANJ	6000	23.8000	296	1.1800	275	2.1700	557
BDQRTIC	5000	1.3500	8726	7.6400	2428	NaN	NaN
DIXMAANK	6000	1.8100	264	1.1100	248	1.8000	587
NONCVXU2	1000	1.5600	2055	1.9200	2015	3.6400	3919
DIXMAANL	6000	0.9700	245	1.3200	215	3.0100	702
SENSORS	100	1.0700	44	0.9700	45	1.3600	66
DIXMAANF	6000	1.0400	230	1.1200	230	1.6200	437
DIXMAANG	6000	1.3400	227	1.0800	227	1.4500	420
DIXMAANH	6000	0.9900	224	1.1600	224	2.6400	825
FLETCBV2	1000	1.4000	1055	1.0000	1044	1.2900	1886
SCHMVETT	10 000	2.3800	60	1.5000	64	2.5900	105
GENHUMPS	500	1.0100	2258	2.1500	2531	2.7000	4147
CRAGGLVY	5000	0.7400	143	0.9900	138	NaN	NaN
MOREBV	10 000	1.1900	97	0.8900	97	1.2800	201
WOODS	10 000	0.8400	257	1.1700	230	2.1400	487
NONDQUAR	1000	0.3800	3147	1.4500	4900	1.6300	8128
SPARSQUR	10 000	0.3500	23	0.3800	23	1.1300	131
POWER	5000	0.6500	259	0.6100	408	0.4000	514
MANCINO	100	0.3500	12	0.6000	11	1.1500	27
CRAGGLVY	2000	0.3300	132	0.3700	142	NaN	NaN
CURLY30	200	0.4800	2819	0.3600	3066	NaN	NaN
LIARWHD	10 000	0.5700	41	0.4600	39	0.4800	46
BDQRTIC	1000	0.4600	1025	0.4900	798	NaN	NaN
GENROSE	500	0.2900	1309	0.4900	1624	0.4600	2278
VARDIM	10 000	0.2700	62	0.2900	57	NaN	NaN
CURLY20	200	0.7100	2951	0.3000	2835	NaN	NaN
FREUROTH	5000	0.4000	96	0.5900	76	NaN	NaN
ENGVAL1	10 000	0.2800	35	0.4100	34	NaN	NaN
POWELLSG	10 000	0.2500	77	0.2300	49	0.7200	362
DIXON3DQ	1000	0.3100	1002	0.2700	1002	0.3300	2005
BRYBND	5000	0.4500	39	0.3200	40	0.3800	66
HILBERTA	200	0.7100	50	0.3700	25	0.3800	38
TQUARTIC	10 000	0.1900	61	0.6500	52	0.5800	38
CURLY10	200	0.2100	3100	0.2000	3182	NaN	NaN
FLETCBV2	500	0.2600	480	0.2200	482	0.3600	962
FMINSURF	1024	0.1200	238	0.2400	300	0.2800	455
VARDIM	5000	0.2000	44	0.1300	47	NaN	NaN
FMINSRF2	1024	0.1400	282	0.2600	355	0.2900	517
SPMSRTLS	1000	0.2400	151	0.1500	151	0.2000	281
LIARWHD	5000	0.2600	32	0.3000	48	0.2500	46
NONDIA	10 000	0.2600	16	0.2300	10	0.3100	26
POWELLSG	5000	0.5500	187	0.1100	53	0.3200	346
ARWHEAD	10 000	0.1600	15	0.5300	12	NaN	NaN
SROSENBR	10 000	0.1900	17	0.1700	19	0.1700	26
TQUARTIC	5000	0.1700	38	0.2100	54	0.1700	32
PENALTY1	5000	0.2500	62	0.2200	80	0.3400	152
DQDRTIC	10 000	0.1300	8	0.2600	8	0.2700	15
NONDIA	5000	0.2200	22	0.1400	26	0.1300	26
ARGLINB	300	0.1300	23	0.2000	17	NaN	NaN
DIXMAAND	6000	0.2500	13	0.1300	12	0.1600	25
ARGLINC	300	0.0800	19	0.2700	25	NaN	NaN
DQRTIC	5000	0.0900	34	0.1000	34	0.1000	66
QUARTC	5000	0.0900	34	0.0900	34	0.1000	66
EIGENALS	110	0.0400	389	0.0800	359	0.1600	806
SINQUAD	500	0.0800	111	0.0400	93	NaN	NaN
SPARSINE	200	0.0600	445	0.0800	445	0.1300	917
DIXON3DQ	500	0.2400	500	0.0600	500	0.0800	1003
DIXMAANC	6000	0.2200	11	0.2400	11	0.2600	23
HILBERTB	200	0.2100	6	0.2200	6	0.2500	13
BROWNAL	400	0.0700	13	0.2000	7	0.2700	37
EIGENCLS	90	0.2500	360	0.0700	350	0.1100	743
ARGLINA	300	0.2300	2	0.2500	2	0.2600	5
EXTROSNB	50	0.1300	5819	0.1900	5294	0.2400	7808
PENALTY2	200	0.1800	365	0.1400	417	NaN	NaN
FREUROTH	1000	0.0700	187	0.1600	137	NaN	NaN
BRYBND	1000	0.0600	52	0.0600	35	0.0800	73
DIXMAANB	3000	0.0400	10	0.0600	10	0.0700	23
NONCVXU2	100	0.0600	396	0.0300	414	0.0500	801
DIXMAANA	3000	0.2100	10	0.0500	9	0.0700	20
TOINTGSS	10 000	0.0300	5	0.2100	5	0.3800	20
POWER	1000	0.0600	117	0.0600	222	0.0400	236
DECONVU	61	0.0200	462	0.0600	460	0.0700	581
GENROSE	100	0.0200	347	0.0200	392	0.0300	626
COSINE	1000	0.0300	24	0.0200	24	0.0300	29
DIXMAANB	1500	0.0100	10	0.0300	10	0.0400	24
CHNROSNB	50	0.0300	273	0.0200	285	0.0100	500
DIXMAANA	1500	0.0100	10	0.0300	9	0.0300	22
FMINSRF2	121	0.0300	115	0.0100	124	0.0100	250
ARWHEAD	1000	0.0100	16	0.0300	19	NaN	NaN
COSINE	500	0.0200	23	0	22	0.0100	26
DQDRTIC	1000	0.0600	8	0.0200	8	0.0300	15
ERRINROS	50	0.0200	1444	0.0900	2416	NaN	NaN
EG2	1000	0.0100	6	0.0100	6	NaN	NaN
TESTQUAD	100	0.0100	321	0.0100	303	0.0100	925
TOINTGOR	50	0.8800	151	0.0100	155	0.0100	250
SPARSINE	5000	0.1300	370	1.5700	544	1.1200	719
FMINSRF2	10 000	0.2800	26	0.1200	23	0.1300	27
FMINSRF2	15 625	1.1300	28	0.2600	23	0.2800	28
FMINSRF2	5625	3.0500	227	1.3100	214	1.8900	430
NONDQUAR	10 000	1.3200	234	2.4200	225	3.5200	440
POWER	10 000	43.7500	142	0.7100	62	NaN	NaN
ARWHEAD	5000	0.2100	7298	36.8400	6398	NaN	NaN
COSINE	5000	59.1900	37	0.2000	35	NaN	NaN
COSINE	10 000	3.6600	8476	31.5200	4721	53.2500	8965
FMINSURF	10 000	0.6400	8771	2.1400	5022	2.4100	6779
FMINSURF	15 625	0.3600	108	0.4700	62	NaN	NaN
BROYDN7D	1000	5.3900	498	0.2700	371	NaN	NaN
SPMSRTLS	4999	0.0010	2232	5.4700	2183	6.4500	4093
SPMSRTLS	10 000	0.0010	NaN	NaN	NaN	0.2800	NaN
FREUROTH	10 000	0.0010	NaN	NaN	NaN	1.8900	NaN
FLETCBV2	500	0.0010	NaN	NaN	NaN	3.5200	NaN
BDQRTIC	10 000	0.0010	1	NaN	NaN	0.2800	NaN
VAREIGVL	10 000	0.0010	1	NaN	NaN	1.8900	NaN
ENGVAL1	5000	NaN	1	NaN	NaN	3.5200	NaN
BRYBND	10 000	0.1000	34677	0.5000	456454	0.9000	40000
EIGENBLS	930	0.1000	15122	0.0500	15401	0.9000	NaN
NONCVXUN	500	0.1000	15084	0.0500	15797	0.9000	NaN
GENROSE	1000	0.1000	2661	0.5000	2261	0.9000	4720
GENROSE	5000	0.1000	4978	0.0500	5440	0.9000	9714
EIGENALS	930	0.1000	1116	0.0500	1116	0.9000	2231
SINQUAD	5000	0.1000	5099	0.5000	5058	0.9000	10058
SINQUAD	10 000	0.1000	14406	0.0500	13659	0.9000	NaN
GENHUMPS	5000	0.1000	1802	0.0500	1883	0.9000	3312
CHAINWOO	1000	0.1000	4516	0.5000	4483	0.9000	8793
TESTQUAD	1000	0.1000	1344	0.0500	1306	0.9000	2998
TESTQUAD	10 000	0.1000	7479	0.0500	9139	0.9000	8986
TESTQUAD	5000	0.1000	3555	0.5000	3435	0.9000	5807
FLETCHCR	5000	0.1000	492	0.0500	669	0.9000	949
CURLY30	1000	0.1000	783	0.0500	783	0.9000	1565
CURLY20	1000	0.1000	303	NaN	306	0.9000	620
DIXMAANI	6000	0.1000	296	NaN	275	0.9000	557
EIGENBLS	420	0.1000	8726	NaN	2428	0.9000	NaN

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	M. Al-Baali, Descent property and global convergence of the Fletcher–Reeves method with inexact line search, IMA Journal of Numerical Analysis, 5 (1985), 121-124. doi: 10.1093/imanum/5.1.121.
[2]	N. Andrei, Another hybrid conjugate gradient algorithm for unconstrained optimization, Numerical Algorithms, 47 (2008), 143-156. doi: 10.1007/s11075-007-9152-9.
[3]	N. Andrei, New hybrid conjugate gradient algorithms for unconstrained optimization, in Encyclopedia of Optimization(eds. A. F. Christodoulos and M. P. Panos), 2009. doi: 10.1007/978-0-387-74759-0_441.
[4]	B. Balaram, M. Narayanan and P. Rajendrakumar, Optimal design of multi-parametric nonlinear systems using a parametric continuation based genetic algorithm approach, Nonlinear Dynamics, 67 (2012), 2759-2777. doi: 10.1007/s11071-011-0187-z.
[5]	I. Bongartz, A. R. Conn, N. Gould and P. L. Toint, CUTE: constrained and unconstrained testing environments, ACM Transactions on Mathematical Software (TOMS), 21 (1995), 123-160.
[6]	N. Chenna, Comments on "New Hybrid Conjugate Gradient Method as a Convex Combination of FR and PRP Methods", FILOMAT, 33 (2019), 3083-3100.
[7]	Y.-H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10 (1999), 177-182. doi: 10.1137/S1052623497318992.
[8]	S. S. Djordjević, New hybrid conjugate gradient method as a convex combination of FR and PRP methods, Filomat, 30 (2016), 3083-3100. doi: 10.2298/FIL1611083D.
[9]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.
[10]	W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16 (2005), 170-192. doi: 10.1137/030601880.
[11]	X. Z. Jiang, G.-D. Ma and J.-B. Jian, A new global convergent conjugate gradient method with Wolfe line search, Chinese Journal of Engineering Mathematics, 28 (2011), 779-786.
[12]	J. Liu and S. Li, New hybrid conjugate gradient method for unconstrained optimization, Applied Mathematics and Computation, 245 (2014), 36-43. doi: 10.1016/j.amc.2014.07.096.
[13]	E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées, Revue Française D'informatique et De Recherche Opérationnelle, Série Rouge, 3 (1969), 35–43.
[14]	B. T. Polyak, The conjugate gradient method in extremal problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112.
[15]	M. Powell, Nonconvex minimization calculations and the conjugate gradient method, Numerical Analysis(ed. D. F.Griffiths), Volume 1066 of Lecture Notes in Math., Dundee, (1984), 122–141. doi: 10.1007/BFb0099521.
[16]	Z. Wei, G. Li and L. Qi, New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems, Applied Mathematics and Computation, 179 (2006), 407-430. doi: 10.1016/j.amc.2005.11.150.
[17]	G. Yuan, Z. Wei and Q. Zhao, A modified Polak–Ribière–Polyak conjugate gradient algorithm for large-scale optimization problems, IIE Transactions, 46 (2014), 397-413. doi: 10.1080/01630563.2013.777350.
[18]	G. Zoutendijk, Nonlinear programming, computational methods, Integer and Nonlinear Programming, (1970), 37–86.