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

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

Поиск нулей: поиск корня [ править ]

Метод Ньютона найти нули функции нескольких переменных задается , где есть левый обратный из матрицы Якоби из оценивали .${\ 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,}$

которое называется секущим уравнением (ряд Тейлора самого градиента). В более чем в одном измерении имеет недоопределенный . В одном измерении решение и применение шага Ньютона с обновленным значением эквивалентно методу секанса . Различные квазиньютоновские методы различаются выбором решения секущего уравнения (в одном измерении все варианты эквивалентны). Большинство методов (но с исключениями, такими как метод Бройдена ) ищут симметричное решение ( ); кроме того, варианты, перечисленные ниже, могут быть мотивированы поиском обновления , максимально приближенного к некоторой норме ; то есть , где${\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}$- некоторая положительно определенная матрица , определяющая норму. Приблизительного начального значения часто бывает достаточно для достижения быстрой сходимости, хотя общей стратегии выбора нет . ^[5] Обратите внимание, что это должно быть положительно-определенным. Неизвестное обновляется с применением шага Ньютона, рассчитанного с использованием текущей приближенной матрицы Гессе :${\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}}$

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

Методика	${\displaystyle \displaystyle B_{k+1}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
BFGS	${\displaystyle 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}}}}$	${\displaystyle \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}}}}$
Broyden	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }}$	${\displaystyle 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}}}}$
Семья Бройден	${\displaystyle (1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]}$
DFP	${\displaystyle \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}}}}$	${\displaystyle 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}}}}$
SR1	${\displaystyle 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}}}}$	${\displaystyle 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]

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

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

Известные реализации [ править ]

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

• GNU Octave в своей fsolveфункции использует форму BFGS с расширениями доверенной области .
• Mathematica включает в себя квазиньютоновские решатели. ^[7]
• NAG библиотека содержит несколько подпрограмм ^[8] для минимизации или максимизации функции ^[9] , которые используют алгоритмов квазиньютоновских.
• В MATLAB в Optimization Toolbox , то fminuncфункция использует (среди других методов) BFGS квазиньютоновский метод. ^[10] Многие методы с ограничениями из набора инструментов Оптимизация используют BFGS и вариант L-BFGS . ^[11]
• R «ы optimобщего назначения подпрограмма оптимизатор использует BFGS метод с помощью method="BFGS". ^[12]
• Scipy .optimize имеет fmin_bfgs. В SciPy расширение Python , то scipy.optimize.minimizeфункция включает в себя, наряду с другими методами, в BFGS реализации. ^[13]

См. Также [ править ]

• Метод BFGS
  • L-BFGS
  • OWL-QN
• Метод Бройдена
• Формула обновления DFP
• Метод Ньютона
• Метод Ньютона в оптимизации
• Формула SR1

Ссылки [ править ]

Дальнейшее чтение [ править ]

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