Modification of the Armijo line search to satisfy the convergence properties of HS method
DOI:
https://doi.org/10.11121/ijocta.01.2013.00141Keywords:
unconstrained optimization, conjugate gradient method, line search algorithmAbstract
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.Downloads
References
Armijo, L., Minimization of functions having Lipschits continuous partial derivatives, Pacific J. Math., 16, (1966) 1–3.
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). Crossref
Birgin, E.G., Martinez, J.M., A spectral conjugate gradient method for unconstrained optimization, Appl. Math. Optim., 43, 117–128 (2001). Crossref
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). Crossref
Dai, Y.H., Yuan, Y., Convergence properties of the conjugate descent method, Advances in Mathematics, 25, 552–562 (1996).
Dai, Y.H., Yuan, Y., A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal of Optimization, 10, 177–182 (1999). Crossref
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). Crossref
Fletcher, R., Practical Method of Optimization, second ed., vol. I: Unconstrained Optimization, Wiley, New York, (1997).
Fletcher, R., Reeves, C., Function minimization by conjugate gradients, Comput. J., 7, 149–154 (1964). Crossref
Fasano, G., Planar conjugate gradient algorithm for large scale unconstrained optimization. Part 1: Theory, Journal of Optimization Theory and Applications, 125, 523–541 (2005). Crossref
Fasano, G., Planar conjugate gradient algorithm for large-scale unconstrained optimization. Part 1: Applications, Journal of Optimization Theory and Applications, 125, 543–558 (2005). Crossref
Grippo, L., Lucidi, S., A globally convergent version of the Polak–Ribi`ere conjugate gradient method, Mathematical Programming, 78, 375–391 (1997). Crossref
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). Crossref
Goldstein, A.A., On steepest descent, SIAM J. Control, 3, 147–151 (1965).
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). Crossref
Hu, Y.F., Storey, C., Global convergence result for conjugate gradient methods, Journal of Optimization Theory and Applications, 71, 399–405 (1991). Crossref
Liu, Y., Storey, C., Efficient generalized conjugate gradient algorithms. Part 1: Theory, Journal of Optimization Theory and Applications, 69, 129–137 (1991). Crossref
Mor´e, J.J., Garbow, B.S., Hillstrom, K.E., Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 17–41 (1981). Crossref
Polak, E., Ribi`ere, G., Note Sur la convergence de directions conjug`ees, Rev. Francaise Informat Recherche Operationelle, 3eAnn`ee16, 35–43 (1969).
Polyak, B.T., The conjugate gradient method in extreme problems, USSR Comp. Math. Math. Phys., 9, 94–112 (1969). Crossref
Powell, M.J.D., Nonconvex minimization calculations and the conjugate gradient method, Lecture Notes in Mathematics, 1066, Springer-Verlag, Berlin, 122–141 (1984).
Sun, J., Zhang, J.P., Convergence of conjugate gradient methods without line search, Annals of Operations Research, 103, 161–173 (2001). Crossref
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). Crossref
Shi, Z.J., Shen, J., Convergence of descent method without line search, Appl. Math. Comput., 167, 94–107 (2005). Crossref
Shi, Z.J., Restricted PR conjugate gradient method and its global convergence, Advances in Mathematics, 31(1), 47–55 (2002)(in Chinese).
Shi, Z.J., Shen, J., Convergence of Polak Rebi`ere Polyak conjugate gradient method, Nonlinear Analysis, 66, 1428–1441 (2007). Crossref
Shi, Z.J., Shen, J., Convergence of LiuStorey conjugate gradient method, European Journal of Operational Research,182(2), 552–560 (2007). Crossref
Oktrik.com. (2020). Oktrik.com. [online] Available at: https://www.oktrik.com/ [Accessed 18 Jan. 2014].
Yuan, Y. Numerical Methods for Nonlinear Programming, Shanghai Scientiï¬c & Technical Publishers, (1993).
Yuan, Y. Analysis on the conjugate gradient method, Optimization Methods and Software, 2, 19–29 (1993). Crossref
Zoutendijk, G. Nonlinear programming computational methods, in: J. Abadie (Ed.), Integer and Nonlinear Programming, NorthHolland, Amsterdam, 37–86 (1970).
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
