American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  doi: 10.1016/j.aml.2007.05.002.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.05.002.  Google Scholar

[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.  doi: 10.1145/200979.201043.  Google Scholar

[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.  doi: 10.1016/S0377-0427(02)00416-8.  Google Scholar

[5]

W. Cheng, A two-term PRP-based descent method,, Numerical Functional Analysis and Optimization, 28 (2007), 1217.  doi: 10.1080/01630560701749524.  Google Scholar

[6]

Y. H. Dai, Nonlinear conjugate gradient methods,, in, (2011).  doi: 10.1002/9780470400531.eorms0183.  Google Scholar

[7]

Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods,, Applied Mathematics and Optimization, 43 (2001), 87.  doi: 10.1007/s002450010019.  Google Scholar

[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.  doi: 10.1137/S1052623497318992.  Google Scholar

[9]

Y. H. Dai and Y. Yuan, A three-parameter family of nonlinear conjugate gradient methods,, Mathematics of Computation, 70 (2001), 1155.  doi: 10.1090/S0025-5718-00-01253-9.  Google Scholar

[10]

Z. Dai and B. S. Tian, Global convergence of some modified PRP nonlinear conjugate gradient methods,, Optimization Letters, 5 (2011), 615.  doi: 10.1007/s11590-010-0224-8.  Google Scholar

[11]

Z. Dai and F. Wen, A modified CG-DESCENT method for unconstrained optimization,, Journal of Computational and Applied Mathematics, 235 (2011), 3332.  doi: 10.1016/j.cam.2011.01.046.  Google Scholar

[12]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[13]

R. Fletcher, "Practical Methods of Optimization,", $2^{nd}$ edition, (1987).   Google Scholar

[14]

R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients,, The Computer Journal, 7 (1964), 149.  doi: 10.1093/comjnl/7.2.149.  Google Scholar

[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.  doi: 10.1145/962437.962439.  Google Scholar

[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.  doi: 10.1137/030601880.  Google Scholar

[17]

W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods,, Pacific Journal of Optimization, 2 (2006), 35.   Google Scholar

[18]

W. W. Hager and H. Zhang, "CG_DESCENT Version 1.4, User's Guide,", University of Florida, (2005).   Google Scholar

[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.  doi: 10.6028/jres.049.044.  Google Scholar

[20]

M. Li and H. Feng, A sufficient descent LS conjugate gradient method for unconstrained optimization problems,, Applied Mathematics and Computation, 218 (2011), 1577.  doi: 10.1016/j.amc.2011.06.034.  Google Scholar

[21]

Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: Theory,, Journal of Optimization Theory and Applications, 69 (1991), 129.  doi: 10.1007/BF00940464.  Google Scholar

[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.  doi: 10.1016/j.cam.2012.01.036.  Google Scholar

[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.  doi: 10.1137/080743573.  Google Scholar

[24]

J. Nocedal and S. J. Wright, "Numerical Optimization,", $2^{nd}$ edition, (2006).   Google Scholar

[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.  doi: 10.1007/s10957-011-9960-x.  Google Scholar

[26]

W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006).   Google Scholar

[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.  doi: 10.1080/10556780701661344.  Google Scholar

[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.  doi: 10.3934/jimo.2008.4.565.  Google Scholar

[29]

G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems,, Optimization Letters, 3 (2009), 11.  doi: 10.1007/s11590-008-0086-5.  Google Scholar

[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.  doi: 10.1016/j.amc.2011.05.032.  Google Scholar

[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.  doi: 10.1007/s00211-006-0028-z.  Google Scholar

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.  doi: 10.1016/j.aml.2007.05.002.  Google Scholar

[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.  doi: 10.1016/j.cam.2010.05.002.  Google Scholar

[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.  doi: 10.1145/200979.201043.  Google Scholar

[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.  doi: 10.1016/S0377-0427(02)00416-8.  Google Scholar

[5]

W. Cheng, A two-term PRP-based descent method,, Numerical Functional Analysis and Optimization, 28 (2007), 1217.  doi: 10.1080/01630560701749524.  Google Scholar

[6]

Y. H. Dai, Nonlinear conjugate gradient methods,, in, (2011).  doi: 10.1002/9780470400531.eorms0183.  Google Scholar

[7]

Y. H. Dai and L. Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods,, Applied Mathematics and Optimization, 43 (2001), 87.  doi: 10.1007/s002450010019.  Google Scholar

[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.  doi: 10.1137/S1052623497318992.  Google Scholar

[9]

Y. H. Dai and Y. Yuan, A three-parameter family of nonlinear conjugate gradient methods,, Mathematics of Computation, 70 (2001), 1155.  doi: 10.1090/S0025-5718-00-01253-9.  Google Scholar

[10]

Z. Dai and B. S. Tian, Global convergence of some modified PRP nonlinear conjugate gradient methods,, Optimization Letters, 5 (2011), 615.  doi: 10.1007/s11590-010-0224-8.  Google Scholar

[11]

Z. Dai and F. Wen, A modified CG-DESCENT method for unconstrained optimization,, Journal of Computational and Applied Mathematics, 235 (2011), 3332.  doi: 10.1016/j.cam.2011.01.046.  Google Scholar

[12]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles,, Mathematical Programming, 91 (2002), 201.  doi: 10.1007/s101070100263.  Google Scholar

[13]

R. Fletcher, "Practical Methods of Optimization,", $2^{nd}$ edition, (1987).   Google Scholar

[14]

R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients,, The Computer Journal, 7 (1964), 149.  doi: 10.1093/comjnl/7.2.149.  Google Scholar

[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.  doi: 10.1145/962437.962439.  Google Scholar

[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.  doi: 10.1137/030601880.  Google Scholar

[17]

W. W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods,, Pacific Journal of Optimization, 2 (2006), 35.   Google Scholar

[18]

W. W. Hager and H. Zhang, "CG_DESCENT Version 1.4, User's Guide,", University of Florida, (2005).   Google Scholar

[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.  doi: 10.6028/jres.049.044.  Google Scholar

[20]

M. Li and H. Feng, A sufficient descent LS conjugate gradient method for unconstrained optimization problems,, Applied Mathematics and Computation, 218 (2011), 1577.  doi: 10.1016/j.amc.2011.06.034.  Google Scholar

[21]

Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: Theory,, Journal of Optimization Theory and Applications, 69 (1991), 129.  doi: 10.1007/BF00940464.  Google Scholar

[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.  doi: 10.1016/j.cam.2012.01.036.  Google Scholar

[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.  doi: 10.1137/080743573.  Google Scholar

[24]

J. Nocedal and S. J. Wright, "Numerical Optimization,", $2^{nd}$ edition, (2006).   Google Scholar

[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.  doi: 10.1007/s10957-011-9960-x.  Google Scholar

[26]

W. Sun and Y. Yuan, "Optimization Theory and Methods: Nonlinear Programming,", Springer, (2006).   Google Scholar

[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.  doi: 10.1080/10556780701661344.  Google Scholar

[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.  doi: 10.3934/jimo.2008.4.565.  Google Scholar

[29]

G. Yuan, Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems,, Optimization Letters, 3 (2009), 11.  doi: 10.1007/s11590-008-0086-5.  Google Scholar

[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.  doi: 10.1016/j.amc.2011.05.032.  Google Scholar

[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.  doi: 10.1007/s00211-006-0028-z.  Google Scholar

[1]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[2]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[4]

Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012
[5]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[6]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[7]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[8]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[9]

Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065
[10]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[11]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[12]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[13]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[14]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[15]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[16]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[17]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[18]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[19]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[20]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences