Множина рівня асимптотичної швидкості збіжності методу найшвидшого спуску

П. Ф. Жук

doi:10.37863/umzh.v74i2.6885

П. Ф. Жук Нац. авiац. ун-т, Київ

DOI: https://doi.org/10.37863/umzh.v74i2.6885

Ключові слова: швидкість збіжності, асимптотична поведінка, метод найшвидшого спуску, множина рівня

Анотація

УДК 519.61

Асимптотична швидкiсть збiжностi методу найшвидшого спуску розглядається як функцiя вiд початкового наближення. У данiй роботi вивчається множина рiвня цiєї швидкостi, тобто множина початкових наближень, для яких вона має задане значення. Запропоновано спосiб побудови цiєї множини i знайдено її компоненти зв’язностi.

Посилання

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).