Mohammed BELLOUFİ, Rachid BENZİNE, Yamina LASKRİ

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.

PDF

___

[1] Armijo, L., Minimization of functions having Lipschits continuous partial derivatives, Pacific 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 conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117-128 (2001).
[4] Chen, X.D., Sun, J., Global convergence of a two-parameter family of conjugate gradient 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 convergence property, SIAM Journal of Optimization, 10, 177-182 (1999).
[7] Dai, Y.H., Han, J.Y., Liu, G.H., Sun, D.F., Yin, H.X., Yuan, Y.X., Convergence properties of nonlinear conjugate gradient methods, SIAM Journal of Optimization, 10, 345-358 (1999).
[8] Fletcher, R., Practical Method of Optimization, second ed., vol. I: Unconstrained Optimization, Wiley, New York, (1997).
[9] Fletcher, R., Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149-154 (1964).
[10] Fasano, G., Planar conjugate gradient algorithm for large scale unconstrained optimization. Part 1: Theory, Journal of Optimization Theory and Applications, 125, 523-541 (2005).
[11] Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization. Part 1: Applications, Journal of Optimization Theory and Applications, 125, 543- 558 (2005).
[12] Grippo, L., Lucidi, S., A globally convergent version of the Polak-Ribi`ere conjugate gradient method, Mathematical Programming, 78, 375-391 (1997).
[13] Grippo, L., Lucidi, S., Convergence conditions, line search algorithms and trust region implementations for the Polak Ribi`ere conjugate 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 systems, J. Res. Nat. Bur. Standars Sect., 5(49), 409-436 (1952).
[16] Hu, Y.F., Storey, C., Global convergence result for conjugate gradient methods, Journal of Optimization Theory and Applications, 71, 399-405 (1991).
[17] Liu, Y., Storey, C ., Efficient generalized conjugate gradient algorithms. Part 1: Theory, Journal of Optimization Theory and Applications, 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 convergence de directions conjug`ees, Rev. Francaise 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 Mathematics, 1066, Springer-Verlag, Berlin, 122-141 (1984).
[22] Sun, J., Zhang, J.P., Convergence of conjugate gradient methods without line search, Annals of O perations 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 Chinese).
[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 LiuStorey 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 & Technical Publishers, (1993).
[30] Yuan, Y. Analysis on the conjugate gradient method, Optimization Methods and Software, 2, 19-29 (1993).
[31] Zoutendijk, G. Nonlinear programming computational methods, in: J. Abadie (Ed.), Integer and Nonlinear Programming, NorthHolland, Amsterdam, 37-86 (1970).