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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Алгоритм Бройдена – Флетчера – Гольдфарба – Шанно»  -  новости  · газеты  · книги  · ученый  · JSTOR ( март 2016 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

В численном оптимизации , то Бройдена-Флетчера-Гольдфарб-Shanno ( BFGS ) Алгоритм представляет собой итерационный метод для решения безусловной нелинейной оптимизации проблемы. ^[1] Как и связанного метода Давидона-Fletcher-Powell , BFGS определяет направление спуска по предобусловливание на градиент с информацией кривизны. Он делает это, постепенно улучшая приближение к матрицам Гесса в функции потерь, полученные только из оценок градиента (или приближенных оценок градиента) с помощью обобщенного метода секущих . ^[2]

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

Алгоритм назван в честь Чарльза Джорджа Бройдена , Роджера Флетчера , Дональда Гольдфарба и Дэвида Шенно . ^{[4] [5] [6] [7]}

Обоснование [ править ]

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

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

Направление поиска р _к на стадии к даются решением аналога уравнения Ньютона:

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

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

Квазиньютоновское условие, накладываемое на обновление, есть${\ displaystyle B_ {k}}$

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

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

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

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

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

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

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

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

${\displaystyle 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}}}.}$

Алгоритм [ править ]

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

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

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

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

${\displaystyle 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}}}.}$

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

${\displaystyle 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}}}.}$

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

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

• Программное обеспечение для крупномасштабной нелинейной оптимизации Artelys Knitro реализует, среди прочего, алгоритмы BFGS и L-BFGS.
• В GSL реализует BFGS в gsl_multimin_fdfminimizer_vector_bfgs2. ^[10]
• В MATLAB Optimization Toolbox функция fminunc ^[11] использует BFGS с кубическим линейным поиском, когда размер задачи установлен на «средний масштаб». ^[12]
• В R алгоритм BFGS (и версия L-BFGS-B, которая допускает ограничения бокса) реализованы как опция базовой функции optim (). ^[13]
• В SciPy функция scipy.optimize.fmin_bfgs реализует BFGS. ^[14] Также возможно запустить BFGS с использованием любого из алгоритмов L-BFGS , установив для параметра L очень большое число.

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

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

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

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