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

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

ОписаниеПравить

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

$\stackrel{\to <!--\; \to \; -->}{g}({\stackrel{\to <!--\; \to \; -->}{x}}_k+{\stackrel{\to <!--\; \to \; -->}{s}}_k)\approx <!--\; \approx \; -->\stackrel{\to <!--\; \to \; -->}{g}({\stackrel{\to <!--\; \to \; -->}{x}}_k)+G({\stackrel{\to <!--\; \to \; -->}{x}}_k){\stackrel{\to <!--\; \to \; -->}{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}}$  должна удовлетворять равенству:

$B_{k+1}{\stackrel{\to <!--\; \to \; -->}{s}}_k={\stackrel{\to <!--\; \to \; -->}{y}}_k$$B_{{k+1}}{\vec {s}}_{k}={\vec {y}}_{k}$ ,

где ${\stackrel{\to <!--\; \to \; -->}{y}}_k=\stackrel{\to <!--\; \to \; -->}{g}({\stackrel{\to <!--\; \to \; -->}{x}}_k+{\stackrel{\to <!--\; \to \; -->}{s}}_k)-<!--\; -\; -->\stackrel{\to <!--\; \to \; -->}{g}({\stackrel{\to <!--\; \to \; -->}{x}}_k)$${\vec {y}}_{k}={\vec {g}}({\vec {x}}_{k}+{\vec {s}}_{k})-{\vec {g}}({\vec {x}}_{k})$ 

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

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

$B_k{\stackrel{\to <!--\; \to \; -->}{p}}_k=-<!--\; -\; -->\stackrel{\to <!--\; \to \; -->}{g}({\stackrel{\to <!--\; \to \; -->}{x}}_k)$$B_{k}{\vec {p}}_{k}=-{\vec {g}}({\vec {x}}_{k})$ 

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

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

В качестве начального приближения $B_0$$B_{0}$  кладут единичную матрицу, таким образом первое направление ${\stackrel{\to <!--\; \to \; -->}{p}}_0$${\vec {p}}_{0}$  будет в точности совпадать с направлением наискорейшего спуска.

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

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

$B_{k+1}=B_k+\stackrel{\to <!--\; \to \; -->}{u}{\stackrel{\to <!--\; \to \; -->}{v}}^T$$B_{{k+1}}=B_{k}+{\vec {u}}{\vec {v}}^{T}$ 

где $\stackrel{\to <!--\; \to \; -->}{u}$${\vec {u}}$  и $\stackrel{\to <!--\; \to \; -->}{v}$$\vec{v}$  некоторые вектора.

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

$(B_k+\stackrel{\to <!--\; \to \; -->}{u}{\stackrel{\to <!--\; \to \; -->}{v}}^T){\stackrel{\to <!--\; \to \; -->}{s}}_k={\stackrel{\to <!--\; \to \; -->}{y}}_k$$(B_{k}+{\vec {u}}{\vec {v}}^{T}){\vec {s}}_{k}={\vec {y}}_{k}$ 

$\stackrel{\to <!--\; \to \; -->}{u}({\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k)={\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k$${\vec {u}}({\vec {v}}^{T}{\vec {s}}_{k})={\vec {y}}_{k}-B_{k}{\vec {s}}_{k}$ 

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

$\stackrel{\to <!--\; \to \; -->}{u}=\frac{1}{{\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k)$${\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}{{\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k){\stackrel{\to <!--\; \to \; -->}{v}}^T$$B_{{k+1}}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}$ 

Из соображений симметричности матрицы Гессе, вектор $\stackrel{\to <!--\; \to \; -->}{v}$$\vec{v}$  берут коллинеарным $\stackrel{\to <!--\; \to \; -->}{u}$${\vec {u}}$ :

$B_{k+1}=B_k+\frac{1}{({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{)}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k)({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{)}^T$$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^{{(j)}}$ . В качестве начального значения $B^{(0)}$$B^{{(0)}}$  берут $B_k$$B_{k}$ , $B^{(1)}$$B^{{(1)}}$  вычисляют по формуле:

$B^{(1)}=B^{(0)}+\frac{1}{{\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B^{(0)}{\stackrel{\to <!--\; \to \; -->}{s}}_k){\stackrel{\to <!--\; \to \; -->}{v}}^T$$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}$$B^{{(2)}}={\frac {B^{{(1)}}+B^{{(1)T}}}{2}}$ 

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

$B^{(2j+1)}=B^{(2j)}+\frac{1}{{\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B^{(2j)}{\stackrel{\to <!--\; \to \; -->}{s}}_k){\stackrel{\to <!--\; \to \; -->}{v}}^T$$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^{{(2j+2)}}={\frac {B^{{(2j+1)}}+B^{{(2j+1)T}}}{2}}$ 

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

$B_{k+1}=B_k+\frac{1}{{\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}[({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k){\stackrel{\to <!--\; \to \; -->}{v}}^T+\stackrel{\to <!--\; \to \; -->}{v}({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{)}^T]-<!--\; -\; -->\frac{({\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->B_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{)}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}{({\stackrel{\to <!--\; \to \; -->}{v}}^T{\stackrel{\to <!--\; \to \; -->}{s}}_k{)}^2}\stackrel{\to <!--\; \to \; -->}{v}{\stackrel{\to <!--\; \to \; -->}{v}}^T$$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}$ 

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

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

$B_{k+1}=B_k-<!--\; -\; -->\frac{1}{{\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k}{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k^T+\frac{1}{{\stackrel{\to <!--\; \to \; -->}{y}}_k^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}{\stackrel{\to <!--\; \to \; -->}{y}}_k{\stackrel{\to <!--\; \to \; -->}{y}}_k^T+({\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k){\stackrel{\to <!--\; \to \; -->}{\mathrm{\omega <!--\; \omega \; -->}}}_k{\stackrel{\to <!--\; \to \; -->}{\mathrm{\omega <!--\; \omega \; -->}}}_k^T$$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}$ ,

где ${\stackrel{\to <!--\; \to \; -->}{\mathrm{\omega <!--\; \omega \; -->}}}_k=\frac{1}{{\stackrel{\to <!--\; \to \; -->}{y}}_k^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}{\stackrel{\to <!--\; \to \; -->}{y}}_k-<!--\; -\; -->\frac{1}{{\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k}{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k$${\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}$ 

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

$B_{k+1}=B_k-<!--\; -\; -->\frac{1}{{\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k}{B}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k{\stackrel{\to <!--\; \to \; -->}{s}}_k^T{B}_k^T+\frac{1}{{\stackrel{\to <!--\; \to \; -->}{y}}_k^T{\stackrel{\to <!--\; \to \; -->}{s}}_k}{\stackrel{\to <!--\; \to \; -->}{y}}_k{\stackrel{\to <!--\; \to \; -->}{y}}_k^T$$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.