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

15

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

JkJk1Fro2 со старым якобиевойусловии ограничениячто она принимает во внимание последнюю секущий: Jk(xkxk1)=f(xk)f(xk1) .

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

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

Ответы:

12

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

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

f(x)minxRn.
xkf То есть, ищется p такой, что ( ) минимально и задает x k + 1 : = x k + p . Вычисление градиента ( ) - «по отношению к p » - и установка его в ноль дает соотношение H ( x k ) [ x k + 1 - x k ] = f ( x k + 1 ) -
f(xk+p)f(xk)+f(xk)Tp+12pTH(xk)p.()
p()xk+1:=xk+p()p где H - «якобиан градиента» или матрица Гессе.
H(xk)[xk+1xk]=f(xk+1)f(xk),
H

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


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

(см. обновление Бройдена) может быть, что обновление BFGS минимизирует H - 1 k - H - 1W в умно выбранной взвешенной норме Фробениуса, при условииHk+11

| |ЧАСК-1-ЧАС-1| |W
  1. ЧАС[ИксК+1-ИксК]знак равное(ИксК+1)-е(ИксК)
  2. ЧАСTзнак равноЧАС

W| |ЧАС| |Wзнак равно| |W1/2ЧАСW1/2| |F граммзнак равно01ЧАС(ИксК+τп)dταКзнак равно1

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

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

п

январь
источник
WW
Да, верно. Ну, я не знаю. Один из ответов заключается в том, что он дает простую для вычисления и хорошо работающую формулу обновления. Исторически такой подход к обновлению, сводящий к минимуму разницу в обновлении, применялся Шенно. Это был рефери (Голдфарб), который обнаружил, что определенный выбор весов приводит к формуле Бройдена и Флетчера. Посмотрите эту кандидатскую диссертацию Историческое развитие метода секущих BFGS ... для интуиции разработчиков BFGS. Однако все 3 подхода достаточно абстрактны.
января
1
Интересно, спасибо за руководство! Моя текущая рецензия (с некоторыми математическими ошибками, которые нуждаются в помощи) находится здесь: graphics.stanford.edu/courses/cs205a-13-fall/assets/notes/… (если вы хотите получить кредит за вашу помощь, я с радостью ее предоставлю) - пожалуйста, напишите мне с подходящей контактной информацией)
Джастин Соломон
ЧАС(ИксК)[ИксК+1-ИксК]знак равное(ИксК+1)-е(ИксК)
ЧАС(ИксК+1)[ИксК+1-ИксК]знак равное(ИксК+1)-е(ИксК)?
ЧАСК+1sКзнак равноYКsКзнак равноИксК+1-ИксК,YКзнак равноеК+1-еК