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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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,

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

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

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

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

Гессенское приближение $B$ выбран для удовлетворения

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

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

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

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

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

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

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

Метод	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
БФГС	$B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}$	$\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$
Бройден	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{\mathrm {T} }H_{k}}{\Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}$
Семья Бройден	$(1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]$
ДФП	$\left(I-{\frac {y_{k}\,\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}$
СР1	$B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}$

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

[1] Бройден, CG (1972). «Квазиньютоновские методы». В Мюррей, В. (ред.). Численные методы неограниченной оптимизации . Лондон: Академическая пресса. стр. 87–106. ISBN 0-12-512250-0 .

[Haelterman-2] Jump up to: ^а ^б ^с Хелтерман, Роб (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 .

[Gower_and_Richtarik-6] Роберт Мэнсел Гауэр; Петр Рихтарик (2015). «Рандомизированные квазиньютоновские обновления представляют собой алгоритмы линейно сходящейся инверсии матриц». arXiv : 1602.01768 [ мат.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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]