A restart scheme for the Dai–Liao conjugate gradient method by ignoring a direction of maximum magnification by the search direction matrix
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 981-991.

As known, finding an effective restart procedure for the conjugate gradient methods has been considered as an open problem. Here, we aim to study the problem for the Dai–Liao conjugate gradient method. In this context, based on a singular value analysis conducted on the Dai–Liao search direction matrix, it is shown that when the gradient approximately lies in the direction of the maximum magnification by the matrix, the method may get into some computational errors as well as it may converge hardly. In such situation, ignoring the Dai–Liao search direction in the sense of performing a restart may enhance the numerical stability as well as may accelerate the convergence. Numerical results are reported; they demonstrate effectiveness of the suggested restart procedure in the sense of the Dolan–Moré performance profile.

DOI : 10.1051/ro/2019045
Classification : 90C53, 65K05, 65F35
Mots-clés : Nonlinear programming, unconstrained optimization, conjugate gradient method, restart strategy, maximum magnification 
@article{RO_2020__54_4_981_0,
     author = {Aminifard, Zohre and Babaie-Kafaki, Saman},
     title = {A restart scheme for the {Dai{\textendash}Liao} conjugate gradient method by ignoring a direction of maximum magnification by the search direction matrix},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {981--991},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {4},
     year = {2020},
     doi = {10.1051/ro/2019045},
     mrnumber = {4091856},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2019045/}
}
TY  - JOUR
AU  - Aminifard, Zohre
AU  - Babaie-Kafaki, Saman
TI  - A restart scheme for the Dai–Liao conjugate gradient method by ignoring a direction of maximum magnification by the search direction matrix
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 981
EP  - 991
VL  - 54
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2019045/
DO  - 10.1051/ro/2019045
LA  - en
ID  - RO_2020__54_4_981_0
ER  - 
%0 Journal Article
%A Aminifard, Zohre
%A Babaie-Kafaki, Saman
%T A restart scheme for the Dai–Liao conjugate gradient method by ignoring a direction of maximum magnification by the search direction matrix
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 981-991
%V 54
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2019045/
%R 10.1051/ro/2019045
%G en
%F RO_2020__54_4_981_0
Aminifard, Zohre; Babaie-Kafaki, Saman. A restart scheme for the Dai–Liao conjugate gradient method by ignoring a direction of maximum magnification by the search direction matrix. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 981-991. doi : 10.1051/ro/2019045. http://www.numdam.org/articles/10.1051/ro/2019045/

[1] N. Andrei, Numerical comparison of conjugate gradient algorithms for unconstrained optimization. Stud. Inform. Control 16 (2007) 333–352.

[2] N. Andrei, Open problems in conjugate gradient algorithms for unconstrained optimization. B. Malays. Math. Sci. Soc. 34 (2011) 319–330. | MR | Zbl

[3] S. Babaie-Kafaki, On the sufficient descent condition of the Hager–Zhang conjugate gradient methods. 4OR 12 (2014) 285–292. | DOI | MR | Zbl

[4] S. Babaie-Kafaki and R. Ghanbari, The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices. Eur. J. Oper. Res. 234 (2014) 625–630. | DOI | MR | Zbl

[5] S. Babaie-Kafaki and R. Ghanbari, A descent family of Dai-Liao conjugate gradient methods. Optim. Methods Softw. 29 (2014) 583–591. | DOI | MR | Zbl

[6] S. Babaie-Kafaki and R. Ghanbari, Two optimal Dai-Liao conjugate gradient methods. Optimization 64 (2015) 2277–2287. | DOI | MR

[7] S. Babaie-Kafaki and R. Ghanbari, Descent symmetrization of the Dai-Liao conjugate gradient method. Asia-Pac. J. Oper. Res. 33 (2016) 1650008. | DOI | MR

[8] J. Barzilai and J.M. Borwein, Two–point stepsize gradient methods. IMA J. Numer. Anal. 8 (1988) 141–148. | DOI | MR | Zbl

[9] E.M.L. Beale, A derivation of conjugate gradients In: Numerical Methods for Nonlinear Optimization, edited by F.A. Lootsma. Academic Press, New York, NY (1972) 39–43. | MR | Zbl

[10] H. Crowder and P. Wolfe, Linear convergence of the conjugate gradient method. IBM J. Res. Dev. 16 (1972) 431–433. | DOI | MR | Zbl

[11] 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) 296–320. | DOI | MR | Zbl

[12] 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

[13] 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

[14] Y.H. Dai, L.Z. Liao and D. Li, On restart procedures for the conjugate gradient method. Numer. Algorithms 35 (2004) 249–260. | DOI | MR | Zbl

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

[16] R. Fletcher and C.M. Reeves, Function minimization by conjugate gradients. Comput. J. 7 (1964) 149–154. | DOI | MR | Zbl

[17] J.C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2 (1992) 21–42. | DOI | MR | Zbl

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

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

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

[21] N.J. Higham, Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, PA (2002). | DOI | MR | Zbl

[22] M.F. Mcguire and P. Wolfe, Evaluating a restart procedure for conjugate gradients. Report RC–4382. IBM Research Center, Yorktown Heights (1973).

[23] J. Nocedal and S.J. Wright, Numerical Optimization. Springer, New York, NY (2006). | MR | Zbl

[24] A. Perry, A modified conjugate gradient algorithm. Oper. Res. 26 (1978) 1073–1078. | DOI | MR | Zbl

[25] M.J.D. Powell, Restart procedures for the conjugate gradient method. Math. Program. 12 (1977) 241–254. | DOI | MR | Zbl

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

[27] D.S. Watkins, Fundamentals of Matrix Computations. John Wiley and Sons, New York, NY (2002). | DOI | MR | Zbl

[28] C. Xu and J.Z. Zhang, A survey of quasi-Newton equations and quasi-Newton methods for optimization. Ann. Oper. Res. 103 (2001) 213–234. | DOI | MR | Zbl

[29] G. Zoutendijk, Nonlinear programming computational methods. In: Integer and Nonlinear Programming, edited by J. Abadie. North-Holland, Amsterdam (1970) 37–86. | MR | Zbl

Cité par Sources :