Квазиньютоновские методы
— методы
оптимизации
, основанные на накоплении информации о
кривизне
целевой функции
по наблюдениям за изменением
градиента
, чем принципиально отличаются от
ньютоновских методов
. Класс квазиньютоновских методов исключает явное формирование матрицы Гессе, заменяя её некоторым приближением.
Описание
Разложим
градиент
исходной функции в
ряд Тейлора
в окрестности точки очередного приближения
по степеням следующего шага алгоритма
:
-
-
Тогда оценка
матрицы Гессе
должна удовлетворять равенству:
-
-
,
где
это условие называют
квазиньютоновским
.
На каждой итерации с помощью
определяется следующее направление поиска
, и матрица
обновляется с учётом вновь полученной информации о кривизне:
-
-
-
-
,
где
— матрица, характеризующая поправку, вносимую на очередном шаге.
В качестве начального приближения
кладут единичную матрицу, таким образом первое направление
будет в точности совпадать с направлением
наискорейшего спуска
.
Поправка единичного ранга
Один шаг алгоритма даёт информацию о кривизне вдоль одного направления, поэтому
ранг
матрицы
полагают малым, и даже единичным:
-
-
где
и
некоторые вектора.
Тогда, квазиньютоновское условие примет вид:
-
-
-
-
Полагая, что предыдущая матрица
на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор
не
ортогонален
, получают выражение для
и
:
-
-
-
-
Из соображений симметричности матрицы Гессе, вектор
берут
коллинеарным
:
-
-
Полученное уравнение называется
симметричной формулой ранга один
.
Поправки ранга два
Один из способов конструирования поправок ранга два заключается в построении сходящейся
последовательности
матриц
. В качестве начального значения
берут
,
вычисляют по формуле:
-
-
После чего её симметризуют:
-
-
Однако полученная матрица больше не удовлетворяет квазиньютоновскому условию. Чтобы это исправить, процедуру повторяют. В результате на
-м шаге:
-
-
-
Предел
этой последовательности равен:
-
-
При выборе различных
(не ортогональных
) получаются различные формулы пересчёта матрицы
:
-
приводит к
симметричной формуле ранга один
;
-
приводит к
симметричной формуле Пауэлла — Бройдена (PSB)
;
-
приводит к
симметричной формуле Девидона — Флетчера — Пауэлла (DFP)
:
-
-
,
где
Нетрудно проверить, что
ортогонален
. Таким образом добавление слагаемого
не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем
формулы
Бройдена — Флетчера — Гольдфарба — Шанно
(BFGS)
:
-
-
Литература
-
Гилл Ф., Мюррей У., Райт М.
Практическая оптимизация = practical optimization.