A new modified three-term conjugate gradient method with sufficient descent property and its global convergence. (English) Zbl 1461.90166
Summary: A new modified three-term conjugate gradient (CG) method is shown for solving the large scale optimization problems. The idea relates to the famous Polak-Ribière-Polyak (PRP) formula. As the numerator of PRP plays a vital role in numerical result and not having the jamming issue, PRP method is not globally convergent. So, for the new three-term CG method, the idea is to use the PRP numerator and combine it with any good CG formula’s denominator that performs well. The new modification of three-term CG method possesses the sufficient descent condition independent of any line search. The novelty is that by using the Wolfe Powell line search the new modification possesses global convergence properties with convex and nonconvex functions. Numerical computation with the Wolfe Powell line search by using the standard test function of optimization shows the efficiency and robustness of the new modification.
Software:
minpackReferences:
| [1] | Nocedal, J.; Nazareth, J. L., Conjugate gradient methods and nonlinear optimization, Linear and Nonlinear Conjugate Gradient Related Methods, 9-23 (1995), Philadelphia, PA, USA: SIAM, Philadelphia, PA, USA · Zbl 0866.65037 |
| [2] | Polak, E., Optimization: Algorithms and Consistent Approximations (1997), New York, NY, USA: Springer, New York, NY, USA · Zbl 0899.90148 |
| [3] | Ziadi, R.; Ellaia, R.; Bencherif-Madani, A., Global optimization through a stochastic perturbation of the Polak-Ribière conjugate gradient method, Journal of Computational and Applied Mathematics, 317, 672-684 (2017) · Zbl 1381.90069 · doi:10.1016/j.cam.2016.12.021 |
| [4] | Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49, 409-436 (1953) (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [5] | Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, The Computer Journal, 7, 149-154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 |
| [6] | Polak, E.; Ribière, G., Note Sur la convergence de directions conjugeès, Rev, Revue Française d’Informatique et de Recherche Opérationnelle, 3, 16, 35-43 (1969) · Zbl 0174.48001 · doi:10.1051/m2an/196903R100351 |
| [7] | Polyak, B. T., The conjugate gradient method in extreme problems, USSR Computational Mathematics and Mathematical Physics, 9, 4, 94-112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4 |
| [8] | Fletcher, R., Practical Method of Optimization, Vol. I: Unconstrained Optimization (1997), New York, NY, USA: Wiley, New York, NY, USA |
| [9] | Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms. I. Theory, Journal of Optimization Theory and Applications, 69, 1, 129-137 (1991) · Zbl 0702.90077 · doi:10.1007/BF00940464 |
| [10] | Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient with a strong global convergence properties, SIAM Journal on Optimization, 10, 1, 177-182 (2000) · Zbl 0957.65061 · doi:10.1137/S1052623497318992 |
| [11] | Alhawarat, A.; Mamat, M.; Rivaie, M.; Salleh, Z., An efficient hybrid conjugate gradient method with the strong Wolfe-Powell line search, Mathematical Problems in Engineering, 2015 (2015) · Zbl 1394.90556 · doi:10.1155/2015/103517 |
| [12] | Alhawarat, A.; Salleh, Z.; Mamat, M.; Rivaie, M., An efficient modified Polak-Ribière-Polyak conjugate gradient method with global convergence properties, Optimization Methods and Software, 1-14 (2016) · Zbl 1379.49028 · doi:10.1080/10556788.2016.1266354 |
| [13] | Alhawarat, A.; Salleh, Z., Modification of nonlinear conjugate gradient method with weak Wolfe-Powell line search, Abstract and Applied Analysis (2017) · Zbl 1470.90158 · doi:10.1155/2017/7238134 |
| [14] | Salleh, Z.; Alhawarat, A., An efficient modification of the Hestenes-Stiefel nonlinear conjugate gradient method with restart property, Journal of Inequalities and Applications, 2016, 1, article no. 110 (2016) · Zbl 1337.65048 · doi:10.1186/s13660-016-1049-5 |
| [15] | Beale, E. M.; Lootsma, F. A., A derivative of conjugate gradients, Numerical Methods for Nonlinear Optimization, 39-43 (1972), Academic Press, London · Zbl 0279.65052 |
| [16] | McGuire, M. F.; Wolfe, P., Evaluating a Restart Procedure for Conjugate Gradients (1973), Yorktown Heights: IBM Research Center, Yorktown Heights |
| [17] | Nazareth, L., A conjugate direction algorithm without line searches, Journal of Optimization Theory and Applications, 23, 3, 373-387 (1977) · Zbl 0348.65061 · doi:10.1007/BF00933447 |
| [18] | Deng, N. Y.; Li, Z., Global convergence of three terms conjugate gradient methods, Optim. Method Softw, 4, 273-282 (1995) |
| [19] | Dai, Y. H.; Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10, 1, 177-182 (1999) · Zbl 0957.65061 · doi:10.1137/S1052623497318992 |
| [20] | Zhang, L.; Zhou, W.; Li, D.-H., A descent modified Polak-Ribiére-Polyak conjugate gradient method and its global convergence, IMA Journal of Numerical Analysis, 26, 4, 629-640 (2006) · Zbl 1106.65056 · doi:10.1093/imanum/drl016 |
| [21] | Zhang, L.; Zhou, W.; Li, D., Some descent three-term conjugate gradient methods and their global convergence, Optimization Methods and Software, 22, 4, 697-711 (2007) · Zbl 1220.90094 · doi:10.1080/10556780701223293 |
| [22] | Cheng, W., A two-term PRP-based descent method, Numerical Functional Analysis and Optimization, 28, 11-12, 1217-1230 (2007) · Zbl 1138.90028 · doi:10.1080/01630560701749524 |
| [23] | Zhang, J.; Xiao, Y.; Wei, Z., Nonlinear conjugate gradient methods with sufficient descent condition for large-scale unconstrained optimization, Mathematical Problems in Engineering (2009) · Zbl 1184.65066 · doi:10.1155/2009/243290 |
| [24] | Al-Bayati, A. Y.; Sharif, W. H., A new three-term conjugate gradient method for unconstrained optimization, Canadian Journal on Science & Engineering Mathematics, 1, 5, 108-124 (2010) |
| [25] | Narushima, Y.; Yabe, H.; Ford, J. A., A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM Journal on Optimization, 21, 1, 212-230 (2011) · Zbl 1250.90087 · doi:10.1137/080743573 |
| [26] | Andrei, N., A modified Polak-Ribière-Polyak conjugate gradient algorithm for unconstrained optimization, Optimization. A Journal of Mathematical Programming and Operations Research, 60, 12, 1457-1471 (2011) · Zbl 1233.90255 · doi:10.1080/02331931003653187 |
| [27] | Andrei, N., On three-term conjugate gradient algorithms for unconstrained optimization, Applied Mathematics and Computation, 219, 11, 6316-6327 (2013) · Zbl 1274.90372 · doi:10.1016/j.amc.2012.11.097 |
| [28] | Andrei, N., A simple three-term conjugate gradient algorithm for unconstrained optimization, Journal of Computational and Applied Mathematics, 241, 19-29 (2013) · Zbl 1258.65056 · doi:10.1016/j.cam.2012.10.002 |
| [29] | Sugiki, K.; Narushima, Y.; Yabe, H., Globally convergent three-term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization, Journal of Optimization Theory and Applications, 153, 3, 733-757 (2012) · Zbl 1262.90170 · doi:10.1007/s10957-011-9960-x |
| [30] | Al-Baali, M.; Narushima, Y.; Yabe, H., A family of three-term conjugate gradient methods with sufficient descent property for unconstrained optimization, Computational Optimization and Applications. An International Journal, 60, 1, 89-110 (2015) · Zbl 1315.90051 · doi:10.1007/s10589-014-9662-z |
| [31] | Babaie-Kafaki, S.; Ghanbari, R., Two modified three-term conjugate gradient methods with sufficient descent property, Optimization Letters, 8, 8, 2285-2297 (2014) · Zbl 1309.90097 · doi:10.1007/s11590-014-0736-8 |
| [32] | Sun, M.; Liu, J., Three modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property, Journal of Inequalities and Applications, 2015, 1 (2015) · Zbl 1310.90108 · doi:10.1186/s13660-015-0649-9 |
| [33] | Powell, M. J., Restart procedures for the conjugate gradient method, Mathematical Programming, 12, 2, 241-254 (1977) · Zbl 0396.90072 · doi:10.1007/BF01593790 |
| [34] | Gilbert, J. C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM Journal on Optimization, 2, 1, 21-42 (1992) · Zbl 0767.90082 · doi:10.1137/0802003 |
| [35] | Wei, Z.; Li, G.; Qi, L., New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems, Applied Mathematics and Computation, 179, 2, 407-430 (2006) · Zbl 1106.65055 · doi:10.1016/j.amc.2005.11.150 |
| [36] | Powell, M. J. D., Nonconvex minimization calculations and the conjugate gradient method, Numerical Analysis. Numerical Analysis, Lecture Notes in Mathematics, 1066, 122-141 (1984), Berlin, Germany: Springer, Berlin, Germany · Zbl 0531.65035 · doi:10.1007/BFb0099521 |
| [37] | Dai, Z.-f.; Tian, B.-S., Global convergence of some modified PRP nonlinear conjugate gradient methods, Optimization Letters, 5, 4, 615-630 (2011) · Zbl 1228.90153 · doi:10.1007/s11590-010-0224-8 |
| [38] | Andrei, N., An unconstrained optimization test functions collection, Advanced Modeling and Optimization, 10, 1, 147-161 (2008) · Zbl 1161.90486 |
| [39] | Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Transactions on Mathematical Software, 7, 1, 17-41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936 |
| [40] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming. A Publication of the Mathematical Programming Society, 91, 2, Ser. A, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263 |
| [41] | Hager, W. W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization. An International Journal, 2, 1, 35-58 (2006) · Zbl 1117.90048 |
| [42] | Dai, Z.; Wen, F., Another improved Wei-Yao-Liu nonlinear conjugate gradient method with sufficient descent property, Applied Mathematics and Computation, 218, 14, 7421-7430 (2012) · Zbl 1254.65074 · doi:10.1016/j.amc.2011.12.091 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
