Квазиньютоновский метод

Алгоритм оптимизации

Квазиньютоновские методы — это методы, используемые для поиска нулей или локальных максимумов и минимумов функций в качестве альтернативы методу Ньютона. Их можно использовать, если якобиан или гессиан недоступны или слишком дороги для вычисления на каждой итерации. «Полный» метод Ньютона требует якобиана для поиска нулей или гессиана для поиска экстремумов. Некоторые итеративные методы , сводящиеся к методу Ньютона, такие как SLSQP , можно считать квазиньютоновскими.

Поиск нулей: поиск корня

Метод Ньютона для поиска нулей функции многих переменных задается формулой , где – левая обратная матрица Якобиана , оцененная для . ${\displaystyle g}$ ${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$ ${\displaystyle [J_{g}(x_{n})]^{-1}}$ ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle g}$ ${\displaystyle x_{n}}$

Строго говоря, любой метод, заменяющий точный якобиан приближением, является квазиньютоновским методом. ^[1] Например, простым примером является метод хорды (где заменяется на для всех итераций). Приведенные ниже методы оптимизации относятся к важному подклассу квазиньютоновских методов — секущим методам. ^[2] ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle J_{g}(x_{n})}$ ${\displaystyle J_{g}(x_{0})}$

Использование методов, разработанных для поиска экстремумов, для поиска нулей не всегда является хорошей идеей, поскольку большинство методов, используемых для поиска экстремумов, требуют, чтобы используемая матрица была симметричной. Хотя это справедливо в контексте поиска экстремумов, оно редко справедливо при поиске нулей. «Хороший» и «плохой» методы Бройдена — это два метода, обычно используемые для поиска экстремумов, которые также можно применять для поиска нулей. Другими методами, которые можно использовать, являются метод обновления столбцов, метод обратного обновления столбцов, метод квазиньютоновских наименьших квадратов и обратный метод квазиньютоновских наименьших квадратов.

Совсем недавно квазиньютоновские методы стали применяться для поиска решения нескольких связанных систем уравнений (например, задач взаимодействия жидкости и структуры или задач взаимодействия в физике). Они позволяют найти решение путем решения каждой составляющей системы отдельно (что проще, чем глобальная система) циклическим итеративным способом, пока не будет найдено решение глобальной системы. ^{[2] [3]}

Поиск экстремумов: оптимизация

Поиск минимума или максимума скалярной функции есть не что иное, как поиск нулей градиента этой функции. Следовательно, для нахождения экстремумов функции можно легко применить квазиньютоновские методы. Другими словами, если – градиент , то поиск нулей вектор-функции соответствует поиску экстремумов скалярной функции ; нынешний якобиан становится гессианом России . Основное отличие состоит в том, что матрица Гессе является симметричной матрицей , в отличие от якобиана при поиске нулей. Большинство квазиньютоновских методов, используемых при оптимизации, используют это свойство. ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$

В оптимизации квазиньютоновские методы (частный случай переменных-метрических методов ) — это алгоритмы поиска локальных максимумов и минимумов функций . Квазиньютоновские методы основаны на методе Ньютона для поиска стационарной точки функции, где градиент равен 0. Метод Ньютона предполагает, что функция может быть локально аппроксимирована как квадратичная в области вокруг оптимума, и использует первый и второй методы. производные, чтобы найти точку покоя. В более высоких измерениях метод Ньютона использует градиент и матрицу Гессе вторых производных функции, подлежащей минимизации.

В квазиньютоновских методах нет необходимости вычислять матрицу Гессе. Вместо этого гессиан обновляется путем анализа последовательных векторов градиента. Квазиньютоновские методы представляют собой обобщение метода секущего для поиска корня первой производной для многомерных задач. В многомерных измерениях секущее уравнение недостаточно определено , а квазиньютоновские методы различаются тем, как они ограничивают решение, обычно путем добавления простого обновления низкого ранга к текущей оценке гессиана.

Первый алгоритм квазиньютона был предложен Уильямом К. Дэвидоном , физиком, работающим в Аргоннской национальной лаборатории . Он разработал первый квазиньютоновский алгоритм в 1959 году: формулу обновления DFP , которая позже была популяризирована Флетчером и Пауэллом в 1963 году, но сегодня редко используется. Наиболее распространенными квазиньютоновскими алгоритмами в настоящее время являются формула SR1 (для «симметричного ранга один»), метод BHHH , широко распространенный метод BFGS (предложенный независимо Бройденом, Флетчером, Гольдфарбом и Шэнно в 1970 году) и его низкий уровень. -расширение памяти L-BFGS . Класс Бройдена представляет собой линейную комбинацию методов DFP и BFGS.

Формула SR1 не гарантирует сохранение положительной определенности матрицы обновления и может использоваться для неопределенных задач. Метод Бройдена не требует, чтобы матрица обновления была симметричной, и используется для поиска корня общей системы уравнений (а не градиента) путем обновления якобиана ( а не гессиана).

Одним из главных преимуществ квазиньютоновских методов перед методом Ньютона является то, что матрицу Гессе (или, в случае квазиньютоновских методов, ее аппроксимацию) не нужно инвертировать. Метод Ньютона и его производные, такие как методы внутренней точки , требуют инвертирования гессиана, что обычно реализуется путем решения системы линейных уравнений и часто является довольно дорогостоящим. Напротив, квазиньютоновские методы обычно дают оценку напрямую. ${\displaystyle B}$ ${\displaystyle B^{-1}}$

Как и в методе Ньютона , для нахождения минимума функции используется приближение второго порядка . Ряд Тейлора вокруг итерации равен ${\displaystyle f(x)}$ ${\displaystyle f(x)}$

${\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,}$

где ( ) — градиент и аппроксимация матрицы Гессе . ^[4] Градиент этого приближения (по отношению к ) равен ${\displaystyle \nabla f}$ ${\displaystyle B}$ ${\displaystyle \Delta x}$

${\displaystyle \nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,}$

и установка этого градиента на ноль (что является целью оптимизации) обеспечивает шаг Ньютона:

${\displaystyle \Delta x=-B^{-1}\nabla f(x_{k}).}$

Приближение Гессе выбрано таким образом, чтобы удовлетворить ${\displaystyle B}$

${\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,}$

которое называется уравнением секущего (ряд Тейлора самого градиента). Недоопределен более чем в одном измерении . В одном измерении решение и применение шага Ньютона с обновленным значением эквивалентно методу секущего . Различные квазиньютоновские методы различаются выбором решения секущего уравнения (в одном измерении все варианты эквивалентны). Большинство методов (но с исключениями, такими как метод Бройдена ) ищут симметричное решение ( ); кроме того, перечисленные ниже варианты можно мотивировать поиском обновления , максимально близкого к некоторой норме ; то есть , где – некоторая положительно определенная матрица , определяющая норму. Приблизительного начального значения часто бывает достаточно для достижения быстрой сходимости, хотя какой-либо общей стратегии не существует . ^[5] Обратите внимание, что это значение должно быть положительно-определенным. Неизвестное обновляется с применением шага Ньютона, рассчитанного с использованием текущей приближенной матрицы Гессе : ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle B^{T}=B}$ ${\displaystyle B_{k+1}}$ ${\displaystyle B_{k}}$ ${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$ ${\displaystyle V}$ ${\displaystyle B_{0}=\beta I}$ ${\displaystyle \beta }$ ${\displaystyle B_{0}}$ ${\displaystyle x_{k}}$ ${\displaystyle B_{k}}$

• ${\displaystyle \Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})}$, выбранный так, чтобы удовлетворять условиям Вульфа ; ${\displaystyle \alpha }$
• ${\displaystyle x_{k+1}=x_{k}+\Delta x_{k}}$;
• Градиент, рассчитанный в новой точке , и ${\displaystyle \nabla f(x_{k+1})}$

${\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}$

используется для обновления приблизительного гессиана или непосредственно его обратного значения с использованием формулы Шермана-Моррисона . ${\displaystyle B_{k+1}}$ ${\displaystyle H_{k+1}=B_{k+1}^{-1}}$

• Ключевым свойством обновлений BFGS и DFP является то, что если оно положительно определенное и выбрано так, чтобы удовлетворять условиям Вульфа, то оно также является положительно определенным. ${\displaystyle B_{k}}$ ${\displaystyle \alpha _{k}}$ ${\displaystyle B_{k+1}}$

Наиболее популярные формулы обновления:

Другими методами являются метод Пирсона, метод Маккормика, метод Пауэлла, симметричный Бройден (PSB) и метод Гринштадта. ^[2]

Связь с инверсией матрицы

Когда является выпуклой квадратичной функцией с положительно определенным гессианом , можно было бы ожидать, что матрицы, сгенерированные методом квазиньютона, сходятся к обратному гессиану . Это действительно так для класса квазиньютоновских методов, основанных на обновлениях с наименьшими изменениями. ^[6] ${\displaystyle f}$ ${\displaystyle B}$ ${\displaystyle H_{k}}$ ${\displaystyle H=B^{-1}}$

Известные реализации

Реализации квазиньютоновских методов доступны во многих языках программирования.

Известные реализации с открытым исходным кодом включают:

• GNU Octave использует в своих функциях разновидность BFGS fsolveс расширениями доверенных регионов .
• Научная библиотека GNU реализует алгоритм Бройдена-Флетчера-Гольдфарба-Шанно ( BFGS ).
• ALGLIB реализует (L)BFGS на C++ и C#.
• optimПодпрограмма оптимизатора общего назначения R использует метод BFGS , используя method="BFGS". ^[7]
• В Scipy .optimize есть fmin_bfgs. В расширении SciPy для Python функция scipy.optimize.minimizeвключает, среди прочих методов, реализацию BFGS . ^[8]

Известные собственные реализации включают:

• Mathematica включает квазиньютоновские решатели. ^[9]
• Библиотека NAG содержит несколько процедур ^[10] для минимизации и максимизации функции ^[11] , использующих квазиньютоновские алгоритмы.
• В MATLAB's Optimization Toolbox функция fminuncиспользует (среди других методов) квазиньютоновский метод BFGS . ^[12] Многие из ограниченных методов набора инструментов оптимизации используют BFGS и вариант L-BFGS . ^[13] <

Смотрите также

• метод БФГС
  • Л-БФГС
  • СОВА-QN
• метод Бройдена
• Формула обновления DFP
• метод Ньютона
• Метод Ньютона в оптимизации
• Формула SR1

Рекомендации

1. Бройден, CG (1972). «Квазиньютоновские методы». В Мюррей, В. (ред.). Численные методы неограниченной оптимизации . Лондон: Академическая пресса. стр. 87–106. ISBN 0-12-512250-0.
2. Хелтерман, Роб (2009). «Аналитическое исследование квазиньютоновского метода наименьших квадратов для задач взаимодействия». Кандидатская диссертация, Гентский университет . Проверено 14 августа 2014 г.
3. Роб Хелтерман; Дирк Ван Эстер; Даан Верлейен (2015). «Ускорение решения физической модели внутри токамака с использованием метода (обратного) обновления столбца». Журнал вычислительной и прикладной математики . 279 : 133–144. дои : 10.1016/j.cam.2014.11.005 .
4. «Введение в теорему Тейлора для функций многих переменных - Math Insight». mathinsight.org . Проверено 11 ноября 2021 г.
5. Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация . Нью-Йорк: Спрингер. стр. 142. ISBN 0-387-98793-2.
6. Роберт Мэнсел Гауэр; Петр Рихтарик (2015). «Рандомизированные квазиньютоновские обновления представляют собой алгоритмы линейно сходящейся инверсии матриц». arXiv : 1602.01768 [math.NA].
7. «Оптимальная функция — RDocumentation» . www.rdocumentation.org . Проверено 21 февраля 2022 г.
8. «Scipy.optimize.minimize — Руководство по SciPy v1.7.1» .
9. «Неограниченная оптимизация: методы локальной минимизации — документация на языке Wolfram». ссылка.wolfram.com . Проверено 21 февраля 2022 г.
10. Группа числовых алгоритмов. «Указатель ключевых слов: Квазиньютон». Руководство по библиотеке НАГ, Марк 23 . Проверено 9 февраля 2012 г.
11. Группа числовых алгоритмов. «E04 – Минимизация или максимизация функции» (PDF) . Руководство по библиотеке НАГ, Марк 23 . Проверено 9 февраля 2012 г.
12. «Найдите минимум неограниченной функции многих переменных - MATLAB fminunc» .
13. «Алгоритмы нелинейной оптимизации с ограничениями - MATLAB и Simulink» . www.mathworks.com . Проверено 21 февраля 2022 г.

дальнейшее чтение

• Боннан, JF; Гилберт, Дж. Ч.; Лемарешаль, К. ; Сагастисабал, Калифорния (2006 г.). Численная оптимизация: теоретические и численные аспекты (второе изд.). Спрингер. ISBN 3-540-35445-Х.
• Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN. 978-0-471-91547-8.
• Носедаль, Хорхе; Райт, Стивен Дж. (1999). «Квазиньютоновские методы». Численная оптимизация . Нью-Йорк: Спрингер. стр. 192–221. ISBN 0-387-98793-2.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 10.9. Квазиньютоновские методы или методы переменной метрики в многомерных измерениях». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
• Весы, LE (1985). Введение в нелинейную оптимизацию. Нью-Йорк: Макмиллан. стр. 84–106. ISBN 0-333-32552-4.