Level set of the asymptotic rate of convergence of the method of steepest descent
Abstract
UDC 519.61
The asymptotic rate of convergence of the steepest descent method is considered as a function of the initial approximation. In this work, we study the set of the level of this speed, i.e. the set of initial approximations for which it takes a given value. A method for constructing this set is proposed and its connected components are found.
References
A. Cauchy, Methode generale pour la resolution des systems d’equations simultanees, Comptes Rend. Hebd. Seances Acad. Sci. Paris, 25, 536 – 538 (1847).
L. V. Kantorovych, Funktsyonalnyi analyz y prykladnaia matematyka, Uspekhy mat., nauk,3, № 6 (28), 89 – 185 (1948).
A. A. Samarskyi, E. S. Nykolaev, Metody reshenyia setochnykh uravnenyi, Nauka, Moskva (1978).
J. M. Ortega, W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Acad. Press, New York; London (1970).
V. V. Ermakov, N. N. Kalytkyn, Dvukhstupenchatyi hradyentnyi spusk, Zhurn. vychyslyt. matematyky y mat. fyzyky,20, № 4, 1040 – 1045 (1980).
J. Barzilai, J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal.,8, 141 – 148 (1988). DOI: https://doi.org/10.1093/imanum/8.1.141
G. E. Forsythe, T. S. Motzkin, Asymptotic properties of the optimum gradient method (abstract), Bull. Amer. Math. Soc., 57, 183 (1951).
H. Akaike, On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Statist. Math., 11, 1 – 16 (1959), https://doi.org/10.1007/bf01831719 DOI: https://doi.org/10.1007/BF01831719
Y. V. Emelyn, O bystrote skhodymosty metoda nayskoreisheho spuska, Uspekhy mat., nauk,32, № 1 (193), 163 – 164 (1977).
P. F. Zhuk, Ob asymptotycheskykh svoistvakh metoda nayskoreisheho spuska v zadachakh na sobstvennye znachenyia, Zhurn. vychyslyt. matematyky y mat. fyzyky, 21, № 2, 271 – 285 (1981).
P. F. Zhuk, V. H. Prykazchykov, Effektyvnaia otsenka skhodymosty neiavnoho yteratsyonnoho metoda v zadachakh na sobstvennye znachenyia, Dyfferents. uravnenyia, 18, № 7, 1197 – 1202 (1982).
P. F. Zhuk, Asymptotycheskaia skorost skhodymosty metoda nayskoreisheho spuska v zadachakh na sobstvennye znachenyia, Zhurn. vychyslyt. matematyky y mat. fyzyky,24, № 4, 605 – 607 (1984).
G. E. Forsythe, On the asymptotic directions of the $s$-dimensional optimum gradient method, Numer. Math, 11, № 1, 57 – 76 (1968), https://doi.org/10.1007/BF02165472 DOI: https://doi.org/10.1007/BF02165472
J. Liesen, The Forsythe conjecture, XXI Householder Symp. Numer. Linear Algebra. Book Abstracts, June 14-19, 249 – 250 (2020).
A. F. Zabolotskaia, Asymptotycheskoe povedenye s-shahovoho metoda skoreisheho spuska v hylbertovom prostranstve, Zhurn. vychyslyt. matematyky y mat. fyzyky,19, № 1, 228 – 232 (1979).
P. F. Zhuk, Asymptotycheskye svoistva $s$-shahovoho metoda skoreisheho spuska, Zhurn. vыchyslyt. matematyky y mat. fyzyky,22, № 2, 269 – 279 (1982).
P. F. Zhuk, L. N. Bondarenko, Ob odnoi hypoteze Dzh. Forsaita, Mat. sb.,121 (163), № 4 (8), 435 – 453 (1983).
P. F. Zhuk, Asymptotycheskoe povedenye $s$-shahovoho metoda nayskoreisheho spuska v zadachakh na sobstvennye znachenyia v hylbertovom prostranstve, Mat. sb., 184, № 12, 87 – 122 (1993).
P. F. Zhuk, Asymptotycheskoe povedenye $s$-shahovoho metoda nayskoreisheho spuska pry mynymyzatsyy kvadratychnoho funktsyonala v hylbertovom prostranstve, Zhurn. vychyslyt. matematyky y mat. fyzyky, 35, № 2, 163 – 177 (1995).
L. Pronzato, H. P. Wynn, A. Zhigljavsky, A dynamical-system analysis of the optimum $s$-gradient algorithm, Optimal Design and Related Areas in Optimization and Statistics, Springer, New York (2009), p. 39 – 80, https://doi.org/10.1007/978-0-387-79936-0_3 DOI: https://doi.org/10.1007/978-0-387-79936-0_3
L. Pronzato, A. Zhigljavsky, Gradient algorithms for quadratic optimization with fast convergence rates, Comput. Optim. and Appl., 50, 597 – 617 (2011), https://doi.org/10.1007/s10589-010-9319-5 DOI: https://doi.org/10.1007/s10589-010-9319-5
R. De Asmundis, D. Di Serafino, F. Riccio, G. Toraldo, On spectral properties of steepest descent methods, IMA J. Numer. Anal., 33, № 4, 1416 – 1435 (2013), https://doi.org/10.1093/imanum/drs056 DOI: https://doi.org/10.1093/imanum/drs056
Y. Huang, Y. H. Dai, X. W. Liu, H. Zhang, Gradient methods exploiting spectral properties, Optim. Methods and Software, 35, № 4, 681 – 705 (2020), https://doi.org/10.1080/10556788.2020.1727476 DOI: https://doi.org/10.1080/10556788.2020.1727476
K. van den Doel, U. Ascher, The chaotic nature of faster gradient descent methods, J. Sci. Comput., 51, 560 – 581 (2012), https://doi.org/10.1007/s10915-011-9521-3 DOI: https://doi.org/10.1007/s10915-011-9521-3
L. N. Bondarenko, P. F. Zhuk, Kombynyrovannye yteratsyonnye metody varyatsyonnoho typa, Zhurn. vychyslyt. matematyky y mat. fyzyky, 28, № 9, 1283 – 1296 (1988).
P. F. Zhuk, A. A. Musyna, Asymptotycheskaia skorost skhodymosty dvukhsloinoho yteratsyonnoho metoda varyatsyonnoho typa, Ukr. mat. zhurn., 12, 1622 – 1635 (2013).
P. F. Zhuk, Oblast dyferentsiiovanosti asymptotychnoi shvydkosti zbizhnosti metodu naishvydshoho spusku, Matematychni problemy mekhaniky ta obchysliuvalnoi matematyky, 11, № 4, 102 – 110 (2014).
P. F. Zhuk, A. A. Musyna, Ob operatore perekhoda metoda nayskoreisheho spuska, Mat. modelyrovanye, 8, 65 – 80 (2014).
V. S. Koziakyn, M. A. Krasnoselskyi, O neskolkykh zadachakh, sviazannykh s metodom mynymalnykh neviazok, Zhurn. vychyslyt. matematyky y mat. fyzyky,19, № 2, 508 – 510 (1979).
V. P. Mikhaĭlov, Дифференциальные уравнения в частных производных [Partial differential equations], Izdat. ``Nauka'', Moscow, (1976).
Copyright (c) 2022 Петро Федорович Жук
This work is licensed under a Creative Commons Attribution 4.0 International License.
