А. О. Родоманов "Новые результаты о сверхлинейной сходимости квазиньютоновских методов"

Общероссийский семинар по оптимизации 17 июня 2020 г. 17:30, Москва, Онлайн Новые результаты о сверхлинейной сходимости квазиньютоновских методов А. О. Родоманов Аннотация: Квазиньютоновские методы считаются наиболее эффективными алгоритмами для безусловной минимизации гладких функций. Основная идея этих алгоритмов заключается в аппроксимации стандартного метода Ньютона с помощью замены точного гессиана на его аппроксимацию, обновляемую в итерациях по специальным формулам (BFGS, DFP, SR1 и т.д.), включающим в себя только градиенты целевой функции. Однако, несмотря на их практическую эффективность, с точки зрения теории про квазиньютоновские методы известно крайне мало. Главным результатом является асимптотическая локальная сверхлинейная сходимость, установленная еще в начале 1970-х годов. Тем не менее, никаких явных оценок скорости этой сверхлинейной сходимости и самого момента ее наступления до последнего времени известно не было. В докладе будут представлены новые результаты, которые решают эту проблему. Доклад основан на следующем цикле работ: New Results on Superlinear Convergence of Classical Quasi-Newton Methods (A. Rodomanov, Y. Nesterov) Rates of Superlinear Convergence for Classical Quasi-Newton Methods (A. Rodomanov, Y. Nesterov) Greedy Quasi-Newton Methods with Explicit Superlinear Convergence (A. Rodomanov, Y. Nesterov)