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

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

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

Метод Ньютона найти нули функции ${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}}$.

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

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

Совсем недавно квазиньютоновские методы стали применяться для поиска решения множественных связанных систем уравнений (например, задач взаимодействия жидкость-структура или задач взаимодействия в физике). Они позволяют найти решение, решая каждую составляющую систему отдельно (что проще, чем глобальная система) циклическим, итеративным способом, пока не будет найдено решение глобальной системы.^[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})+abla f(x_{k})^{mathrm {T} },Delta x+{frac {1}{2}}Delta x^{mathrm {T} }B,Delta x,}$

где (${displaystyle abla f}$) это градиент, и ${displaystyle B}$ приближение к Матрица Гессе^[4]. Градиент этого приближения (по ${displaystyle Delta x}$) является

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

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

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

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

${displaystyle abla f(x_{k}+Delta x)=abla 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}$ есть некоторые положительно определенная матрица что определяет норму. Примерное начальное значение ${displaystyle B_{0}=eta I}$ часто бывает достаточно для достижения быстрой сходимости, хотя нет общей стратегии выбора ${displaystyle eta }$ ^[5]. Обратите внимание, что ${displaystyle B_{0}}$ должно быть положительно-определенным. Неизвестный ${displaystyle x_{k}}$ обновляется с применением шага Ньютона, рассчитанного с использованием текущей приближенной матрицы Гессе ${displaystyle B_{k}}$:

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

${displaystyle y_{k}=abla f(x_{k+1})-abla 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}}}ight)H_{k}left(I-{frac {y_{k}Delta x_{k}^{mathrm {T} }}{y_{k}^{mathrm {T} }Delta x_{k}}}ight)+{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}^{ ext{BFGS}}+varphi _{k}B_{k+1}^{ ext{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}}}ight)B_{k}left(I-{frac {Delta x_{k}y_{k}^{mathrm {T} }}{y_{k}^{mathrm {T} },Delta x_{k}}}ight)+{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]

Связь с обращением матрицы

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

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

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

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

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

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

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

1. Бройден, К. Г. (1972). «Квазиньютоновские методы». В Мюррей, W. (ред.). Численные методы безусловной оптимизации. Лондон: Academic Press. С. 87–106. ISBN  0-12-512250-0.
2. Хельтерман, Роб (2009). «Аналитическое исследование квазиньютоновского метода наименьших квадратов для задач взаимодействия». Докторская диссертация, Гентский университет. Получено 2014-08-14.
3. Роб Хэлтерман, Дирк Ван Эстер, Даан Верлейен (2015). «Ускорение решения физической модели внутри токамака с помощью (обратного) метода обновления столбца». Журнал вычислительной и прикладной математики. 279: 133–144. Дои:10.1016 / j.cam.2014.11.005.
4. https://mathinsight.org/taylors_theorem_multivariable_introduction
5. Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация. Нью-Йорк: Спрингер. стр.142. ISBN  0-387-98793-2.
6. Роберт Мансел Гауэр; Питер Рихтарик (2015). «Рандомизированные квазиньютоновские обновления представляют собой алгоритмы обращения линейно сходящейся матрицы». arXiv:1602.01768 [math.NA ].
7. http://reference.wolfram.com/mathematica/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.html
8. Группа численных алгоритмов. "Указатель ключевых слов: квазиньютон". Руководство библиотеки NAG, Mark 23. Получено 2012-02-09.
9. Группа численных алгоритмов. «E04 - Минимизация или максимизация функции» (PDF). Руководство библиотеки NAG, Mark 23. Получено 2012-02-09.
10. http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html
11. http://www.mathworks.com/help/toolbox/optim/ug/brnoxzl.html
12. [1]
13. http://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

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

• Bonnans, J. F .; Gilbert, J. Ch .; Лемарешаль, К.; Сагастизабал, К.А. (2006). Численная оптимизация: теоретические и численные аспекты (Второе изд.). Springer. ISBN  3-540-35445-X.
• Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: Джон Уайли и сыновья, ISBN  978-0-471-91547-8.
• Нокедаль, Хорхе; Райт, Стивен Дж. (1999). «Квазиньютоновские методы». Численная оптимизация. Нью-Йорк: Спрингер. С. 192–221. ISBN  0-387-98793-2.
• Press, W. H .; Теукольский, С. А .; Vetterling, W. T .; Фланнери, Б. П. (2007). «Раздел 10.9. Квазиньютон или методы переменной метрики в многомерности». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
• Весы, Л. Э. (1985). Введение в нелинейную оптимизацию. Нью-Йорк: Макмиллан. С. 84–106. ISBN  0-333-32552-4.