Extensions of the Hestenes-Stiefel and Polak-Ribiere-Polyak conjugate gradient methods with sufficient descent property

Document Type: Research Paper

Authors

1 Department of Mathematics‎, ‎Faculty of Mathematics‎, ‎Statistics and Computer Science‎, ‎Semnan University‎, ‎P.O‎. ‎Box 35195--363‎, ‎Semnan‎, ‎Iran.

2 Faculty of Mathematical Sciences, Ferdowsi University of Mashhad‎, ‎P.O‎. ‎Box‎: ‎9177948953, Mashhad‎, ‎Iran.

Abstract

Using search directions of a recent class of three--term conjugate gradient methods, modified versions of the Hestenes-Stiefel and Polak-Ribiere-Polyak methods are proposed which satisfy the sufficient descent condition. The methods are shown to be globally convergent when the line search fulfills the (strong) Wolfe conditions. Numerical experiments are done on a set of CUTEr unconstrained optimization test problems. They demonstrate efficiency of the proposed methods in the sense of the Dolan-More performance profile.

Keywords

Main Subjects


N. Andrei, Numerical comparison of conjugate gradient algorithms for unconstrained optimization, Stud. Inform. Control 16 (2007), no. 4, 333--352.

N. Andrei, A modified  Polak--Ribiere--Polyak conjugate gradient algorithm for unconstrained optimization, Optimization 60 (2011), no. 12, 1457--1471.

N. Andrei, Open problems in conjugate gradient algorithms for unconstrained optimization, Bull. Malays. Math. Sci. Soc. 34 (2011), no. 2, 319--330.

S. Babaie--Kafaki, An eigenvalue study on the sufficient descent property of a modified Polak--Ribiere--Polyak conjugate gradient method, Bull. Iranian Math. Soc. 40 (2014), no. 1, 235--242.

S. Babaie--Kafaki, On the sufficient descent condition of the Hager Zhang conjugate gradient methods, 4OR 12 (2014), no. 3, 285--292.

S. Babaie--Kafaki, On optimality of two adaptive choices for the parameter of Dai Liaomethod, Optim. Lett. 10 (2016), no. 8, 1789--1797.

S. Babaie--Kafaki and R. Ghanbari, The Dai--Liao nonlinear conjugate gradient method with optimal parameter choices, European J. Oper. Res. 234 (2014), no. 3, 625--630.

S. Babaie--Kafaki and R. Ghanbari, A descent extension of the Polak Ribiere Polyak conjugate gradient method, Comput. Math. Appl. 68 (2014), no. 12, 2005--2011.

S. Babaie--Kafaki and R. Ghanbari, A descent family of Dai--Liao conjugate gradient methods, Optim. Methods Softw. 29 (2014), no. 3, 583--591.

S. Babaie--Kafaki and R. Ghanbari, Two modified  three--term conjugate gradient methods with sufficient descent property, Optim. Lett. 8 (2014), no. 8, 2285--2297.

S. Babaie--Kafaki and R. Ghanbari, Two optimal Dai--Liao conjugate gradient methods, Optimization 64 (2015), no. 11, 2277--2287.

W. Cheng, A two--term PRP--based descent method, Numer. Funct. Anal. Optim. 28 (2007), no. 11-12, 1217--1230.

Z. Dai, X. Chen and F. Wen, A modified  Perry's conjugate gradient method--based derivative--free method for solving large--scale nonlinear monotone equations, Appl. Math. Comput. 270 (2015), no. 7, 378--386.

Y.H. Dai and C.X. Kou, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search, SIAM J. Optim. 23 (2013), no. 1, 296--320.

Y.H. Dai and L.Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods, Appl. Math. Optim. 43 (2001), no. 1, 87--101.

E.D. Dolan and J.J. More, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), no. 2, Ser. A, 201--213.

X.L. Dong, H.W. Liu and Y.B. He, A self--adjusting conjugate gradient method with sufficient descent condition and conjugacy condition, J. Optim. Theory Appl. 165 (2015), no. 1, 225--241.

X.L. Dong, H.W. Liu, Y.B. He and X.M. Yang, A modified  Hestenes--Stiefel conjugate gradient method with sufficient descent condition and conjugacy condition, J. Comput. Appl. Math. 281 (2015), no. 1, 239--249.

M. Fatemi, An optimal parameter for Dai--Liao family of conjugate gradient methods, J. Optim. Theory Appl. 169 (2016), no. 2, 587--605.

N.I.M. Gould, D. Orban and Ph.L. Toint, CUTEr: a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software 29 (2003), no. 4, 373--394.

W.W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim. 16 (2005), no. 1, 170--192.

W.W. Hager and H. Zhang, Algorithm 851: CG􀀀Descent, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Software 32 (2006), no. 1, 113--137.

W.W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods, Pac. J. Optim. 2 (2006), no. 1, 35--58.

M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), no. 6, 409--436.

Y. Narushima, H. Yabe and J.A. Ford, A three--term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim. 21 (2011), no. 1, 212--230.

E. Polak and G. Ribiere, Note sur la convergence de methodes de directions conjuguees, Rev. Francaise Informat. Recherche Operationnelle 3 (1969), no. 16, 35--43.

B.T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys. 9 (1969), no. 4, 94--112.

M.J.D. Powell, Convergence properties of algorithms for nonlinear optimization, SIAM Rev. 28 (1986), no. 4, 487--500.

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, J. Optim. Theory Appl. 153 (2012), no. 3, 733--757.

W. Sun and Y.X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, New York, 2006.

C. Xu and J.Z. Zhang, A survey of quasi--Newton equations and quasi--Newton methods for optimization, Ann. Oper. Res. 103 (2001), no. 1-4, 213--234.

G. Yu, L. Guan and G. Li, Global convergence of modified  Polak--Ribiere--Polyak conjugate gradient methods with sufficient descent property, J. Ind. Manag. Optim. 4 (2008), no. 3, 565--579.

G.L. Yuan, Modified  nonlinear conjugate gradient methods with sufficient descent property for large--scale optimization problems, Optim. Lett. 3 (2009), no. 1, 11--21.

G.L. Yuan, X.W. Lu and Z.X. Wei, A conjugate gradient method with descent direction for unconstrained optimization, J. Comput. Appl. Math. 233 (2009), no. 2, 519--530.

G.L. Yuan, Z. Wei and Q. Zhao, A modified Polak Ribiere Polyak conjugate gradient algorithm for large--scale optimization problems, IIE Trans. 46 (2014), no. 4, 397--413.

G.L. Yuan and M. Zhang, A modified Hestenes Stiefel conjugate gradient algorithm for large--scale optimization, Numer. Funct. Anal. Optim. 34 (2013), no. 8, 914--937.

L. Zhang, W. Zhou and D.H. Li, A descent modified Polak Ribiere--Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006), no. 4, 629--640.

L. Zhang, W. Zhou and D.H. Li, Some descent three term conjugate gradient methods and their global convergence, Optim. Methods Softw. 22 (2007), no. 4, 697--711.