A descent hybrid modification of the Polak–Ribière–Polyak conjugate gradient method
RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 567-574.

Hybridizing self-adjusting approach of Dong et al. and three-term formulation of Zhang et al., a nonlinear conjugate gradient method is proposed. The method reduces to the Polak–Ribière–Polyak method under the exact line search and satisfies the sufficient descent condition independent of the line search and the objective function convexity. Similar to the Polak–Ribière–Polyak method, the method possesses an automatic restart feature which avoids jamming. Global convergence analyses are conducted when the line search fulfills the popular Wolfe conditions as well as an Armijo-type condition. Numerical experiments are done on a set of CUTEr unconstrained optimization test problems. Results of comparisons show computational efficiency of the proposed method in the sense of Dolan–Moré performance profile.

Received:
Accepted:
DOI: 10.1051/ro/2016009
Classification: 90C53, 49M37, 65K05
Keywords: Unconstrained optimization, conjugate gradient method, sufficient descent condition, line search, global convergence
Babaie-Kafaki, Saman 1; Ghanbari, Reza 2

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.
@article{RO_2016__50_3_567_0,
     author = {Babaie-Kafaki, Saman and Ghanbari, Reza},
     title = {A descent hybrid modification of the {Polak{\textendash}Ribi\`ere{\textendash}Polyak} conjugate gradient method},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {567--574},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ro/2016009},
     mrnumber = {3538840},
     zbl = {1354.90174},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2016009/}
}
TY  - JOUR
AU  - Babaie-Kafaki, Saman
AU  - Ghanbari, Reza
TI  - A descent hybrid modification of the Polak–Ribière–Polyak conjugate gradient method
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 567
EP  - 574
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2016009/
DO  - 10.1051/ro/2016009
LA  - en
ID  - RO_2016__50_3_567_0
ER  - 
%0 Journal Article
%A Babaie-Kafaki, Saman
%A Ghanbari, Reza
%T A descent hybrid modification of the Polak–Ribière–Polyak conjugate gradient method
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 567-574
%V 50
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2016009/
%R 10.1051/ro/2016009
%G en
%F RO_2016__50_3_567_0
Babaie-Kafaki, Saman; Ghanbari, Reza. A descent hybrid modification of the Polak–Ribière–Polyak conjugate gradient method. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 3, pp. 567-574. doi : 10.1051/ro/2016009. http://archive.numdam.org/articles/10.1051/ro/2016009/

N. Andrei, A modified Polak–Ribière–Polyak conjugate gradient algorithm for unconstrained optimization. Optimization 60 (2011) 1457–1471. | DOI | MR | Zbl

N. Andrei, An adaptive conjugate gradient algorithm for large–scale unconstrained optimization. J. Comput. Appl. Math. 292 (2016) 83–91. | DOI | MR | Zbl

S. Babaie-Kafaki, An eigenvalue study on the sufficient descent property of a modified Polak–Ribière–Polyak conjugate gradient method. Bull. Iranian Math. Soc. 40 (2014) 235–242. | MR | Zbl

S. Babaie-Kafaki and R. Ghanbari, A descent extension of the Polak–Ribière–Polyak conjugate gradient method. Comput. Math. Appl. 68 (2014) 2005–2011. | DOI | MR | Zbl

W. Cheng, A two-term PRP-based descent method. Numer. Funct. Anal. Optim. 28 (2007) 1217–1230. | DOI | MR | Zbl

Y.H. Dai and L.Z. Liao, New conjugacy conditions and related nonlinear conjugate gradient methods. Appl. Math. Optim. 43 (2001) 87–101. | DOI | MR | Zbl

Y.H. Dai, J.Y. Han, G.H. Liu, D.F. Sun, H.X. Yin and Y.X. Yuan, Convergence properties of nonlinear conjugate gradient methods. SIAM J. Optim. 10 (1999) 348–358. | Zbl

S. Deng, Z. Wan and X. Chen, An improved spectral conjugate gradient algorithm for nonconvex unconstrained optimization problems. J. Optim. Theory Appl. 157 (2013) 820–842. | DOI | MR | Zbl

E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Program. 91 (2002) 201–213. | DOI | MR | Zbl

X.L. Dong, H.W. Liu and Y.B. He, New version of the three-term conjugate gradient method based on spectral scaling conjugacy condition that generates descent search direction. Appl. Math. Comput. 269 (2015) 606–617. | DOI | MR | Zbl

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) 225–241. | DOI | MR | Zbl

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) 239–249. | DOI | MR | Zbl

N.I.M. Gould, D. Orban and Ph.L. Toint, CUTEr: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29 (2003) 373–394. | DOI | Zbl

W.W. Hager and H. Zhang, Algorithm 851: CG−Descent, a conjugate gradient method with guaranteed descent. ACM Trans. Math. Softw. 32 (2006) 113–137. | DOI | MR | Zbl

W.W. Hager and H. Zhang, A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2 (2006) 35–58. | MR | Zbl

M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Standards 49 (1952) 409–436. | DOI | MR | Zbl

E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées. Rev. Française Informat. Recherche Opérationnelle 3 (1969) 35–43. | Numdam | MR | Zbl

B.T. Polyak, The conjugate gradient method in extreme problems. USSR Comp. Math. Math. Phys. 9 (1969) 94–112. | DOI | Zbl

W. Sun and Y.X. Yuan, Optimization Theory and Methods: Nonlinear Programming. Springer, New York (2006). | MR | Zbl

Z. Wan, Z.L. Yang and Y.L. Wang, New spectral PRP conjugate gradient method for unconstrained optimization. Appl. Math. Lett. 24 (2011) 16–22. | DOI | MR | Zbl

G. Yu, L. Guan and G. Li, Global convergence of modified Polak–Ribière–Polyak conjugate gradient methods with sufficient descent property. J. Ind. Manag. Optim. 4 (2008) 565–579. | DOI | MR | Zbl

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

L. Zhang, W. Zhou and D.H. Li, A descent modified Polak–Ribière–Polyak conjugate gradient method and its global convergence. IMA J. Numer. Anal. 26 (2006) 629–640. | DOI | MR | Zbl

Cited by Sources: