A modified HZ conjugate gradient algorithm without gradient Lipschitz continuous condition for non convex functions. (English) Zbl 1502.65035
Summary: As we know, conjugate gradient methods are widely used for unconstrained optimization because of the advantages of simple structure and small storage. For non-convex functions, the global convergence analysis of these methods are also crucial. But almost all of them require the gradient Lipschitz continuous condition. Based on the work of W. W. Hager and H. Zhang [SIAM J. Optim. 16, No. 1, 170–192 (2005; Zbl 1093.90085)], Algorithm 1 and Algorithm 2 are proposed and analyzed for the optimization problems. The proposed algorithms possess the sufficient descent property and the trust region feature independent of line search technique. The global convergence of Algorithm 1 is obtained without the gradient Lipschitz continuous condition under the weak Wolfe-Powell inexact line search. Based on Algorithm 1, Algorithm 2 is further improved which global convergence can be obtained independently of line search technique. Numerical experiments are done for Muskingum model and image restoration problems.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 90C52 | Methods of reduced gradient type |
Keywords:
non-convex functions; sufficient descent; trust region; inexact line search; global convergenceCitations:
Zbl 1093.90085References:
| [1] | Andrei, N., Scaled conjugate gradient algorithms for unconstrained optimization, Comput. Optim. Appl., 38, 401-416 (2007) · Zbl 1168.90608 · doi:10.1007/s10589-007-9055-7 |
| [2] | Birgin, E., Martnez, J. M.: A spectral conjugate gradient method for unconstrained optimization. Appl. Math. Optim., 43(2001), pp. 117-128 · Zbl 0990.90134 |
| [3] | Dai, Y.: Analysis of conjugate gradient methods, Ph.D. Thesis, Institute of Computational Mathe- matics and Scientific/Engineering Computing, Chese Academy of Sciences, 1997 |
| [4] | Dai, Y., Convergence properties of the BFGS algoritm, SIAM J. Optim., 13, 693-701 (2003) · Zbl 1036.65052 · doi:10.1137/S1052623401383455 |
| [5] | Dai, Y.; Yuan, Y., A nonlinear conjugate gradient with a strong global convergence properties, SIAM J. Optim., 10, 177-182 (2000) · Zbl 0957.65061 · doi:10.1137/S1052623497318992 |
| [6] | Dai, Y., Yuan, Y.: Nonlinear conjugate gradient Methods, Shanghai Scientific and Technical Publishers, 1998 |
| [7] | Fletcher, R.: Practical Methods of Optimization, 2nd edn. John Wiley and Sons, New York (1987) · Zbl 0905.65002 |
| [8] | Fletcher, R.; Reeves, CM, Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 |
| [9] | Fan, J., Yuan, Y.: A new trust region algorithm with trust region radius converging to zero, D. Li ed. Proceedings of the 5th International Conference on Optimization: Techniques and Applications (December 2001, Hongkong), (2001), pp. 786-794 |
| [10] | Geem, ZW, Parameter estimation for the nonlinear Muskingum model using the BFGS technique, J. Hydrol. Eng., 132, 21-43 (2006) |
| [11] | Grippo, L.; Lucidi, S., A globally convergent version of the Polak-Ribière-Polyak conjugate gradient method, Math. Program., 78, 375-391 (1997) · Zbl 0887.90157 · doi:10.1007/BF02614362 |
| [12] | Gilbert, JC; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim., 2, 21-42 (1992) · Zbl 0767.90082 · doi:10.1137/0802003 |
| [13] | Hestenes, MR; Stiefel, E., Method of conjugate gradient for solving linear equations, J. Res. Nation. Bur. Stand., 49, 409-436 (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044 |
| [14] | Hager, W.; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085 · doi:10.1137/030601880 |
| [15] | Hager, W.; Zhang, H., Algorithm 851: A conjugate gradient method with guaranteed descent, ACM Trans. Math. Soft., 32, 113-137 (2006) · Zbl 1346.90816 · doi:10.1145/1132973.1132979 |
| [16] | Levenberg, K., A method for the solution of certain nonlinear problem in least squares, Quart. Appl. Math., 2, 164-168 (1944) · Zbl 0063.03501 · doi:10.1090/qam/10666 |
| [17] | Li, Q.; Li, D., A class of derivative-free methods for large-scale nonlinear monotone equations, IMA Journal of Numerical Analysis, 31, 1625-1635 (2011) · Zbl 1241.65047 · doi:10.1093/imanum/drq015 |
| [18] | Liu, Y.; Storey, C., Effcient generalized conjugate gradient algorithms part 1: Theory, J. Optim. Theo. Appl., 69, 129-137 (1991) · Zbl 0702.90077 · doi:10.1007/BF00940464 |
| [19] | Li, X., Wang, S., Jin, Z., Pham, H.: A conjugate gradient algorithm under Yuan-Wei-Lu line search technique for large-scale minimization optimization models, Math. Probl. Eng., Volume 2018, pp. 1-11 · Zbl 1427.90294 |
| [20] | Martinet, B., Régularisation d’inéquations variationelles par approxiamations succcessives, Rev. Fr. Inform. Rech. Oper, 4, 154-158 (1970) · Zbl 0215.21103 |
| [21] | Ouyang, A.; Liu, L.; Sheng, Z., A class of parameter estimation methods for nonlinear Muskingum model using hybrid invasive weed optimization algorithm, Math. Probl. Eng., 2015, 1-15 (2015) · Zbl 1394.90575 |
| [22] | Ouyang, A.; Tang, Z.; Li, K., Estimating parameters of Muskingum model using an adaptive hybrid PSO algorithm, Int. J. Pattern. Recogn., 28, 1-29 (2014) · doi:10.1142/S0218001414590034 |
| [23] | Polak, E., The conjugate gradient method in extreme problems, Comput. Math. Mathem. Phy., 9, 94-112 (1969) · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4 |
| [24] | Powell, M. J. D.: Convergence properties of a class of minimization algorithms, Mangasarian, Q.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming, Academic Press, New York, 2(1974), pp. 1-27 · Zbl 0321.90045 |
| [25] | Powell, MJD, Convergence properties of algorithm for nonlinear optimization, SIAM Rev., 28, 487-500 (1986) · Zbl 0624.90091 · doi:10.1137/1028154 |
| [26] | Powell, M.J.D.: Nonconvex minimization calculations and the conjugate gradient method. Lecture Notes in Mathematics, vol. 1066. Spinger-Verlag, Berlin (1984) · Zbl 0531.65035 |
| [27] | Polak, E.; Ribière, G., Note sur la convergence de directions conjugees, Rev. Fran. Inf. Rech. Opérat., 3, 35-43 (1969) · Zbl 0174.48001 |
| [28] | Sheng, Z., Ouyang, A., Liu, L.: et.al., A novel parameter estimation method for Muskingum model using new Newton-type trust region algorithm, Math. Probl. Eng., (2014), Art. ID 634852, pp. 1-7 · Zbl 1407.86023 |
| [29] | Sheng, Z.; Yuan, G., An effective adaptive trust region algorithm for nonsmooth minimization, Comput. Optim. Appl., 71, 251-271 (2018) · Zbl 1406.90099 · doi:10.1007/s10589-018-9999-9 |
| [30] | Sheng, Z.; Yuan, G.; Cui, Z., A new adaptive trust region algorithm for optimization problems, Acta Math. Scientia, 38B, 2, 479-496 (2018) · Zbl 1399.65135 · doi:10.1016/S0252-9602(18)30762-8 |
| [31] | Sheng, Z.; Yuan, G.; Cui, Z., An adaptive trust region algorithm for large-residual nonsmooth least squares problems, J. Ind. Manage. Optim., 14, 707-718 (2018) · Zbl 1412.90125 · doi:10.3934/jimo.2017070 |
| [32] | Wei, Z.; Yao, S.; Liu, L., The convergence properties of some new conjugate gradient methods, Appl. Math. Comput., 183, 1341-1350 (2006) · Zbl 1116.65073 |
| [33] | Yuan, G., Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optim. Let., 3, 11-21 (2009) · Zbl 1154.90623 · doi:10.1007/s11590-008-0086-5 |
| [34] | Yuan, Y., Analysis on the conjugate gradient method, Optim. Meth. Soft., 2, 19-29 (1993) · doi:10.1080/10556789308805532 |
| [35] | Yuan, G.; Lu, X., A modified PRP conjugate gradient method, Anna. Operat. Res., 166, 73-90 (2009) · Zbl 1163.90798 · doi:10.1007/s10479-008-0420-4 |
| [36] | Yuan, G.; Lu, S.; Wei, Z., A new trust-region method with line search for solving symmetric nonlinear equations, Intern, J. Comput. Math., 88, 2109-2123 (2011) · Zbl 1254.90181 |
| [37] | Yuan, G.; Lu, X.; Wei, Z., A conjugate gradient method with descent direction for unconstrained optimization, J. Comput. Appl. Math., 233, 519-530 (2009) · Zbl 1179.65075 · doi:10.1016/j.cam.2009.08.001 |
| [38] | Yuan, G.; Lu, X.; Wei, Z., BFGS trust-region method for symmetric nonlinear equations, J. Compu. Appl. Math., 230, 44-58 (2009) · Zbl 1168.65026 · doi:10.1016/j.cam.2008.10.062 |
| [39] | Yuan, G.; Meng, Z.; Li, Y., A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, J. Optim. Theory. Appl., 168, 129-152 (2016) · Zbl 1332.65081 · doi:10.1007/s10957-015-0781-1 |
| [40] | Yuan, G.; Wei, Z.; Li, G., A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs, J. Comput. Appl. Math., 255, 86-96 (2014) · Zbl 1291.90315 · doi:10.1016/j.cam.2013.04.032 |
| [41] | Yuan, G.; Wei, Z.; Lu, X., Global convergence of the BFGS method and the PRP method for general functions under a modified weak Wolfe-Powell line search, Appl. Math. Model., 47, 811-825 (2017) · Zbl 1446.65031 · doi:10.1016/j.apm.2017.02.008 |
| [42] | Yuan, G.; Wang, X.; Sheng, Z., The projection technique for two open problems of unconstrained optimization problems, Journal of Optimization Theory and Applications, 186, 590-619 (2020) · Zbl 1450.90037 · doi:10.1007/s10957-020-01710-0 |
| [43] | Yuan, G.; Wei, Z.; Yang, Y., The global convergence of the Polak-Ribière-Polyak conjugate gradient algorithm under inexact line search for nonconvex functions, J. Comput. Appl. Math., 362, 262-275 (2019) · Zbl 1418.90205 · doi:10.1016/j.cam.2018.10.057 |
| [44] | Yuan, G.; Zhang, M., A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations, J. Comput. Appl. Math., 286, 186-195 (2015) · Zbl 1316.90038 · doi:10.1016/j.cam.2015.03.014 |
| [45] | Zoutendijk, G.: Nonlinear programming computational methods. In: Abadie, J. (ed.) Integer and Nonlinear programming, pp. 37-86. Northholland, Amsterdam (1970) · Zbl 0336.90057 |
| [46] | Zhang, L.; Zhou, W.; Li, D., A descent modified Polak-Ribière-Polyak conjugate method and its global convergence, IMA Journal on Numerical Analysis, 26, 629-649 (2006) · Zbl 1106.65056 · doi:10.1093/imanum/drl016 |
| [47] | Zhang, L.; Zhou, W.; Li, D., Global convergence of a modified Fletcher-Reèves conjugate gradient method with Armijo-type line search, Numer. Math., 104, 561-572 (2006) · Zbl 1103.65074 · doi:10.1007/s00211-006-0028-z |
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.
