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

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

Описание

Разложим градиент g → ( x → k ) {displaystyle {vec {g}}({vec {x}}_{k})} исходной функции в ряд Тейлора в окрестности точки очередного приближения x → k {displaystyle {vec {x}}_{k}} по степеням следующего шага алгоритма s → k {displaystyle {vec {s}}_{k}} :

Тогда оценка матрицы Гессе B k + 1 {displaystyle B_{k+1}} должна удовлетворять равенству:

где y → k = g → ( x → k + s → k ) − g → ( x → k ) {displaystyle {vec {y}}_{k}={vec {g}}({vec {x}}_{k}+{vec {s}}_{k})-{vec {g}}({vec {x}}_{k})}

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

На каждой итерации с помощью B k {displaystyle B_{k}} определяется следующее направление поиска p → k {displaystyle {vec {p}}_{k}} , и матрица B {displaystyle B} обновляется с учётом вновь полученной информации о кривизне:

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

В качестве начального приближения B 0 {displaystyle B_{0}} кладут единичную матрицу, таким образом первое направление p → 0 {displaystyle {vec {p}}_{0}} будет в точности совпадать с направлением наискорейшего спуска.

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

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

где u → {displaystyle {vec {u}}} и v → {displaystyle {vec {v}}} некоторые вектора.

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

Полагая, что предыдущая матрица B k {displaystyle B_{k}} на очередном шаге квазиньютоновскому условию не удовлетворяет (т.е. разность в правой части не равна нулю), и что вектор v → {displaystyle {vec {v}}} не ортогонален s → k {displaystyle {vec {s}}_{k}} , получают выражение для u → {displaystyle {vec {u}}} и B k + 1 {displaystyle B_{k+1}} :

Из соображений симметричности матрицы Гессе, вектор v → {displaystyle {vec {v}}} берут коллинеарным u → {displaystyle {vec {u}}} :

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

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

Один из способов конструирования поправок ранга два заключается в построении сходящейся последовательности матриц B ( j ) {displaystyle B^{(j)}} . В качестве начального значения B ( 0 ) {displaystyle B^{(0)}} берут B k {displaystyle B_{k}} , B ( 1 ) {displaystyle B^{(1)}} вычисляют по формуле:

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

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

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

При выборе различных v → {displaystyle {vec {v}}} (не ортогональных s → k {displaystyle {vec {s}}_{k}} ) получаются различные формулы пересчёта матрицы B {displaystyle B} :

• v → = y → k − B k s → k {displaystyle {vec {v}}={vec {y}}_{k}-B_{k}{vec {s}}_{k}} приводит к симметричной формуле ранга один;
• v → = s → k {displaystyle {vec {v}}={vec {s}}_{k}} приводит к симметричной формуле Пауэлла — Бройдена (PSB);
• v → = y → k {displaystyle {vec {v}}={vec {y}}_{k}} приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):

где ω → k = 1 y → k T s → k y → k − 1 s → k T B k s → k B k s → k {displaystyle {vec {omega }}_{k}={frac {1}{{vec {y}}_{k}^{T}{vec {s}}_{k}}}{vec {y}}_{k}-{frac {1}{{vec {s}}_{k}^{T}B_{k}{vec {s}}_{k}}}B_{k}{vec {s}}_{k}}

Нетрудно проверить, что ω → k {displaystyle {vec {omega }}_{k}} ортогонален s → k {displaystyle {vec {s}}_{k}} . Таким образом добавление слагаемого ω → k ω → k T {displaystyle {vec {omega }}_{k}{vec {omega }}_{k}^{T}} не нарушит ни квазиньютоновского условия, ни условия симметричности. Поэтому проводился ряд теоретических исследований, подвергавших последнее слагаемое масштабированию на предмет получения наилучшего приближения. В результате была принята точка зрения, что наилучшим вариантом является отвечающий полному отсутствию последнего слагаемого. Этот вариант пересчёта известен под именем формулы Бройдена — Флетчера — Гольдфарба — Шанно (BFGS):