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

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

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

Описание[править | править исходный текст]

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

\vec{g}(\vec{x}_k+\vec{s}_k)\approx \vec{g}(\vec{x}_k)+G(\vec{x}_k)\vec{s}_k

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

B_{k+1}\vec{s}_k=\vec{y}_k,

где \vec{y}_k=\vec{g}(\vec{x}_k+\vec{s}_k)- \vec{g}(\vec{x}_k)

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

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

B_k\vec{p}_k=-\vec{g}(\vec{x}_k)
B_{k+1}=B_k+U_k,

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

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

Поправка единичного ранга[править | править исходный текст]

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

B_{k+1}=B_k+\vec{u}\vec{v}^T

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

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

(B_k+\vec{u}\vec{v}^T)\vec{s}_k=\vec{y}_k
\vec{u}(\vec{v}^T\vec{s}_k)=\vec{y}_k-B_k\vec{s}_k

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

\vec{u}=\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B_k\vec{s}_k)
B_{k+1}=B_k+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B_k\vec{s}_k)\vec{v}^T

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

B_{k+1}=B_k+\frac{1}{(\vec{y}_k-B_k\vec{s}_k)^T\vec{s}_k}(\vec{y}_k-B_k\vec{s}_k)(\vec{y}_k-B_k\vec{s}_k)^T

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

Поправки ранга два[править | править исходный текст]

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

B^{(1)}=B^{(0)}+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B^{(0)}\vec{s}_k)\vec{v}^T

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

B^{(2)}=\frac{B^{(1)}+B^{(1)T}}{2}

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

B^{(2j+1)}=B^{(2j)}+\frac{1}{\vec{v}^T\vec{s}_k}(\vec{y}_k-B^{(2j)}\vec{s}_k)\vec{v}^T
B^{(2j+2)}=\frac{B^{(2j+1)}+B^{(2j+1)T}}{2}

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

B_{k+1}=B_k+\frac{1}{\vec{v}^T\vec{s}_k}[(\vec{y}_k-B_k\vec{s}_k)\vec{v}^T+\vec{v}(\vec{y}_k-B_k\vec{s}_k)^T]-\frac{(\vec{y}_k-B_k\vec{s}_k)^T\vec{s}_k}{(\vec{v}^T\vec{s}_k)^2}\vec{v}\vec{v}^T

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

  • \vec{v}=\vec{y}_k-B_k\vec{s}_k приводит к симметричной формуле ранга один;
  • \vec{v}=\vec{s}_k приводит к симметричной формуле Пауэлла — Бройдена (PSB);
  • \vec{v}=\vec{y}_k приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):
B_{k+1}=B_k-\frac{1}{\vec{s}_k^T B_k \vec{s}_k}B_k \vec{s}_k \vec{s}_k^T B_k+\frac{1}{\vec{y}_k^T\vec{s}_k}\vec{y}_k\vec{y}_k^T+(\vec{s}_k^T B_k \vec{s}_k)\vec{\omega}_k\vec{\omega}_k^T,

где \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

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

B_{k+1}=B_k-\frac{1}{\vec{s}_k^T B_k \vec{s}_k}B_k \vec{s}_k \vec{s}_k^T B_k+\frac{1}{\vec{y}_k^T\vec{s}_k}\vec{y}_k\vec{y}_k^T

Литература[править | править исходный текст]

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