Алгоритм Бройдена – Флетчера – Гольдфарба – Шенно - Broyden–Fletcher–Goldfarb–Shanno algorithm

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

В числовой оптимизация, то Бройден – Флетчер – Гольдфарб – Шанно (BFGS) алгоритм является итерационный метод для решения неограниченных нелинейная оптимизация проблемы.^[1]

Метод BFGS относится к квазиньютоновские методы, класс оптимизация восхождения методы, которые ищут стационарный пункт функции (желательно дважды непрерывно дифференцируемой). Для таких проблем необходимое условие оптимальности это то градиент быть нулевым. Метод Ньютона и методы BFGS не гарантируют сходимость, если функция не имеет квадратичного Расширение Тейлора рядом с оптимальный. Однако BFGS может иметь приемлемую производительность даже для экземпляров неплавной оптимизации.^[2]

В Квазиньютоновские методы, то Матрица Гессе второй производные не вычисляется. Вместо этого матрица Гессе аппроксимируется с использованием обновлений, заданных оценками градиента (или приблизительными оценками градиента). Квазиньютоновские методы являются обобщениями секущий метод найти корень первой производной для многомерных задач. В многомерных задачах секущее уравнение не задает единственного решения, а квазиньютоновские методы различаются тем, как они ограничивают решение. Метод BFGS - один из самых популярных членов этого класса.^[3] Также широко используется L-BFGS, который представляет собой версию BFGS с ограниченным объемом памяти, которая особенно подходит для задач с очень большим количеством переменных (например,> 1000). Вариант BFGS-B обрабатывает простые ограничения коробки.^[4]

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

Обоснование

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

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

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

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

куда ${ displaystyle B_ {k}}$ является приближением к Матрица Гессе, который обновляется итеративно на каждом этапе, и ${ Displaystyle набла е ( mathbf {х} _ {к})}$ - градиент функции, вычисленной при Икс_k. А линейный поиск в направлении п_k затем используется для поиска следующей точки Икс_k+1 минимизируя ${ 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_ {к + 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}}$. Если функция не является сильно выпуклой, то условие должно выполняться явно.

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

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

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

${ 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 е ( mathbf {х})}$ обозначает минимизируемую целевую функцию. Сходимость можно проверить, наблюдая за нормой градиента, ${ Displaystyle || набла е ( mathbf {x} _ {k}) ||}$. Если ${ displaystyle B_ {0}}$инициализируется ${ displaystyle B_ {0} = I}$, первый шаг будет эквивалентен градиентный спуск, но дальнейшие шаги все более уточняются ${ displaystyle B_ {k}}$, приближение к гессиану.

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

${ Displaystyle B_ {к + 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_ {к + 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 может не сходиться к истинной матрице Гессе.^[10]

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

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

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

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

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

• Авриэль, Мардохей (2003), Нелинейное программирование: анализ и методы., Dover Publishing, ISBN  978-0-486-43227-4
• Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод; Сагастизабал, Клаудиа А. (2006), «Ньютоновские методы», Численная оптимизация: теоретические и практические аспекты (Второе изд.), Берлин: Springer, стр. 51–66, ISBN  3-540-35445-X
• Деннис, Дж. Э., мл.; Шнабель, Роберт Б. (1983), "Секущие методы безусловной минимизации", Численные методы безусловной оптимизации и нелинейных уравнений, Englewood Cliffs, NJ: Prentice-Hall, pp. 194–215, ISBN  0-13-627216-9
• Флетчер, Роджер (1987), Практические методы оптимизации (2-е изд.), Нью-Йорк: Джон Уайли и сыновья, 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
• Нокедаль, Хорхе; Райт, Стивен Дж. (2006), Численная оптимизация (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-0-387-30303-1