Abstract
In this paper, a new nonlinear conjugate gradient method is proposed, whose search direction can be viewed as a simple approximation to that of the memoryless BFGS method. The search direction of the proposed method satisfies the sufficient descent property regardless of line search. Global convergence properties of the new method are explored on uniformly convex functions and general functions with the standard Wolfe line search. Numerical experiments are done to test the efficiency of the new method, which implies the new method is promising.
Similar content being viewed by others
References
Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, Ph.L.: CUTE: Constrained and unconstrained testing environment. ACM Trans. Math. Softw. 20, 123–160 (1995)
Andrei, N.: Scaled conjugate gradient algorithms for unconstrained optimization. Comput. Optim. Appl. 38, 401–416 (2007)
Andrei, N.: An unconstrained optimization test functions collection. Adv. Model. Optim. 10, 147–161 (2008)
Cheng, W.Y., Liu, Q.F.: Sufficient descent nonlinear conjugate gradient methods with conjugacy condition. Numer. Algorithm 53, 113–131 (2010)
Dai, Y.H.: Nonlinear Gradient Methods, Wiley Encylopedia of Operations Research and Management Science, Published online Feb. 2011, doi:10.1002/9780470400531.eorms0183/pdf
Dai, Y.H., Kou, C.X.: A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM J. Optim. 23, 296–320 (2013)
Dai, Y.H., Liao, L.Z.: New conjugacy conditions and related conjugate gradient methods. Appl. Math. Optim. 43, 87–101 (2001)
Dai, Y.H., Ni, Q.: Testing different conjugate gradient methods for large-scale unconstrained optimization. J. Comput. Math. 21, 311–320 (2003)
Dai, Y.H., Yuan, Y.X.: A nonlinear conjugate gradient method with a strong global convergence property. SIAM. J. Optim. 10, 177–182 (1999)
Dai, Y.H., Yuan, Y.X.: Nonlinear Conjugate Gradient Methods. Shang Hai Science and Technolgy Press, Shanghai (2001) (in Chinese)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance files. Math. Program. 91, 201–213 (2002)
Fletcher, R., Reeves, C.M.: Function minimization by conjugate gradient methods. Comput. J. 7, 149–154 (1964)
Gilbert, J.C., Nocedal, J.: Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2, 21–42 (1992)
Hager, W.W., Zhang, H.C.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16, 170–192 (2005)
Hager, W.W., Zhang, H.C.: A survey of nonlinear gradient methods. Pacific J. Optim. 2, 35–58 (2006)
Hestenes, M.R., Stiefel, E.: Method of conjugate gradient for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409–436 (1952)
Kobayashi, M., Narushima, Y., Yabe, H.: Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems. J. Comput. Appl. Math. 234, 375–397 (2010)
Li, D.H., Fukushima, M.: A modified BFGS method and its global convergence in nonconvex minimization. J. Comput. Appl. Math. 129, 15–35 (2001)
Li, G.Y., Tang, C.M., Wei, Z.X.: New conjugacy conditon and related new conjugate gradient methods for unconstrained optimization. J. Comput. Appl. Math. 202, 523–539 (2007)
Necodal, J., Wright, S.J.: Numerical Optimization, Springer Series in Operations Research. Springer, New York (1999)
Nocedal, J.: Updating quasi-Newton matrixes with limited storage. Math. Comput. 35, 773–782 (1980)
Narushima, Y., Yabe, H.: Conjugate gradient methods on secant conditions that generate descent search directions for unconstrained optimization. J. Comput. Appl. Math. 236, 4303–4317 (2012)
Oren, S.S., Luenberger, D.G.: Self-scaling variable metric (SSVM) algorithms, part I: criteria and sufficient conditions for scaling a class of algorithms. Manage. Sci. 20, 845–862 (1974)
Oren, S.S., Luenberger, D.G.: Self-scaling variable metric (SSVM) algorithms, part II: implementation and experiments. Manage. Sci. 20, 863–874 (1974)
Perry, J.M.: A class of conjugate gradient with a two-step variable-metric memory, Discussion Paper 269, Center for Mathematical studies in Economics and Management Sciences, Northwestern University, Evanston (1977)
Perry, J.M.: A modified conjugate gradient algorithm. Oper. Res. 26, 1073–1078 (1978)
Polak, E., Ribière, G.: Note sur la convergence de méthods de directions conjugées. Rev. Franccaise Inform. Rech. Opiérationnelle 16, 35–43 (1969)
Polyak, B.T.: The conjugate gradient method in extremem problems. USSR Comput. Math. Math. Phys. 9, 94–112 (1969)
Shanno, D.F.: Conjugate gradient methods with inexact line searches. Math. Oper. Res. 3, 244–256 (1978)
Wei, Z.X., Li, G.Y., Qi, L.Q.: New quasi-Newton methods for unconstrained optimization problems. Appl. Math. Comput. 175, 1156–1188 (2006)
Yabe, H., Takano, M.: Globla convergence properties of nonlinear conjugate gradient methods with modified secant equation. Comput. Optim. Appl. 28, 203–225 (2004)
Yu, G.H., Guan, L.T., Chen, W.F.: Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization. Optim. Methods Softw. 23, 561–572 (2006)
Zhang, J.Z., Xu, C.X.: Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations. J. Comput. Appl. Math. 137, 269–278 (2001)
Zhou, W.J., Zhang, L.: A nonlinear conjugate gradient method based on the MBFGS secant equation. Optim. Meth. Softw. 21, 707–714 (2006)
Zhang, L., Zhou, W.J., Li, D.H.: A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA J. Numer. Anal. 26, 629–640 (2006)
Zhang, L., Zhou, W.J., Li, D.H.: Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search. Numer. Math. 104, 561–572 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Liu, H., Wang, H., Qian, X. et al. A conjugate gradient method with sufficient descent property. Numer Algor 70, 269–286 (2015). https://doi.org/10.1007/s11075-014-9946-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-014-9946-5