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

редактировать

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

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

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

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

Содержание

1 Обоснование
2 Алгоритм
3 Известные реализации
4 См. Также
5 Ссылки
6 Дополнительная литература

Обоснование

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

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

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

B kpk = - ∇ f (xk), {\ displaystyle B_ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k}),}

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

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

Условие квазиньютона, наложенное на обновление $B k {\ displaystyle B_ {k}}$ $B_ {k}$ , равно

B k + 1 (xk + 1 - xk) знак равно ∇ е (xk + 1) - ∇ е (xk). {\ Displaystyle B_ {k + 1} (\ mathbf {x} _ {k + 1} - \ mathbf {x } _ {k}) = \ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k}).}

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

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

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

B k + 1 = B k + U k + В к. {\ displaystyle B_ {k + 1} = B_ {k} + U_ {k} + V_ {k}.}

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

И $U k {\ displaystyle U_ {k}}$ $U_ {k}$ , и $V k {\ displaystyle V_ {k}}$ $V_ {k}$ - симметричные матрицы первого ранга, но их сумма представляет собой матрицу обновления ранга два. Матрицы обновления BFGS и DFP отличаются от своего предшественника матрицей второго ранга. Другой более простой метод ранга один известен как симметричный метод ранга один, который не гарантирует положительной определенности. Чтобы сохранить симметрию и положительную определенность $B k + 1 {\ displaystyle B_ {k + 1}}$ $B_ {k + 1}$ , форма обновления может быть выбрана как $B k + 1 = B к + α uu ⊤ + β vv ⊤ {\ displaystyle B_ {k + 1} = B_ {k} + \ alpha \ mathbf {u} \ mathbf {u} ^ {\ top} + \ beta \ mathbf {v} \ mathbf {v} ^ {\ top}}$ ${\ displaystyle B_ {k + 1} = B_ {k} + \ alpha \ mathbf {u} \ mathbf {u} ^ {\ top} + \ beta \ mathbf {v} \ mathbf {v} ^ {\ top}}$ . Применяя условие секанса, $B k + 1 sk = yk {\ displaystyle B_ {k + 1} \ mathbf {s} _ {k} = \ mathbf {y} _ {k}}$ ${\ displaystyle B_ {k + 1} \ mathbf {s} _ {k} = \ mathbf {y} _ {k}}$ . Выбор $u = yk {\ displaystyle \ mathbf {u} = \ mathbf {y} _ {k}}$ ${\ displaystyle \ mathbf { u} = \ mathbf {y} _ {k}}$ и $v = B ksk {\ displaystyle \ mathbf {v} = B_ {k} \ mathbf {s} _ {k}}$ ${\ displaystyle \ mathbf {v} = B_ {k} \ mathbf {s } _ {k}}$ , мы можем получить:

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

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

β = - 1 sk TB ksk. {\ displaystyle \ beta = - {\ frac {1} {\ mathbf {s} _ {k} ^ {T} B_ {k} \ mathbf {s} _ {k}}}.}

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

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

B k + 1 = B k + ykyk T yk T sk - B ksksk TB k T sk TB ksk. {\ 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 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}}}.}

Алгоритм

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

Получите направление $pk {\ displaystyle \ mathbf {p} _ {k}}$ $\ mathbf { p} _ {k}$ , решив $B kpk = - ∇ f (xk) {\ displaystyle B_ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k})}$ ${\ displaystyle B_ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k})}$ .
Выполните одномерную оптимизацию (поиск строки ), чтобы найти приемлемый размер шага $α k {\ displaystyle \ alpha _ {k}}$ $\ alpha _ {k}$ в направлении, найденном на первом шаге, поэтому $α k = arg ⁡ min f (xk + α pk) {\ Displaystyle \ альфа _ {к} = \ arg \ min f (\ mathbf {x} _ {k} + \ alpha \ mathbf {p} _ {k})}$ ${\ displaystyle \ alpha _ {k} = \ arg \ min f (\ mathbf {x} _ {k} + \ alpha \ mathbf {p} _ {k})}$ .
Установить $sk = α kpk {\ displaystyle \ mathbf {s} _ {k} = \ alpha _ {k} \ mathbf {p} _ {k}}$ ${\ displaystyle \ mathbf {s} _ {k} = \ alpha _ {k} \ mathbf {p} _ {k}}$ и обновить $xk + 1 = xk + sk {\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ mathbf {s} _ {k}}$ ${\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ mathbf {s} _ {k}}$ .
$yk = ∇ f (xk + 1) - ∇ f (xk) {\ displaystyle \ mathbf {y} _ {k} = {\ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k})}}$ ${\ displaystyle \ mathbf {y} _ {k} = {\ nabla е (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k})}}$ .
$B k + 1 = B k + ykyk T yk T sk - B ksksk TB k T sk TB ksk {\ 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 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}}}}$ .

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

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

B k + 1 - 1 = (I - skyk T yk T sk) B k - 1 (I - yksk T yk T sk) + sksk T yk T sk. {\ 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} ^ {- 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 {\ displaystyle B_ {k} ^ {- 1}}$ $B_ {к} ^ {- 1}$ является симметричным, и что $yk TB k - 1 yk {\ displaystyle \ mathbf {y} _ {k} ^ {\ mathrm {T}} B_ {k} ^ {- 1} \ mathbf {y} _ {k}}$ $\ mathbf {y} _ {k} ^ {\ mathrm {T}} B_ {k} ^ {- 1} \ mathbf {y } _ {k}$ и $sk T yk {\ displaystyle \ mathbf {s} _ {k} ^ {\ mathrm {T}} \ mathbf {y} _ {k}}$ $\ mathbf {s} _ {k} ^ {\ mathrm {T}} \ mathbf {y} _ {k}$ - скаляры с использованием расширения, такого как

B k + 1 - 1 = B k - 1 + (sk T yk + yk TB k - 1 yk) (sksk T) (sk T yk) 2 - B k - 1 yksk T + skyk TB k - 1 sk T yk. {\ 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}}}.}

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 может не сходиться к истинной матрице Гессе.

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

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

См. Также

Ссылки

Дополнительная литература

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