Modification of the Armijo line search to satisfy the convergence properties of HS method
The Hestenes-Stiefel (HS) conjugate gradient algorithm is a useful tool of unconstrainednumerical optimization, which has good numerical performance but no global convergence result under traditional line searches. This paper proposes a line search technique that guarantee the globalconvergence of the Hestenes-Stiefel (HS) conjugate gradient method. Numerical tests are presented tovalidate the different approaches.
[1] Armijo, L., Minimization of functions having Lipschits continuous partial derivatives, Pa- cific J. Math., 16, (1966) 1–3.
[2] Al-Baali, M., Descent property and global convergence of the Fletcher–Reeves method with inexact line search, IMA J. Numer. Anal., 5, 121–124 (1985).
[3] Birgin, E.G., Martinez, J.M., A spectral con- jugate gradient method for unconstrained op- timization, Appl. Math. Optim., 43, 117–128 (2001).
[4] Chen, X.D., Sun, J., Global convergence of a two-parameter family of conjugate gradi- ent methods without line search, Journal of Computational and Applied Mathematics, 146, 37–45 (2002).
[5] Dai, Y.H., Yuan, Y., Convergence properties of the conjugate descent method, Advances in Mathematics, 25, 552–562 (1996).
[6] Dai, Y.H., Yuan, Y., A nonlinear conjugate gradient method with a strong global conver- gence property, SIAM Journal of Optimiza- tion, 10, 177–182 (1999).
[7] Dai, Y.H., Han, J.Y., Liu, G.H., Sun, D.F., Yin, H.X., Yuan, Y.X., Convergence proper- ties of nonlinear conjugate gradient methods, SIAM Journal of Optimization, 10, 345–358 (1999).
[8] Fletcher, R., Practical Method of Optimiza- tion, second ed., vol. I: Unconstrained Opti- mization, Wiley, New York, (1997).
[9] Fletcher, R., Reeves, C., Function minimiza- tion by conjugate gradients, Comput. J., 7, 149–154 (1964).
[10] Fasano, G., Planar conjugate gradient algo- rithm for large scale unconstrained optimiza- tion. Part 1: Theory, Journal of Optimiza- tion Theory and Applications, 125, 523–541 (2005).
[11] Fasano, G., Planar conjugate gradient algo- rithm for large-scale unconstrained optimiza- tion. Part 1: Applications, Journal of Opti- mization Theory and Applications, 125, 543– 558 (2005).
[12] Grippo, L., Lucidi, S., A globally convergent version of the Polak–Ribi`ere conjugate gradi- ent method, Mathematical Programming, 78, 375–391 (1997).
[13] Grippo, L., Lucidi, S., Convergence condi- tions, line search algorithms and trust region implementations for the Polak Ribi`ere conju- gate gradient method, Optimization Methods and Software, 20(1), 71–98 (2005).
[14] Goldstein, A.A., On steepest descent, SIAM J. Control, 3, 147–151 (1965).
[15] Hestenes, M.R., and Stiefel, E.L., Methods of conjugate gradients for solving linear sys- tems, J. Res. Nat. Bur. Standars Sect. , 5(49), 409-436 (1952).
[16] Hu, Y.F., Storey, C., Global convergence re- sult for conjugate gradient methods, Journal of Optimization Theory and Applications, 71, 399–405 (1991).
[17] Liu, Y., Storey, C., Efficient generalized con- jugate gradient algorithms. Part 1: Theory, Journal of Optimization Theory and Appli- cations, 69, 129–137 (1991).
[18] Mor´e, J.J., Garbow, B.S., Hillstrom, K.E., Testing unconstrained optimization software, ACM Trans. Math. Softw. , 7, 17–41 (1981).
[19] Polak, E., Ribi`ere, G., Note Sur la con- vergence de directions conjug`ees, Rev. Fran- caise Informat Recherche Operationelle, 3e Ann`ee16, 35–43 (1969).
[20] Polyak, B.T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9, 94–112 (1969).
[21] Powell, M.J.D., Nonconvex minimization calculations and the conjugate gradient method, Lecture Notes in Mathemat- ics, 1066, Springer-Verlag, Berlin, 122–141 (1984).
[22] Sun, J., Zhang, J.P., Convergence of conju- gate gradient methods without line search, Annals of Operations Research, 103, 161–173 (2001).
[23] Sun, J., Yang, X.Q., Chen, X.D., Quadratic cost flow and the conjugate gradient method, European Journal of Operational Research, 164, 104–114 (2005).
[24] Shi, Z.J., Shen, J., Convergence of descent method without line search, Appl. Math. Comput., 167, 94–107 (2005).
[25] Shi, Z.J., Restricted PR conjugate gradient method and its global convergence, Advances in Mathematics, 31(1), 47–55 (2002)(in Chi- nese).
[26] Shi, Z.J., Shen, J., Convergence of Polak Rebi`ere Polyak conjugate gradient method, Nonlinear Analysis, 66, 1428–1441 (2007).
[27] Shi, Z.J., Shen, J., Convergence of Liu- Storey conjugate gradient method, European Journal of Operational Research,182(2), 552– 560 (2007).
[28] Wolfe, P. Convergence conditions for ascent methods, SIAM Rev., 11, 226–235 (1969).
[29] Yuan, Y. Numerical Methods for Nonlinear Programming, Shanghai Scientific & Techni- cal Publishers, (1993).
[30] Yuan, Y. Analysis on the conjugate gradient method, Optimization Methods and Software, 2, 19–29 (1993).
[31] Zoutendijk, G. Nonlinear programming com- putational methods, in: J. Abadie (Ed.), In- teger and Nonlinear Programming, North- Holland, Amsterdam, 37–86 (1970).