×

New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems. (English) Zbl 1106.65055

Some new nonlinear conjugate gradient (CG) formulas for computing the search directions for unconstrained optimization problems are proposed. The significant differences of this approach from the classical studies on CG methods are that: 1) some proposed formulas possess the sufficient descent property without any line searches, and 2) the global convergence results for some of these given formulas with the standard Armijo line search are also given.
The new formulas turn out to be the conjugate descent formula if exact line searches are made. General convergence results for the proposed formulas with the weak Wolfe-Powell conditions are studied. It is proved that some of the formulas with the steplength technique which ensures the Zoutendijk condition to be held are globally convergent. Preliminary numerical results show that the proposed methods are very promising.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming

Software:

minpack
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Armijo, L., Minimization of functions having Lipschitz conditions partial derivatives, Pacific J. math., 16, 1-3, (1966) · Zbl 0202.46105
[2] Al-Baali, A., Descent property and global convergence of the fletcher – reeves method with inexact line search, IMA J. numer. anal., 5, 121-124, (1985) · Zbl 0578.65063
[3] Chen, X.; Sun, J., Global convergence of a two-parameter family of conjugate gradient methods without line search, J. comput. appl. math., 146, 1, 37-45, (2002) · Zbl 1018.65081
[4] Dai, Y., Convergence of nonlinear conjugate methods, J. comput. math., 19, 539-549, (2001)
[5] Y. Dai, Convergence of Polak-Ribière-Polyak conjugate gradient method with constant stepsizes, Manuscript, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 2001.
[6] Dai, Y.; Han, J.; Liu, G.; Sun, D.; Yin, H.; Yan, Y., Convergence properties of nonlinear conjugate methods, SIAM J. optimizat., 2, 345-358, (1999) · Zbl 0957.65062
[7] Dai, Y.; Ni, Q., Testing different conjugate gradient methods for large-scale unconstrained optimization, J. comput. math., 21, 3, 311-320, (2003) · Zbl 1041.65048
[8] Dai, Y.; Yuan, Y., Convergence properties of the conjugate descent method, Adv. math., 6, 552-562, (1996) · Zbl 0871.49028
[9] Dai, Y.; Yuan, Y., A nonlinear conjugate gradient with a strong global convergence properties, SIAM J. optimizat., 10, 177-182, (2000)
[10] Dai, Y.; Yuan, Y., An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. oper. res., 103, 33-47, (2001) · Zbl 1007.90065
[11] Y. Dai, Y. Yuan, Further studies on the Polak-Ribière-Polyak method, Research Report ICM-95-040, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1995.
[12] Dai, Y.; Yuan, Y., Nonlinear conjugate gradient methods, (2000), Science Press of Shanghai Shanghai · Zbl 1030.90141
[13] Fletcher, R., Practical method of optimization, vol. I: unconstrained optimization, (1997), Wiley New York
[14] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149-154, (1964) · Zbl 0132.11701
[15] Gibert, J.C.; Nocedal, J., Global convergence properties of conjugate gradient methods for optimization, SIAM J. optimizat., 2, 21-42, (1992) · Zbl 0767.90082
[16] Griewank, A., On automatic differentiation, (), 84-108
[17] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for newton’s methods, SIAM J. numer. anal., 23, 707-716, (1986) · Zbl 0616.65067
[18] Grippo, L.; Lucidi, S., A globally convergent version of the polak – ribière gradient method, Math. programm., 78, 375-391, (1997) · Zbl 0887.90157
[19] Han, J.; Liu, G.; Sun, D.; Yin, H., Two fundamental convergence theorems for nonlinear conjugate gradient methods and their applications, Acta math. appl. sinica, 1, 38-46, (2001) · Zbl 0973.65048
[20] Hestenes, M.R.; Stiefel, E., Method of conjugate gradient for solving linear equations, J. res. nat. bur. stand., 49, 409-436, (1952) · Zbl 0048.09901
[21] Liu, G.; Han, J., On the global convergence of conjugate gradient methods with inexact line search, Numer. math. (A journal of Chinese university), 2, 147-153, (1995) · Zbl 0845.65024
[22] Liu, G.; Han, J.; Yin, H., Global convergence of the fletcher – reeves algorithm with inexact line search, Appl. math. JCU, 10B, 75-82, (1995) · Zbl 0834.90122
[23] Liu, Y.; Storey, C., Efficient generalized conjugate gradient algorithms, part 1: theory, J. optimizat. theor. appl., 69, 129-137, (1992) · Zbl 0702.90077
[24] McCormick, G., A modification of armijo’s step-size rule for negative curvature, Mathematical programming, 13, 111-115, (1977) · Zbl 0367.90100
[25] Morè, J.J.; Garbow, B.S.; Hillstrome, K.E., Testing unconstrained optimization software, ACM trans. math. software, 7, 17-41, (1981) · Zbl 0454.65049
[26] Nocedal, J., Theory of algorithms for unconstrained optimization, (), 199-242 · Zbl 0766.65051
[27] Nocedal, J., Conjugate gradient methods and nonlinear optimization, (), 9-23 · Zbl 0866.65037
[28] Polak, E., Optimization: algorithms and consistent approximations, (1997), Springer-Verlag New York · Zbl 0899.90148
[29] Polak, E.; Ribière, G., Note sur la convergence de directions conjugèes, Rev. francaise informat recherche operationelle 3e annèe, 16, 35-43, (1969) · Zbl 0174.48001
[30] Polyak, B.T., The conjugate gradient method in extreme problems, USSR comput. math. math. phys., 9, 94-112, (1969) · Zbl 0229.49023
[31] Powell, M.J.D., Convergence properties of algorithms for nonlinear optimization, SIAM rev., 28, 487-500, (1986) · Zbl 0624.90091
[32] Powell, M.J.D., Nonconvex minimization calculations and the conjugate gradient method, Lecture notes in mathematics, vol. 1066, (1984), Springer-Verlag Berlin, pp. 122-141 · Zbl 0531.65035
[33] Qi, H.; Han, J.; Liu, G., A modification of hestenes – stiefel conjugate gradient method, Chinese ann. math., 3, 177-184, (1996)
[34] Sun, J.; Zhang, J., Convergence of conjugate gradient methods without line search, Ann. oper. res., 103, 161-173, (2001) · Zbl 1014.90071
[35] Z. Wei, G. Li, L. Qi, Global convergence of the Polak-Ribière-Polyak conjugate gradient method with inexact line searches for nonconvex unconstrained optimization problems, Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong, May 2002.
[36] Z. Wei, L. Qi, X. Chen, An SQP-type method and its application in stochastic programming, J. Optimizat. Theor. Appl. 116 (2003). · Zbl 1030.90142
[37] Z. Wei, L. Qi, S. Ito, New step-size rules for optimization problems, Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, PR China, October 2000.
[38] Wolfe, P., Convergence conditions for ascent methods, SIAM rev., 11, 226-235, (1969) · Zbl 0177.20603
[39] Wolfe, P., Convergence conditions for ascent methods II: some corrections, SIAM rev., 11, 185-188, (1971) · Zbl 0216.26901
[40] Yuan, Y.; Sun, W., Theory and methods of optimization, (1999), Science Press of China Beijing
[41] Zoutendijk, G., Nonlinear programming computational methods, (), 37-86 · Zbl 0336.90057
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.