Квазиньютоновские методы | это... Что такое Квазиньютоновские методы? (original) (raw)

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

Содержание

1 Описание
- 1.1 Поправка единичного ранга
- 1.2 Поправки ранга два
2 Литература

Описание

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

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

$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_{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.

Методы оптимизации
Одномерные	Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск
Прямые методы	Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка
Первого порядка	Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта
Второго порядка	Метод Ньютона • Метод Ньютона — Рафсона
Стохастические	Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц
Методы линейного программирования	Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов
Методы нелинейногопрограммирования	Последовательное квадратичное программирование