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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

,

где

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

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

,

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

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

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

[править | править код]

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

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

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

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

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

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

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

[править | править код]

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

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

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

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

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

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

где

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

Литература

[править | править код]
  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = practical optimization.