×
Wei, Zengxin; Li, Guoyin; Qi, Liqun

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

Appl. Math. Comput. 179, No. 2, 407-430 (2006).
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.
Reviewer: Nada Djuranović-Miličić (Belgrade)

Cited in 35 Documents

MSC:

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

Keywords:

unconstrained optimization; large scale problem; Wolfe-Powell conditions; Armijo line search; global convergence; nonlinear conjugate gradient formulas; numerical results

Software:

minpack
PDF BibTeX XML Cite
\textit{Z. Wei} et al., Appl. Math. Comput. 179, No. 2, 407--430 (2006; Zbl 1106.65055)
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)
[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
[12] Dai, Y.; Yuan, Y., Nonlinear Conjugate Gradient Methods (2000), Science Press of Shanghai: Science Press of Shanghai Shanghai · Zbl 1030.90141
[13] Fletcher, R., Practical Method of Optimization, Vol. I: Unconstrained Optimization (1997), Wiley: 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, (Iri, M.; Tanabe, K., Mathematical Programming: Recent Developments and Applications (1989), Kluwer Academic Publishers), 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, (Acta Numerica (1992), Cambridge University Press: Cambridge University Press Cambridge), 199-242 · Zbl 0766.65051
[27] Nocedal, J., Conjugate gradient methods and nonlinear optimization, (Adams, L.; Nazareth, J. L., Linear and Nonlinear Conjugate Gradient Related Methods (1995), SIAM: SIAM Philadelphia), 9-23 · Zbl 0866.65037
[28] Polak, E., Optimization: Algorithms and Consistent Approximations (1997), Springer-Verlag: 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: 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
[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: Science Press of China Beijing
[41] Zoutendijk, G., Nonlinear programming computational methods, (Abadie, J., Integer and Nonlinear Programming (1970), North-Holland: North-Holland Amsterdam), 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.