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

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

Описание

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

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

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

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

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

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

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

$B_k{\overrightarrow{p}}_k=-\overrightarrow{g}({\overrightarrow{x}}_k)$

$B_{k+1}=B_k+U_k$,

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

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

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

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

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

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

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

$(B_k+\overrightarrow{u}{\overrightarrow{v}}^T){\overrightarrow{s}}_k={\overrightarrow{y}}_k$

$\overrightarrow{u}({\overrightarrow{v}}^T{\overrightarrow{s}}_k)={\overrightarrow{y}}_k-B_k{\overrightarrow{s}}_k$

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

$\overrightarrow{u}=\frac{1}{{\overrightarrow{v}}^T{\overrightarrow{s}}_k}({\overrightarrow{y}}_k-B_k{\overrightarrow{s}}_k)$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• $\overrightarrow{v}={\overrightarrow{y}}_k-B_k{\overrightarrow{s}}_k$ приводит к симметричной формуле ранга один;
• $\overrightarrow{v}={\overrightarrow{s}}_k$ приводит к симметричной формуле Пауэлла — Бройдена (PSB);
• $\overrightarrow{v}={\overrightarrow{y}}_k$ приводит к симметричной формуле Девидона — Флетчера — Пауэлла (DFP):

$B_{k+1}=B_k-\frac{1}{{\overrightarrow{s}}_k^T{B}_k{\overrightarrow{s}}_k}{B}_k{\overrightarrow{s}}_k{\overrightarrow{s}}_k^T{B}_k^T+\frac{1}{{\overrightarrow{y}}_k^T{\overrightarrow{s}}_k}{\overrightarrow{y}}_k{\overrightarrow{y}}_k^T+({\overrightarrow{s}}_k^T{B}_k{\overrightarrow{s}}_k){\overrightarrow{\omega }}_k{\overrightarrow{\omega }}_k^T$,

где ${\overrightarrow{\omega }}_k=\frac{1}{{\overrightarrow{y}}_k^T{\overrightarrow{s}}_k}{\overrightarrow{y}}_k-\frac{1}{{\overrightarrow{s}}_k^T{B}_k{\overrightarrow{s}}_k}{B}_k{\overrightarrow{s}}_k$

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

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

Литература

• Шаблон:Книга