Алгоритм Бройдена–Флетчера–Гольдфарба–Шенно

«БФГС» перенаправляется сюда. Чтобы узнать о канадской хардкор-панк-группе, см. Bunchofuckingoofs .

В числовой оптимизации Бройдена -Флетчера-Гольдфарба-Шанно ( BFGS ) алгоритм представляет собой итерационный метод решения нелинейной оптимизации без ограничений. задач родственный метод Дэвидона-Флетчера-Пауэлла , BFGS определяет направление спуска , предварительно определяя градиент Как и с помощью информации о кривизне. Это достигается путем постепенного улучшения аппроксимации матрицы Гессе функции потерь , полученной только из оценок градиента (или приблизительных оценок градиента) с помощью обобщенного метода секущих .

Поскольку обновления матрицы кривизны BFGS не требуют инверсии матрицы , ее вычислительная сложность составляет всего лишь ${\mathcal {O}}(n^{2})$, по сравнению с ${\mathcal {O}}(n^{3})$ в методе Ньютона . Также широко используется L-BFGS , версия BFGS с ограниченной памятью, которая особенно подходит для задач с очень большим количеством переменных (например, >1000). Вариант BFGS-B обрабатывает простые ограничения блока.

Алгоритм назван в честь Чарльза Джорджа Бройдена , Роджера Флетчера , Дональда Гольдфарба и Дэвида Шенно .

Обоснование

Задача оптимизации состоит в том, чтобы минимизировать $f(\mathbf {x} )$, где $\mathbf {x}$ является вектором в $\mathbb {R} ^{n}$, и $f$ является дифференцируемой скалярной функцией. Нет никаких ограничений на значения, которые $\mathbf {x}$ могу взять.

Алгоритм начинается с начальной оценки $\mathbf {x} _{0}$ для оптимального значения и продолжается итеративно, чтобы получить лучшую оценку на каждом этапе.

Направление поиска p _k на этапе k задается решением аналога уравнения Ньютона:

$B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k}),$

где $B_{k}$ является приближением к матрице Гессе при $\mathbf {x} _{k}$, который обновляется итеративно на каждом этапе, и $\nabla f(\mathbf {x} _{k})$ — градиент функции, оцененной в точке x _k . в Затем используется поиск линии направлении p _k для поиска следующей точки x _{k +1} путем минимизации $f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})$ над скаляром $\gamma >0.$

Условие квазиньютона, налагаемое на обновление $B_{k}$ является

$B_{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k})=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k}).$

Позволять $\mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})$ и $\mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}$, затем $B_{k+1}$ удовлетворяет

$B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}$,

что является секущим уравнением.

Условие кривизны $\mathbf {s} _{k}^{\top }\mathbf {y} _{k}>0$ должен быть удовлетворен за $B_{k+1}$ быть положительно определенным, что можно проверить, предварительно умножив уравнение секущего на $\mathbf {s} _{k}^{T}$. Если функция не является сильно выпуклой , то условие должно быть выполнено явно, например, путем нахождения точки x _{k +1,} удовлетворяющей условиям Вульфа , которые влекут за собой условие кривизны, с использованием поиска по прямой.

Вместо того, чтобы требовать полную матрицу Гессе в точке $\mathbf {x} _{k+1}$ быть вычислено как $B_{k+1}$, приближенный гессиан на этапе k обновляется добавлением двух матриц:

$B_{k+1}=B_{k}+U_{k}+V_{k}.$

Оба $U_{k}$ и $V_{k}$ являются симметричными матрицами первого ранга, но их сумма представляет собой матрицу обновления второго ранга. Матрица обновления BFGS и DFP отличается от своей предшественницы матрицей второго ранга. Другой более простой метод ранга один известен как симметричный метод ранга один , который не гарантирует положительную определенность . Для сохранения симметрии и положительной определенности $B_{k+1}$, форму обновления можно выбрать как $B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }$. Наложив условие секущего, $B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}$. Выбор $\mathbf {u} =\mathbf {y} _{k}$ и $\mathbf {v} =B_{k}\mathbf {s} _{k}$, мы можем получить:

$\alpha ={\frac {1}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}},$

$\beta =-{\frac {1}{\mathbf {s} _{k}^{T}B_{k}\mathbf {s} _{k}}}.$

Наконец, мы заменяем $\alpha$ и $\beta$ в $B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }$ и получить уравнение обновления $B_{k+1}$:

$B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}.$

Алгоритм

Рассмотрим следующую задачу неограниченной оптимизации.

$${\begin{aligned}{\underset {\mathbf {x} \in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(\mathbf {x} ),\end{aligned}}$$

где $f:\mathbb {R} ^{n}\to \mathbb {R}$ является нелинейной целевой функцией.

По первоначальному предположению $\mathbf {x} _{0}\in \mathbb {R} ^{n}$ и первоначальное предположение матрицы Гессе $B_{0}\in \mathbb {R} ^{n\times n}$ следующие шаги повторяются как $\mathbf {x} _{k}$ сходится к решению:

1. Получить направление $\mathbf {p} _{k}$ решив $B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$.
2. Выполните одномерную оптимизацию ( линейный поиск ), чтобы найти приемлемый размер шага. $\alpha _{k}$ в направлении, найденном на первом шаге. Если производится точный поиск строки, то $\alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ . На практике обычно бывает достаточно неточного поиска по строке с приемлемым значением. $\alpha _{k}$ удовлетворяющие условиям Вульфа .
3. Набор $\mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}$ и обновить $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}$.
4. $\mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$.
5. $B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}$.

Сходимость можно определить, наблюдая за нормой градиента; учитывая некоторые $\epsilon >0$, можно остановить алгоритм, когда $||\nabla f(\mathbf {x} _{k})||\leq \epsilon .$ Если $B_{0}$ инициализируется с помощью $B_{0}=I$, первый шаг будет эквивалентен градиентному спуску , но дальнейшие шаги все более уточняются за счет $B_{k}$, приближение к гессиану.

Первый шаг алгоритма осуществляется с использованием обратной матрицы $B_{k}$, который можно эффективно получить, применив формулу Шермана–Моррисона к шагу 5 алгоритма, давая

$B_{k+1}^{-1}=\left(I-{\frac {\mathbf {s} _{k}\mathbf {y} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)B_{k}^{-1}\left(I-{\frac {\mathbf {y} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)+{\frac {\mathbf {s} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}.$

Это можно эффективно вычислить без временных матриц, учитывая, что $B_{k}^{-1}$ симметричен,и это $\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k}$ и $\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}$ являются скалярами, используя такое расширение, как

$B_{k+1}^{-1}=B_{k}^{-1}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {B_{k}^{-1}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}.$

Следовательно, чтобы избежать инверсии матрицы, обратную гессиану: вместо самого гессиана можно аппроксимировать $H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}.$

По первоначальному предположению $\mathbf {x} _{0}$ и приближенная обращенная матрица Гессе $H_{0}$ следующие шаги повторяются как $\mathbf {x} _{k}$ сходится к решению:

1. Получить направление $\mathbf {p} _{k}$ решив $\mathbf {p} _{k}=-H_{k}\nabla f(\mathbf {x} _{k})$.
2. Выполните одномерную оптимизацию ( линейный поиск ), чтобы найти приемлемый размер шага. $\alpha _{k}$ в направлении, найденном на первом шаге. Если производится точный поиск строки, то $\alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ . На практике обычно бывает достаточно неточного поиска по строке с приемлемым значением. $\alpha _{k}$ удовлетворяющие условиям Вульфа .
3. Набор $\mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}$ и обновить $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}$.
4. $\mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$.
5. $H_{k+1}=H_{k}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }H_{k}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {H_{k}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }H_{k}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}$.

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

Дальнейшие разработки

Формула обновления BFGS во многом зависит от кривизны. $\mathbf {s} _{k}^{\top }\mathbf {y} _{k}$ строго положительное и отделенное от нуля.Это условие выполняется, когда мы выполняем поиск по прямой с условиями Вульфа на выпуклой цели.Однако некоторые реальные приложения (например, методы последовательного квадратичного программирования) обычно создают отрицательную или почти нулевую кривизну.Это может произойти при оптимизации невыпуклой цели или при использовании подхода доверительной области вместо линейного поиска.Также возможно получение ложных значений из-за шума в цели.

В таких случаях можно использовать одно из так называемых демпфированных обновлений BFGS (см. ), которые изменяют $\mathbf {s} _{k}$ и/или $\mathbf {y} _{k}$ чтобы получить более надежное обновление.

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

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

• ALGLIB реализует BFGS и его версию с ограниченной памятью на C++ и C#.
• GNU Octave использует разновидность BFGS в своей fsolve функция с расширениями доверительного региона .
• GSL . реализует BFGS как gsl_multimin_fdfminimizer_vector_bfgs2
• В R алгоритм BFGS (и версия L-BFGS-B, допускающая ограничения блоков) реализован как опция базовой функции optim().
• В SciPy функция scipy.optimize.fmin_bfgs реализует BFGS. Также возможно запустить BFGS, используя любой из алгоритмов L-BFGS , установив для параметра L очень большое число.
• В Julia пакет Optim.jl . реализует BFGS и L-BFGS в качестве опции решателя для функцииоптимизации() (среди других опций)

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

• Программное обеспечение для крупномасштабной нелинейной оптимизации Artelys Knitro реализует, среди прочего, алгоритмы BFGS и L-BFGS.
• В MATLAB Optimization Toolbox функция fminunc использует BFGS с поиском кубической линии, когда размер проблемы установлен на «средний масштаб».
• Mathematica включает BFGS.
• LS-DYNA также использует BFGS для решения неявных проблем.

См. также

• Алгоритм БХХХ
• Формула Дэвидона – Флетчера – Пауэлла
• Градиентный спуск
• Л-БФГС
• Алгоритм Левенберга – Марквардта
• Метод Нелдера-Мида
• Поиск по шаблону (оптимизация)
• Квазиньютоновские методы
• Симметричный первого ранга

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

• Авриэль, Мордекай (2003), Нелинейное программирование: анализ и методы , Dover Publishing, ISBN  978-0-486-43227-4
• Боннан, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастисабал, Клаудия А. (2006), «Ньютоновские методы», Численная оптимизация: теоретические и практические аспекты (второе изд.), Берлин: Springer, стр. 51–66, ISBN  3-540-35445-Х
• Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: John Wiley & Sons , ISBN  978-0-471-91547-8
• Люенбергер, Дэвид Г .; Йе, Инью (2008), Линейное и нелинейное программирование , Международная серия по исследованию операций и науке управления, том. 116 (Третье изд.), Нью-Йорк: Springer, стр. xiv+546, ISBN.  978-0-387-74502-2 , МР   2423726
• Келли, Коннектикут (1999), Итеративные методы оптимизации , Филадельфия: Общество промышленной и прикладной математики, стр. 71–86, ISBN.  0-89871-433-8