Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization

Previous Article
Generalized weak sharp minima of variational inequality problems with functional constraints
JIMO Home
This Issue
Next Article
On the robust control design for a class of nonlinearly affine control systems: The attractive ellipsoid approach

July 2013, 9(3): 595-619. doi: 10.3934/jimo.2013.9.595

Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization

Wataru Nakamura ^1, , Yasushi Narushima ^2, and Hiroshi Yabe ^3,

1.	Central Japan Railway Company, JR Central Towers, 1-1-4, Meieki, Nakamura-ku, Nagoya, Aichi 450-6101, Japan
2.	Department of Management System Science, Yokohama National University, 79-4 Tokiwadai, Hodogaya-ku, Yokohama 240-8501, Japan
3.	Department of Mathematical Information Science, Tokyo University of Science, 1-3, Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan

Received June 2012 Revised March 2013 Published April 2013

Abstract
Related Papers

It is very important to generate a descent search direction independent of line searches in showing the global convergence of conjugate gradient methods. The method of Hager and Zhang (2005) satisfies the sufficient descent condition. In this paper, we treat two subjects. We first consider a unified formula of parameters which establishes the sufficient descent condition and follows the modification technique of Hager and Zhang. In order to show the global convergence of the conjugate gradient method with the unified formula of parameters, we define some property (say Property A). We prove the global convergence of the method with Property A. Next, we apply the unified formula to a scaled conjugate gradient method and show its global convergence property. Finally numerical results are given.

Keywords: scaled conjugate gradient method, Nonlinear conjugate gradient method, sufficient descent property, global convergence., unconstrained optimization.

Mathematics Subject Classification: Primary: 90C30, 90C06; Secondary: 65K0.

Citation: Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595

References:

[1]	N. Andrei, A Dai-Yuan conjugate gradient algorithm with sufficient descent and conjugacy conditions for unconstrained optimization, Applied Mathematics Letters, 21 (2008), 165-171. doi: 10.1016/j.aml.2007.05.002.
[2]	N. Andrei, New accelerated conjugate gradient algorithms as a modification of Dai-Yuan's computational scheme for unconstrained optimization, Journal of Computational and Applied Mathematics, 234 (2010), 3397-3410. doi: 10.1016/j.cam.2010.05.002.
[3]	I. Bongartz, A. R. Conn, N. I. M. Gould and P. L. Toint, CUTE: Constrained and unconstrained testing environments, ACM Transactions on Mathematical Software, 21 (1995), 123-160. doi: 10.1145/200979.201043.
[4]	X. Chen and J. Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search, Journal of Computational and Applied Mathematics, 146 (2002), 37-45. doi: 10.1016/S0377-0427(02)00416-8.
[5]	W. Cheng, A two-term PRP-based descent method, Numerical Functional Analysis and Optimization, 28 (2007), 1217-1230. doi: 10.1080/01630560701749524.
[6]	Y. H. Dai, Nonlinear conjugate gradient methods, in "Wiley Encyclopedia of Operations Research and Management Science" (eds. J. J. Cochran, L. A. Cox, Jr., P. Keskinocak, J. P. Kharoufeh and J. C. Smith), John Wiley $&$ Sons, (2011). doi: 10.1002/9780470400531.eorms0183.
[7]	Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods, Applied Mathematics and Optimization, 43 (2001), 87-101. doi: 10.1007/s002450010019.
[8]	Y. H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10 (1999), 177-182. doi: 10.1137/S1052623497318992.
[9]	Y. H. Dai and Y. Yuan, A three-parameter family of nonlinear conjugate gradient methods, Mathematics of Computation, 70 (2001), 1155-1167. doi: 10.1090/S0025-5718-00-01253-9.
[10]	Z. Dai and B. S. Tian, Global convergence of some modified PRP nonlinear conjugate gradient methods, Optimization Letters, 5 (2011), 615-630. doi: 10.1007/s11590-010-0224-8.
[11]	Z. Dai and F. Wen, A modified CG-DESCENT method for unconstrained optimization, Journal of Computational and Applied Mathematics, 235 (2011), 3332-3341. doi: 10.1016/j.cam.2011.01.046.
[12]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.
[13]	R. Fletcher, "Practical Methods of Optimization," $2^{nd}$ edition, John Wiley $&$ Sons, 1987.
[14]	R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal, 7 (1964), 149-154. doi: 10.1093/comjnl/7.2.149.
[15]	N. I. M. Gould, D. Orban and P. L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 373-394. doi: 10.1145/962437.962439.
[16]	W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16 (2005), 170-192. doi: 10.1137/030601880.
[17]	W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization, 2 (2006), 35-58.
[18]	W. W. Hager and H. Zhang, "CG_DESCENT Version 1.4, User's Guide," University of Florida, November 14, 2005, http://www.math.ufl.edu/~hager/papers/CG/.
[19]	M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49 (1952), 409-436. doi: 10.6028/jres.049.044.
[20]	M. Li and H. Feng, A sufficient descent LS conjugate gradient method for unconstrained optimization problems, Applied Mathematics and Computation, 218 (2011), 1577-1586. doi: 10.1016/j.amc.2011.06.034.
[21]	Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: Theory, Journal of Optimization Theory and Applications, 69 (1991), 129-137. doi: 10.1007/BF00940464.
[22]	Y. Narushima and H. Yabe, Conjugate gradient methods based on secant conditions that generate descent search directions for unconstrained optimization, Journal of Computational and Applied Mathematics, 236 (2012), 4303-4317. doi: 10.1016/j.cam.2012.01.036.
[23]	Y. Narushima, H. Yabe and J. A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM Journal on Optimization, 21 (2011), 212-230. doi: 10.1137/080743573.
[24]	J. Nocedal and S. J. Wright, "Numerical Optimization," $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, 2006.
[25]	K. Sugiki, Y. Narushima and H. Yabe, Globally convergent three-term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization, Journal of Optimization Theory and Applications, 153 (2012), 733-757. doi: 10.1007/s10957-011-9960-x.
[26]	W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer, 2006.
[27]	G. Yu, L. Guan and W. Chen, Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization, Optimization Methods and Software, 23 (2008), 275-293. doi: 10.1080/10556780701661344.
[28]	G. Yu, L. Guan and G. Li, Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property, Journal of Industrial and Management Optimization, 4 (2008), 565-579. doi: 10.3934/jimo.2008.4.565.
[29]	G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optimization Letters, 3 (2009), 11-21. doi: 10.1007/s11590-008-0086-5.
[30]	L. Zhang and J. Li, A new globalization technique for nonlinear conjugate gradient methods for nonconvex minimization, Applied Mathematics and Computation, 217 (2011), 10295-10304. doi: 10.1016/j.amc.2011.05.032.
[31]	L. Zhang, W. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik, 104 (2006), 561-572. doi: 10.1007/s00211-006-0028-z.

show all references

References:

[1]	N. Andrei, A Dai-Yuan conjugate gradient algorithm with sufficient descent and conjugacy conditions for unconstrained optimization, Applied Mathematics Letters, 21 (2008), 165-171. doi: 10.1016/j.aml.2007.05.002.
[2]	N. Andrei, New accelerated conjugate gradient algorithms as a modification of Dai-Yuan's computational scheme for unconstrained optimization, Journal of Computational and Applied Mathematics, 234 (2010), 3397-3410. doi: 10.1016/j.cam.2010.05.002.
[3]	I. Bongartz, A. R. Conn, N. I. M. Gould and P. L. Toint, CUTE: Constrained and unconstrained testing environments, ACM Transactions on Mathematical Software, 21 (1995), 123-160. doi: 10.1145/200979.201043.
[4]	X. Chen and J. Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search, Journal of Computational and Applied Mathematics, 146 (2002), 37-45. doi: 10.1016/S0377-0427(02)00416-8.
[5]	W. Cheng, A two-term PRP-based descent method, Numerical Functional Analysis and Optimization, 28 (2007), 1217-1230. doi: 10.1080/01630560701749524.
[6]	Y. H. Dai, Nonlinear conjugate gradient methods, in "Wiley Encyclopedia of Operations Research and Management Science" (eds. J. J. Cochran, L. A. Cox, Jr., P. Keskinocak, J. P. Kharoufeh and J. C. Smith), John Wiley $&$ Sons, (2011). doi: 10.1002/9780470400531.eorms0183.
[7]	Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods, Applied Mathematics and Optimization, 43 (2001), 87-101. doi: 10.1007/s002450010019.
[8]	Y. H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization, 10 (1999), 177-182. doi: 10.1137/S1052623497318992.
[9]	Y. H. Dai and Y. Yuan, A three-parameter family of nonlinear conjugate gradient methods, Mathematics of Computation, 70 (2001), 1155-1167. doi: 10.1090/S0025-5718-00-01253-9.
[10]	Z. Dai and B. S. Tian, Global convergence of some modified PRP nonlinear conjugate gradient methods, Optimization Letters, 5 (2011), 615-630. doi: 10.1007/s11590-010-0224-8.
[11]	Z. Dai and F. Wen, A modified CG-DESCENT method for unconstrained optimization, Journal of Computational and Applied Mathematics, 235 (2011), 3332-3341. doi: 10.1016/j.cam.2011.01.046.
[12]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Mathematical Programming, 91 (2002), 201-213. doi: 10.1007/s101070100263.
[13]	R. Fletcher, "Practical Methods of Optimization," $2^{nd}$ edition, John Wiley $&$ Sons, 1987.
[14]	R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal, 7 (1964), 149-154. doi: 10.1093/comjnl/7.2.149.
[15]	N. I. M. Gould, D. Orban and P. L. Toint, CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM Transactions on Mathematical Software, 29 (2003), 373-394. doi: 10.1145/962437.962439.
[16]	W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16 (2005), 170-192. doi: 10.1137/030601880.
[17]	W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pacific Journal of Optimization, 2 (2006), 35-58.
[18]	W. W. Hager and H. Zhang, "CG_DESCENT Version 1.4, User's Guide," University of Florida, November 14, 2005, http://www.math.ufl.edu/~hager/papers/CG/.
[19]	M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49 (1952), 409-436. doi: 10.6028/jres.049.044.
[20]	M. Li and H. Feng, A sufficient descent LS conjugate gradient method for unconstrained optimization problems, Applied Mathematics and Computation, 218 (2011), 1577-1586. doi: 10.1016/j.amc.2011.06.034.
[21]	Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: Theory, Journal of Optimization Theory and Applications, 69 (1991), 129-137. doi: 10.1007/BF00940464.
[22]	Y. Narushima and H. Yabe, Conjugate gradient methods based on secant conditions that generate descent search directions for unconstrained optimization, Journal of Computational and Applied Mathematics, 236 (2012), 4303-4317. doi: 10.1016/j.cam.2012.01.036.
[23]	Y. Narushima, H. Yabe and J. A. Ford, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM Journal on Optimization, 21 (2011), 212-230. doi: 10.1137/080743573.
[24]	J. Nocedal and S. J. Wright, "Numerical Optimization," $2^{nd}$ edition, Springer Series in Operations Research and Financial Engineering, Springer, 2006.
[25]	K. Sugiki, Y. Narushima and H. Yabe, Globally convergent three-term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization, Journal of Optimization Theory and Applications, 153 (2012), 733-757. doi: 10.1007/s10957-011-9960-x.
[26]	W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming," Springer, 2006.
[27]	G. Yu, L. Guan and W. Chen, Spectral conjugate gradient methods with sufficient descent property for large-scale unconstrained optimization, Optimization Methods and Software, 23 (2008), 275-293. doi: 10.1080/10556780701661344.
[28]	G. Yu, L. Guan and G. Li, Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property, Journal of Industrial and Management Optimization, 4 (2008), 565-579. doi: 10.3934/jimo.2008.4.565.
[29]	G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems, Optimization Letters, 3 (2009), 11-21. doi: 10.1007/s11590-008-0086-5.
[30]	L. Zhang and J. Li, A new globalization technique for nonlinear conjugate gradient methods for nonconvex minimization, Applied Mathematics and Computation, 217 (2011), 10295-10304. doi: 10.1016/j.amc.2011.05.032.
[31]	L. Zhang, W. Zhou and D. H. Li, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Numerische Mathematik, 104 (2006), 561-572. doi: 10.1007/s00211-006-0028-z.

[1]	Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[2]	Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565
[3]	C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[4]	Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[5]	El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[6]	Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[7]	Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
[8]	Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025
[9]	ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021150
[10]	Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739
[11]	Abdulkarim Hassan Ibrahim, Jitsupa Deepho, Auwal Bala Abubakar, Kazeem Olalekan Aremu. A modified Liu-Storey-Conjugate descent hybrid projection method for convex constrained nonlinear equations and image restoration. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021022
[12]	Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems and Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010
[13]	Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147
[14]	Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial and Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[15]	Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021143
[16]	Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[17]	Ting Hu. Kernel-based maximum correntropy criterion with gradient descent method. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4159-4177. doi: 10.3934/cpaa.2020186
[18]	Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems and Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[19]	Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003
[20]	Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Wataru Nakamura Yasushi Narushima Hiroshi Yabe
on Google Scholar
Wataru Nakamura Yasushi Narushima Hiroshi Yabe

[Back to Top]