×

Matrix analyses on the Dai-Liao conjugate gradient method. (English) Zbl 1415.90146

Summary: Some optimal choices for a parameter of the Dai-Liao conjugate gradient method are proposed by conducting matrix analyses of the method. More precisely, first the \(\ell_{1}\) and \(\ell_{\infty}\) norm condition numbers of the search direction matrix are minimized, yielding two adaptive choices for the Dai-Liao parameter. Then we show that a recent formula for computing this parameter which guarantees the descent property can be considered as a minimizer of the spectral condition number as well as the well-known measure function for a symmetrized version of the search direction matrix. Brief convergence analyses are also carried out. Finally, some numerical experiments on a set of test problems related to constrained and unconstrained testing environment, are conducted using a well-known performance profile.

MSC:

90C53 Methods of quasi-Newton type
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods

Software:

CUTEr; CG_DESCENT
Full Text: DOI

References:

[1] N.Andrei, “Open problems in conjugate gradient algorithms for unconstrained optimization“, Bull. Malays. Math. Sci. Soc.34 (2011) 319-330; <uri xlink:type=”simple“ xlink:href=”http://emis.ams.org/journals/BMMSS/pdf/v34n2/v34n2p11.pdf”>http://emis.ams.org/journals/BMMSS/pdf/v34n2/v34n2p11.pdf. · Zbl 1225.49030
[2] S.Babaie-Kafaki and R.Ghanbari, “The Dai-Liao nonlinear conjugate gradient method with optimal parameter choices“, European J. Oper. Res.234 (2014) 625-630; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1016/j.ejor.2013.11.012”>10.1016/j.ejor.2013.11.012. · Zbl 1304.90216
[3] S.Babaie-Kafaki and R.Ghanbari, “A descent family of Dai-Liao conjugate gradient methods“, Optim. Methods Softw.29 (2014) 583-591; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1080/10556788.2013.833199”>10.1080/10556788.2013.833199. · Zbl 1285.90063
[4] S.Babaie-Kafaki and R.Ghanbari, “Two optimal Dai-Liao conjugate gradient methods“, Optimization64 (2015) 2277-2287; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1080/02331934.2014.938072”>10.1080/02331934.2014.938072. · Zbl 1386.65158
[5] S.Babaie-Kafaki and R.Ghanbari, “A class of adaptive Dai-Liao conjugate gradient methods based on the scaled memoryless BFGS update“, 4OR15 (2017) 85-92; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1007/s10288-016-0323-1”>10.1007/s10288-016-0323-1. · Zbl 1360.90293
[6] R. H.Byrd and J.Nocedal, “A tool for the analysis of quasi-Newton methods with application to unconstrained minimization“, SIAM J. Numer. Anal.26 (1989) 727-739; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1137/0726042”>10.1137/0726042. · Zbl 0676.65061
[7] 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; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1137/S1052623494268443”>10.1137/S1052623494268443. · Zbl 0957.65062
[8] 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:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1137/100813026”>10.1137/100813026. · Zbl 1266.49065
[9] Y. H.Dai and L. Z.Liao, “New conjugacy conditions and related nonlinear conjugate gradient methods“, Appl. Math. Optim.43 (2001) 87-101; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1007/s002450010019”>10.1007/s002450010019. · Zbl 0973.65050
[10] E. D.Dolan and J. J.Moré, “Benchmarking optimization software with performance profiles“, Math. Program. Ser. A91(2) (2002) 201-213; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1007/s101070100263”>10.1007/s101070100263. · Zbl 1049.90004
[11] M.Fatemi, “An optimal parameter for Dai-Liao family of conjugate gradient methods“, J. Optim. Theory Appl.169 (2016) 587-605; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1007/s10957-015-0786-9”>10.1007/s10957-015-0786-9. · Zbl 1368.90131
[12] N. I. M.Gould, D.Orban and P. L.Toint, “CUTEr: a constrained and unconstrained testing environment, revisited“, ACM Trans. Math. Software29 (2003) 373-394; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1145/962437.962439”>10.1145/962437.962439. · Zbl 1068.90526
[13] W. W.Hager and H.Zhang, “A new conjugate gradient method with guaranteed descent and an efficient line search“, SIAM J. Optim.16 (2005) 170-192; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1137/030601880”>10.1137/030601880. · Zbl 1093.90085
[14] W. W.Hager and H.Zhang, “Algorithm 851: CG-descent, a conjugate gradient method with guaranteed descent“, ACM Trans. Math. Software32 (2006) 113-137; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1145/1132973.1132979”>10.1145/1132973.1132979. · Zbl 1346.90816
[15] W. W.Hager and H.Zhang, “A survey of nonlinear conjugate gradient methods“, Pac. J. Optim.2(1) (2006) 35-58; <uri xlink:type=”simple“ xlink:href=”https://www.caam.rice.edu/ yzhang/caam554/pdf/cgsurvey.pdf”>https://www.caam.rice.edu/∼yzhang/caam554/pdf/cgsurvey.pdf. · Zbl 1117.90048
[16] M. R.Hestenes and E.Stiefel, “Methods of conjugate gradients for solving linear systems“, J. Res. Nat. Bur. Stand.49 (1952) 409-436; doi:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.6028/jres.049.044”>10.6028/jres.049.044. · Zbl 0048.09901
[17] J.Nocedal and S. J.Wright, Numerical optimization, Springer Ser. Oper. Res. Financ. Eng. (Springer, New York, 2006); doi:10.1007/978-0-387-40065-5. · Zbl 1104.65059
[18] M. J. D.Powell, “Some global convergence properties of a variable metric algorithm for minimization without exact line searches“, in: Nonlinear programming, Volume 9 of SIAM-AMS Proc. (eds <string-name name-style=”western“> <given-names initials=”R.“>R. W.Cottle and <string-name name-style=”western“> <given-names initials=”C.”>C. E.Lemke), (American Mathematical Society, Providence, RI, 1976) 53-72.
[19] W.Sun and Y. X.Yuan, Optimization theory and methods: nonlinear programming (Springer, New York, 2006); https://www.springer.com/gp/book/9780387249759. · Zbl 1129.90002
[20] D. S.Watkins, Fundamentals of matrix computations (John Wiley, New York, 2002); https://www.wiley.com/enus/Fundamentals+of+Matrix+Computations · Zbl 1005.65027
[21] 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:<uri xlink:type=”simple“ xlink:href=”https://doi.org/10.1023/A:1012959223138”>10.1023/A:1012959223138. · Zbl 1007.90069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.