Нелинейный метод сопряженных градиентов

В числовой оптимизации метод нелинейного сопряженного градиента обобщает метод сопряженного градиента на нелинейную оптимизацию . Для квадратичной функции $\displaystyle f(x)$

$\displaystyle f(x)=\|Ax-b\|^{2},$

минимум $f$ получается, когда градиент равен 0:

$\nabla _{x}f=2A^{T}(Ax-b)=0$.

В то время как линейный сопряженный градиент ищет решение линейного уравнения $\displaystyle A^{T}Ax=A^{T}b$, метод нелинейного сопряженного градиента обычно используется для поиска локального минимума нелинейной функции используя его градиент $\nabla _{x}f$ один. Это работает, когда функция приблизительно квадратична вблизи минимума, а это тот случай, когда функция дважды дифференцируема в минимуме, а вторая производная там невырождена.

Дана функция $\displaystyle f(x)$ из $N$ переменные для минимизации, его градиент $\nabla _{x}f$ указывает направление максимального увеличения.Просто начинается в противоположном направлении ( наиболее крутой спуск ):

$\Delta x_{0}=-\nabla _{x}f(x_{0})$

с регулируемой длиной шага $\displaystyle \alpha$ и выполняет поиск строки в этом направлении, пока не достигнет минимума $\displaystyle f$:

$\displaystyle \alpha _{0}:=\arg \min _{\alpha }f(x_{0}+\alpha \Delta x_{0})$,

$\displaystyle x_{1}=x_{0}+\alpha _{0}\Delta x_{0}$

После этой первой итерации в самом крутом направлении $\displaystyle \Delta x_{0}$, следующие шаги составляют одну итерацию движения по последующему сопряженному направлению $\displaystyle s_{n}$, где $\displaystyle s_{0}=\Delta x_{0}$:

1. Рассчитайте самое крутое направление: $\Delta x_{n}=-\nabla _{x}f(x_{n})$,
2. Вычислить $\displaystyle \beta _{n}$ по одной из приведенных ниже формул,
3. Обновите сопряженное направление: $\displaystyle s_{n}=\Delta x_{n}+\beta _{n}s_{n-1}$
4. Выполните поиск по строке: оптимизируйте $\displaystyle \alpha _{n}=\arg \min _{\alpha }f(x_{n}+\alpha s_{n})$,
5. Обновите позицию: $\displaystyle x_{n+1}=x_{n}+\alpha _{n}s_{n}$,

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

В линейном приближении параметры $\displaystyle \alpha$ и $\displaystyle \beta$ такие же, как и вметод линейного сопряженного градиента, но были получены с помощью поиска линий.Метод сопряженных градиентов может следовать по узким ( плохо обусловленным ) долинам, где метод наискорейшего спуска замедляется и следует схеме крест-накрест.

Четыре наиболее известные формулы $\displaystyle \beta _{n}$ названы в честь своих разработчиков:

• Флетчер-Ривз:

$\beta _{n}^{FR}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$

• Полак-Рибьер:

$\beta _{n}^{PR}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{\Delta x_{n-1}^{T}\Delta x_{n-1}}}.$

• Гестенес-Штифель:

$\beta _{n}^{HS}={\frac {\Delta x_{n}^{T}(\Delta x_{n}-\Delta x_{n-1})}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.$

• Дай-Юань:

$\beta _{n}^{DY}={\frac {\Delta x_{n}^{T}\Delta x_{n}}{-s_{n-1}^{T}(\Delta x_{n}-\Delta x_{n-1})}}.$.

Эти формулы эквивалентны для квадратичной функции, но для нелинейной оптимизации предпочтительная формула зависит от эвристики или вкуса. Популярный выбор – $\displaystyle \beta =\max\{0,\beta ^{PR}\}$, что обеспечивает автоматический сброс направления.

Алгоритмы, основанные на методе Ньютона, потенциально сходятся гораздо быстрее. Там и направление, и длина шага вычисляются из градиента как решения линейной системы уравнений, при этом матрица коэффициентов представляет собой точную матрицу Гессе (для собственно метода Ньютона) или ее оценку (в квазиньютоновских методах , где наблюдаемое изменение градиента во время итераций используется для обновления оценки Гессиана). Для задач большой размерности точное вычисление гессиана обычно непомерно дорого, и даже его хранение может быть проблематичным, требуя $O(N^{2})$ с ограниченной памятью L-BFGS память (но см. квазиньютоновский метод ).

Метод сопряженных градиентов также может быть получен с использованием теории оптимального управления . В этой теории ускоренной оптимизации метод сопряженных градиентов выступает в роли нелинейного оптимального контроллера с обратной связью .

$u=k(x,{\dot {x}}):=-\gamma _{a}\nabla _{x}f(x)-\gamma _{b}{\dot {x}}$для системы двойного интегратора ,

${\ddot {x}}=u$

Количества $\gamma _{a}>0$ и $\gamma _{b}>0$ являются переменными коэффициентами усиления обратной связи.

См. также

• Градиентный спуск
• Алгоритм Бройдена–Флетчера–Гольдфарба–Шенно
• Метод сопряженных градиентов
• L-BFGS (BFGS с ограниченной памятью)
• Метод Нелдера-Мида
• Условия Вульфа