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

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

Описание

Разложим градиент $\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.