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

Квазиньютоновские методы считаются наиболее эффективными алгоритмами для безусловной минимизации гладких функций. Основная идея этих алгоритмов заключается в аппроксимации стандартного метода Ньютона с помощью замены точного гессиана на его аппроксимацию, обновляемую в итерациях по специальным формулам (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)