Interested Article - Квазиньютоновские методы

Квазиньютоновские методы — методы оптимизации , основанные на накоплении информации о кривизне целевой функции по наблюдениям за изменением градиента , чем принципиально отличаются от ньютоновских методов . Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.

Описание

Разложим градиент исходной функции в ряд Тейлора в окрестности точки очередного приближения по степеням следующего шага алгоритма :

Тогда оценка матрицы Гессе должна удовлетворять равенству:

,

где

это условие называют квазиньютоновским .

На каждой итерации с помощью определяется следующее направление поиска , и матрица обновляется с учётом вновь полученной информации о кривизне:

,

где — матрица, характеризующая поправку, вносимую на очередном шаге.

В качестве начального приближения кладут единичную матрицу, таким образом первое направление будет в точности совпадать с направлением наискорейшего спуска .

Поправка единичного ранга

Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому ранг матрицы полагают малым, и даже единичным:

где и некоторые вектора.

Тогда, квазиньютоновское условие примет вид:

Полагая, что предыдущая матрица на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор не ортогонален , получают выражение для и :

Из соображений симметричности матрицы Гессе, вектор берут коллинеарным :

Полученное уравнение называется симметричной формулой ранга один .

Поправки ранга два

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

После чего её симметризуют:

Однако полученная матрица больше не удовлетворяет квазиньютоновскому условию. Чтобы это исправить, процедуру повторяют. В результате на -м шаге:

Предел этой последовательности равен:

При выборе различных (не ортогональных ) получаются различные формулы пересчёта матрицы :

  • приводит к симметричной формуле ранга один ;
  • приводит к симметричной формуле Пауэлла — Бройдена (PSB) ;
  • приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP) :
,

где

Нетрудно проверить, что ортогонален . Таким образом добавление слагаемого не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем формулы Бройдена — Флетчера — Гольдфарба — Шанно (BFGS) :

Литература

  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = practical optimization.
Источник —

Same as Квазиньютоновские методы