Abstract
The steepest descent algorithm with exact line searches (Cauchy algorithm) is inefficient, generating oscillating step lengths and a sequence of points converging to the span of the eigenvectors associated with the extreme eigenvalues. The performance becomes very good if a short step is taken at every (say) ten iterations. We show a new method for estimating short steps, and propose a method alternating Cauchy and short steps. Finally, we use the roots of a certain Chebyshev polynomial to further accelerate the methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akaike, H.: On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method. Ann. Inst. Stat. Math. Tokyo 11, 1–17 (1959)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)
Birgin, E.G., Martínez, J.M., Raydan, M.: Spectral projected gradient methods. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 3652–3659. Springer, New York (2009)
Cauchy, A.: Méthode générale pour la résolution des systèmes d’équations simultanées. Comp. Rend. Acad. Sci. Paris 25, 536–538 (1847)
Dai, Y.H.: Alternate step gradient method. Optimization 52(4–5), 395–415 (2003)
de Asmundis, R., di Serafino, D., Hager, W., Toraldo, G., Zhang, H.: An efficient gradient method using the Yuan steplength. Comput. Optim. Appl. 59, 541–563 (2014). doi:10.1007/s10589-014-9669-5
de Asmundis, R., di Serafino, D., Riccio, R., Toraldo, G.: On spectral properties of steepest descent methods. IMA J. Numer. Anal. 33, 1416–1435 (2013)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Forsythe, G.E.: On the asymptotic directions of the s-dimensional optimum gradient method. Numer. Math. 11, 57–76 (1968)
Gonzaga, C.C.: Optimal performance of the steepest descent algorithm for quadratic functions. Technical report, Federal University of Santa Catarina, Florianopolis, Brazil (2014)
Nocedal, J., Sartenaer, A., Zhu, C.: On the behavior of the gradient norm in the steepest descent method. Comput. Optim. Appl. 22, 5–35 (2002)
Raydan, M.: The Barzilai and Borwein gradient method for large scale unconstrained minimization problem. SIAM J. Optim. 7, 26–33 (1997)
Raydan, M., Svaiter, B.: Relaxed steepest descent and Cauchy-Barzilai-Borwein method. Comput. Optim. Appl. 21, 155–167 (2002)
Acknowledgments
The author was partially supported by CNPq under Grant 308413/2009-1.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gonzaga, C.C., Schneider, R.M. On the steepest descent algorithm for quadratic functions. Comput Optim Appl 63, 523–542 (2016). https://doi.org/10.1007/s10589-015-9775-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-015-9775-z