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

Описание

править

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

 

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

 ,

где  

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

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

 
 ,

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

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

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

править

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

 

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

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

 
 

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

 
 

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

 

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

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

править

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

 

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

 

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

 
 

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

 

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

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

где  

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

 

Литература

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