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

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

Описание

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

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

Литература

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