Метод Барзилаи-Борвейна

Метод Барзилаи -Борвейна. — это итерационный метод градиентного спуска для неограниченной оптимизации с использованием любого из двух размеров шага, полученных на основе линейного тренда последних двух итераций. Этот метод и его модификации глобально сходятся в мягких условиях. и конкурентоспособно работать с методами сопряженных градиентов для решения многих задач. Независимо от самой цели, он также может решать некоторые системы линейных и нелинейных уравнений.

Метод

Чтобы минимизировать выпуклую функцию $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$ с вектором градиента $g$ в точку $x$, пусть есть две предыдущие итерации, $g_{k-1}(x_{k-1})$ и $g_{k}(x_{k})$, в котором $x_{k}=x_{k-1}-\alpha _{k-1}g_{k-1}$ где $\alpha _{k-1}$ — размер шага предыдущей итерации (не обязательно размер шага Барзилаи-Борвейна), и для краткости пусть $\Delta x=x_{k}-x_{k-1}$ и $\Delta g=g_{k}-g_{k-1}$.

Итерация Барзилай-Борвейна (BB) $x_{k+1}=x_{k}-\alpha _{k}g_{k}$ где размер шага $\alpha _{k}$ либо

[длинный шаг ББ] $\alpha _{k}^{LONG}={\frac {\Delta x\cdot \Delta x}{\Delta x\cdot \Delta g}}$, или

[короткий шаг ББ] $\alpha _{k}^{SHORT}={\frac {\Delta x\cdot \Delta g}{\Delta g\cdot \Delta g}}$.

Барзилай-Борвейн применяется также к системам уравнений $g(x)=0$ для $g:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}$ в котором якобиан $g$ положительно определен в симметричной части, т. е. $\Delta x\cdot \Delta g$ обязательно положительный.

Вывод

Несмотря на свою простоту и свойства оптимальности, классический метод наискорейшего спуска Коши для неограниченной оптимизации часто работает плохо. Это побудило многих предложить альтернативные направления поиска, такие как метод сопряженных градиентов . Вместо этого Джонатан Барзилай и Джонатан Борвейн предложили новые размеры шага для градиента путем аппроксимации метода квазиньютона , создавая скалярную аппроксимацию гессиана, оцененного на основе конечных разностей между двумя точками оценки градиента, причем это две самые последние итерации.

В квазиньютоновской итерации

$x_{k+1}=x_{k}-B^{-1}g(x_{k})$

где $B$ является некоторым приближением матрицы Якобиана $g$ (т.е. гессиан целевой функции), который удовлетворяет уравнению секущего $B_{k}\Delta x_{k}=\Delta g_{k}$. Барзилай и Борвейн упрощают $B$ со скаляром $1/\alpha$, которое обычно не может точно удовлетворить уравнению секущего, но аппроксимирует его как ${\frac {1}{\alpha }}\Delta x\approx \Delta g$. Аппроксимации по двум критериям наименьших квадратов:

[1] Свернуть $\|\Delta x/\alpha -\Delta g\|^{2}$ относительно $\alpha$, что дает длинный шаг BB, или

[2] Свернуть $\|\Delta x-\alpha \Delta g\|^{2}$ относительно $\alpha$, что дает короткий шаг BB.

Характеристики

В одном измерении оба размера шага BB равны и такие же, как и в классическом методе секущих .

Размер длинного шага BB такой же, как и линеаризованный шаг Коши, т.е. первая оценка с использованием метода секущих для поиска прямой (также для линейных задач ). Размер короткого шага BB такой же, как и линеаризованный шаг с минимальной невязкой. BB применяет размеры шага к вектору прямого направления для следующей итерации вместо предыдущего вектора направления, как если бы для другого шага поиска строки.

Барзилай и Борвейн доказали, что их метод сходится R -сверхлинейно для квадратичной минимизации в двух измерениях. Райдан демонстрирует сходимость в целом для квадратичных задач. Сходимость обычно немонотонна, то есть ни целевая функция, ни величина остатка или градиента не обязательно уменьшаются с каждой итерацией при успешной сходимости к решению.

Если $f$ квадратичная функция с гессианом $A$, $1/\alpha ^{LONG}$ является Рэлея коэффициентом $A$ по вектору $\Delta x$, и $1/\alpha ^{SHORT}$ является коэффициентом Рэлея $A$ по вектору ${\sqrt {A}}\Delta x$ (здесь берём ${\sqrt {A}}$ как решение $({\sqrt {A}})^{T}{\sqrt {A}}=A$, подробнее в разделе «Определенная матрица» ).

Флетчер сравнил его вычислительную производительность с методами сопряженных градиентов (CG) и обнаружил, что CG стремится быстрее для линейных задач, но BB часто быстрее для нелинейных задач по сравнению с применимыми методами на основе CG.

BB имеет низкие требования к объему памяти и подходит для больших систем с миллионами элементов. $x$.

${\frac {\alpha ^{SHORT}}{\alpha ^{LONG}}}=cos^{2}($угол между $\Delta x$ и $\Delta g)$.

Модификации и связанные с ними методы

С тех пор, как его продемонстрировал Райдан, BB часто применяется вместе с немонотонной защитной стратегией Гриппо, Лампариелло и Люсиди. Это допускает некоторое повышение цели, но чрезмерное повышение инициирует поиск линии с возвратом с использованием меньших размеров шага, чтобы обеспечить глобальную конвергенцию. Флетчер обнаруживает, что предоставление более широких пределов немонотонности приводит к более эффективной сходимости.

Другие определили размер шага, представляющий собой среднее геометрическое между размерами длинного и короткого шага BB, который демонстрирует аналогичные свойства.

Внешние ссылки

• Джонатан Барзилай