Интуитивная мотивация для обновления BFGS

Я преподаю урок по численному анализу и ищу мотивацию для метода BFGS для студентов с ограниченным опытом / интуицией в оптимизации!

$\|J_k-J_{k-1}\|^2_{\textrm{Fro}}$ со старым якобиевойусловии ограничениячто она принимает во внимание последнюю секущий: $J_k(\vec x_k-\vec x_{k-1})=f(\vec x_k)-f(\vec x_{k-1})$ .

Выводы обновлений BFGS кажутся гораздо более запутанными и мутными! В частности, я бы не хотел априори предполагать, что обновление должно быть ранга 2 или принимать определенную форму. Есть ли короткая вариативно-мотивирующая мотивация для обновления BFGS Hessian, как для Бройдена?

optimization iterative-method nonlinear-programming Джастин Соломон
источник

Если вы разрешите произвольное обновление, то вы можете просто использовать полный гессиан в методе Ньютона. Одним из основных вычислительных преимуществ обновления низкого ранга является то, что оно позволяет очень быстро обновлять факторизацию приближенного гессиана.

Брайан Борхерс

Вывод BFGS является более интуитивным, если рассматривать (строго) выпуклые функционалы стоимости:

Однако некоторая справочная информация необходима: Предположим, что нужно минимизировать выпуклый функционал Скажем, есть приблизительное решение . Тогда каждый приближает минимум к минимуму усеченного разложения Тейлора

f (x) \to min_{x \in R^{n}} .

$f(x) \to \min_{x\in \mathbb R^n}.$

x_{k}

$x_k$

f

$f$

То есть, ищется

такой, что

минимально и задает

. Вычисление градиента

- «по отношению к

» - и установка его в ноль дает соотношение

f (x_{k} + p) \approx f (x_{k}) + \nabla f (x_{k})^{T} p + \frac{1}{2} p^{T} H (x_{k}) p . (*)

$f(x_k+p) \approx f(x_k) +\nabla f(x_k)^Tp + \frac{1}{2}p^T H(x_k)p. \quad(*)$

p

$p$

(*)

$(*)$

x_{k + 1} := x_{k} + p

$x_{k+1} := x_k + p$

(*)

$(*)$

p

$p$

где

- «якобиан градиента» или матрица Гессе.

H (x_{k}) [x_{k + 1} - x_{k}] = \nabla f (x_{k + 1}) - \nabla f (x_{k}),

$H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k),$

H

$H$

Поскольку вычисление и инверсия гессиана стоит дорого ...

... короткий ответ

(см. обновление Бройдена) может быть, что обновление BFGS минимизирует в умно выбранной взвешенной норме Фробениуса, при условии $H_{k+1}^{-1}$

| | {ЧАС}_{К}^{- 1} - {ЧАС}^{- 1} {| |}_{W}

$\|H_k^{-1} - H^{-1}\|_W$

$H[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$
$H^T = H$

$W$ $\|H\|_W := \|W^{1/2}HW^{1/2}\|_F$ $G:=\int_0^1 H(x_k + \tau p) d\tau$ $\alpha_k = 1$

Основные моменты:

Попытка приблизить решение для фактических затрат решением для квадратичного приближения
Вычисление гессиана и его обратное дорого. Один предпочитает простые обновления.
Обновление выбрано оптимально для обратного, а не фактического гессиана.
То, что это обновление ранга 2, является следствием особого выбора весов в норме Фробениуса.

$p$

январь
источник

W

$W$

W

$W$

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

января

Интересно, спасибо за руководство! Моя текущая рецензия (с некоторыми математическими ошибками, которые нуждаются в помощи) находится здесь: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (если вы хотите получить кредит за вашу помощь, я с радостью ее предоставлю) - пожалуйста, напишите мне с подходящей контактной информацией)

Джастин Соломон

ЧАС ({Икс}_{К}) [{Икс}_{К + 1} - {Икс}_{К}] знак равно \nabla е ({Икс}_{К + 1}) - \nabla е ({Икс}_{К})

$H(x_k)[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)$

ЧАС ({Икс}_{К + 1}) [{Икс}_{К + 1} - {Икс}_{К}] знак равно \nabla е ({Икс}_{К + 1}) - \nabla е ({Икс}_{К}) ?

$H(x_{k+1})[x_{k+1} - x_k] = \nabla f(x_{k+1}) - \nabla f(x_k)?$

H_{k + 1} s_{k} = y_{k}

$H_{k+1}s_k =y_k$

s_{k} = x_{k + 1} - x_{k}, y_{k} = \nabla f_{k + 1} - \nabla f_{k}

$s_k=x_{k+1}-x_k, y_k=\nabla f_{k+1}-\nabla f_k$

Интуитивная мотивация для обновления BFGS

Ответы:

... короткий ответ