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

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

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

Некоторые итерационные методы , сводящиеся к методу Ньютона, такие как последовательное квадратичное программирование , также можно считать квазиньютоновскими методами.

Поиск нулей: нахождение корня

Метод Ньютона для нахождения нулей функции нескольких переменных задается формулой , где — левая обратная матрица Якоби для , вычисленная для . ${\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 Octavefsolve использует в своей работе разновидность BFGS с расширениями доверенных областей .
• Научная библиотека 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 Optimization Toolbox функция fminuncиспользует (помимо других методов) квазиньютоновский метод BFGS . ^[12] Многие из ограниченных методов Optimization toolbox используют BFGS и вариант L-BFGS . ^[13]

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

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

Ссылки

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

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

• Bonnans, JF; Gilbert, J. Ch.; Lemaréchal, C .; Sagastizábal, CA (2006). Численная оптимизация: теоретические и численные аспекты (второе издание). Springer. ISBN 3-540-35445-X.
• Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN 978-0-471-91547-8.
• Нокедаль, Хорхе; Райт, Стивен Дж. (1999). «Квазиньютоновские методы». Численная оптимизация . Нью-Йорк: Springer. С. 192–221. ISBN 0-387-98793-2.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 10.9. Квазиньютоновские или переменные метрические методы в многомерных пространствах". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.
• Scales, LE (1985). Введение в нелинейную оптимизацию. Нью-Йорк: MacMillan. С. 84–106. ISBN 0-333-32552-4.