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

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

Описание

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

${\displaystyle {\vec {g}}({\vec {x}}_{k}+{\vec {s}}_{k})\approx {\vec {g}}({\vec {x}}_{k})+G({\vec {x}}_{k}){\vec {s}}_{k}}$

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

${\displaystyle B_{k+1}{\vec {s}}_{k}={\vec {y}}_{k}}$,

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

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

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

${\displaystyle B_{k}{\vec {p}}_{k}=-{\vec {g}}({\vec {x}}_{k})}$

${\displaystyle B_{k+1}=B_{k}+U_{k}}$,

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

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

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

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

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

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

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

${\displaystyle (B_{k}+{\vec {u}}{\vec {v}}^{T}){\vec {s}}_{k}={\vec {y}}_{k}}$

${\displaystyle {\vec {u}}({\vec {v}}^{T}{\vec {s}}_{k})={\vec {y}}_{k}-B_{k}{\vec {s}}_{k}}$

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

${\displaystyle {\vec {u}}={\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})}$

${\displaystyle B_{k+1}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}}$

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

${\displaystyle 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}}$

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

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

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

${\displaystyle B^{(1)}=B^{(0)}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B^{(0)}{\vec {s}}_{k}){\vec {v}}^{T}}$

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

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

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

${\displaystyle B^{(2j+1)}=B^{(2j)}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B^{(2j)}{\vec {s}}_{k}){\vec {v}}^{T}}$

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

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

${\displaystyle 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}}$

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

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

${\displaystyle 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}^{T}+{\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}}$,

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

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

${\displaystyle 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}^{T}+{\frac {1}{{\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}{\vec {y}}_{k}^{T}}$

Литература

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