×

A scaled BFGS preconditioned conjugate gradient algorithm for unconstrained optimization. (English) Zbl 1116.90114

Summary: This letter presents a scaled memoryless BFGS preconditioned conjugate gradient algorithm for solving unconstrained optimization problems. The basic idea is to combine the scaled memoryless BFGS method and the preconditioning technique in the frame of the conjugate gradient method. The preconditioner, which is also a scaled memoryless BFGS matrix, is reset when the Powell restart criterion holds. The parameter scaling the gradient is selected as the spectral gradient. Computational results for a set consisting of 750 test unconstrained optimization problems show that this new scaled conjugate gradient algorithm substantially outperforms known conjugate gradient methods such as the spectral conjugate gradient SCG of E. Birgin and J. M. Martínez [Appl. Math. Optim. 43, No. 2, 117–128 (2001; Zbl 0990.90134)] and the (classical) conjugate gradient of E. Polak and G. Ribière [Rev. Franç. Inform. Rech. Opér. 3, No. 16, 35–43 (1969; Zbl 0174.48001)], but subject to the CPU time metric it is outperformed by L-BFGS [D. C. Liu and J. Nocedal, Math. Program., Ser. B 45, No. 3, 503–528 (1989; Zbl 0696.90048)]; J. Nocedal, http://www.ece.northwestern.edu/ nocedal/lbfgs.html].

MSC:

90C52 Methods of reduced gradient type
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods

Software:

L-BFGS; CUTEr; CUTE; SCALCG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birgin, E.; Martínez, J. M., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117-128 (2001) · Zbl 0990.90134
[2] Bongartz, I.; Conn, A. R.; Gould, N. I.M.; Toint, P. L., CUTE: Constrained and unconstrained testing environments, ACM Trans. Math. Software, 21, 123-160 (1995) · Zbl 0886.65058
[3] Dai, Y. H.; Liao, L. Z., New conjugate conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim., 43, 87-101 (2001) · Zbl 0973.65050
[4] Fletcher, R.; Reeves, C. M., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964) · Zbl 0132.11701
[5] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stan. Sec. B, 48, 409-436 (1952) · Zbl 0048.09901
[6] Liu, D.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Program. B, 45, 503-528 (1989) · Zbl 0696.90048
[7] Nocedal, J.
[8] J.M. Perry, A class of conjugate gradient algorithms with a two step variable metric memory, Discussion paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1977; J.M. Perry, A class of conjugate gradient algorithms with a two step variable metric memory, Discussion paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University, 1977
[9] Polak, E.; Ribière, G., Note sur la convergence de méthodes de directions conjuguées, Revue Francaise Informat. Reserche Opérationnelle, 3e Année, 16, 35-43 (1969) · Zbl 0174.48001
[10] Powell, M. J.D., Restart procedures for the conjugate gradient method, Math. Program., 12, 241-254 (1977) · Zbl 0396.90072
[11] Shanno, D. F., Conjugate gradient methods with inexact searches, Math. Oper. Res., 3, 244-256 (1978) · Zbl 0399.90077
[12] Shanno, D. F., On the convergence of a new conjugate gradient algorithm, SIAM J. Numer. Anal., 15, 1247-1257 (1978) · Zbl 0408.90071
[13] Wolfe, P., Convergence conditions for ascent methods, SIAM Rev., 11, 226-235 (1969) · Zbl 0177.20603
[14] Wolfe, P., Convergence conditions for ascent methods II: Some corrections, SIAM Rev., 13, 185-188 (1971) · Zbl 0216.26901
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.