Метод сопряжённых градиентов

Шаблон:Другие значения Метод сопряжённых градиентов (Метод Флетчера — Ривcа) — метод нахождения локального экстремума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в ${ℝ}^n$ минимум находится не более чем за $n$ шагов.

Основные понятия

Определим терминологию:

Пусть $\overrightarrow{S_1},\dots ,\overrightarrow{S_n}\in 𝕏\subset {ℝ}^n$.

Введём на $𝕏$ целевую функцию $f(\overrightarrow{x})\in {\mathrm{C}}^{\mathrm{2}}(𝕏)$.

Векторы $\overrightarrow{S_1},\dots ,\overrightarrow{S_n}$ называются сопряжёнными, если:

• ${\overrightarrow{S_i}}^{T}H\overrightarrow{S_j}=0,i\ne j,i,j=1,\dots ,n$
• ${\overrightarrow{S_i}}^{T}H\overrightarrow{S_i}⩾0,i=1,\dots ,n$

где $H$ — матрица Гессе $f(\overrightarrow{x})$.

Обоснование метода

Нулевая итерация

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

Пусть $\overrightarrow{S_0}=-\mathrm{\nabla }f(\overrightarrow{x_0})(1)$

Тогда $\overrightarrow{x_1}=\overrightarrow{x_0}+{\lambda }_1\overrightarrow{S_0}$.

Определим направление

$\overrightarrow{S_1}=-\mathrm{\nabla }f(\overrightarrow{x_1})+{\omega }_1\overrightarrow{S_0}(2)$

так, чтобы оно было сопряжено с $\overrightarrow{S_0}$:

${\overrightarrow{S_0}}^{T}H\overrightarrow{S_1}=0(3)$

Разложим $\mathrm{\nabla }f(\overrightarrow{x})$ в окрестности $\overrightarrow{x_0}$ и подставим $\overrightarrow{x}=\overrightarrow{x_1}$:

$\mathrm{\nabla }f(\overrightarrow{x_1})-\mathrm{\nabla }f(\overrightarrow{x_0})=H(\overrightarrow{x_1}-\overrightarrow{x_0})={\lambda }_{1}H\overrightarrow{S_0}$

Транспонируем полученное выражение и домножаем на $H^{-1}$ справа:

$(\mathrm{\nabla }f(\overrightarrow{x_1})-\mathrm{\nabla }f(\overrightarrow{x_0}){)}^T{H}^{-1}={\lambda }_1{\overrightarrow{S_0}}^T{H}^T{H}^{-1}$

В силу непрерывности вторых частных производных $H^T=H$. Тогда:

${\overrightarrow{S_0}}^T=\frac{(\mathrm{\nabla }f(\overrightarrow{x_1})-\mathrm{\nabla }f(\overrightarrow{x_0}){)}^T{H}^{-1}}{{\lambda }_1}$

Подставим полученное выражение в (3):

$\frac{(\mathrm{\nabla }f(\overrightarrow{x_1})-\mathrm{\nabla }f(\overrightarrow{x_0}){)}^T{H}^{-1}H\overrightarrow{S_1}}{{\lambda }_1}=0$

Тогда, воспользовавшись (1) и (2):

$(\mathrm{\nabla }f(\overrightarrow{x_1})-\mathrm{\nabla }f(\overrightarrow{x_0}){)}^T(-\mathrm{\nabla }f(\overrightarrow{x_1})-{\omega }_1\mathrm{\nabla }f(\overrightarrow{x_0})))=0(4)$

Если $\lambda =\arg \underset{\lambda }{min}f(\overrightarrow{x_0}+\lambda \overrightarrow{S_0})$, то градиент в точке $\overrightarrow{x_1}=\overrightarrow{x_0}+\lambda \overrightarrow{S_0}$ перпендикулярен градиенту в точке $\overrightarrow{x_0}$, тогда по правилам скалярного произведения векторов:

$(\mathrm{\nabla }f(\overrightarrow{x_0}),\mathrm{\nabla }f(\overrightarrow{x_1}))=0$

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления $\omega$:

${\omega }_1=\frac{||\mathrm{\nabla }f(\overrightarrow{x_1})|{|}^2}{||\mathrm{\nabla }f(\overrightarrow{x_0})|{|}^2}$

К-я итерация

На k-й итерации имеем набор $\overrightarrow{S_0},\dots ,\overrightarrow{S_{k-1}}$.

Тогда следующее направление вычисляется по формуле:

$\overrightarrow{S_k}=-\mathrm{\nabla }f(\overrightarrow{x_k})-\Vert \mathrm{\nabla }f(\overrightarrow{x_k}){\Vert }^2\cdot (\frac{\mathrm{\nabla }f({\overrightarrow{x}}_{k-1})}{\Vert \mathrm{\nabla }f({\overrightarrow{x}}_{k-1}){\Vert }^2}+\dots +\frac{\mathrm{\nabla }f(\overrightarrow{x_0})}{\Vert \mathrm{\nabla }f({\overrightarrow{x}}_0){\Vert }^2})$

Это выражение может быть переписано в более удобном итеративном виде:

$\overrightarrow{S_k}=-\mathrm{\nabla }f(\overrightarrow{x_k})+{\omega }_k{\overrightarrow{S}}_{k-1},{\omega }_i=\frac{\Vert \mathrm{\nabla }f(\overrightarrow{x_i}){\Vert }^2}{\Vert \mathrm{\nabla }f({\overrightarrow{x}}_{i-1}){\Vert }^2},$

где ${\omega }_k$ непосредственно рассчитывается на k-й итерации.

Алгоритм

• Пусть ${\overrightarrow{x}}_0$ — начальная точка, ${\overrightarrow{r}}_0$ — направление антиградиента и мы пытаемся найти минимум функции $f(\overrightarrow{x})$. Положим ${\overrightarrow{S}}_0={\overrightarrow{r}}_0$ и найдём минимум вдоль направления ${\overrightarrow{S}}_0$. Обозначим точку минимума ${\overrightarrow{x}}_1$.

• Пусть на некотором шаге мы находимся в точке ${\overrightarrow{x}}_k$, и ${\overrightarrow{r}}_k$ — направление антиградиента. Положим ${\overrightarrow{S}}_k={\overrightarrow{r}}_k+{\omega }_k{\overrightarrow{S}}_{k-1}$, где ${\omega }_k$ выбирают либо $\frac{({\overrightarrow{r}}_k,{\overrightarrow{r}}_k)}{({\overrightarrow{r}}_{k-1},{\overrightarrow{r}}_{k-1})}$ (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с $H>0$), либо $max(0,\frac{({\overrightarrow{r}}_k,{\overrightarrow{r}}_k-{\overrightarrow{r}}_{k-1})}{({\overrightarrow{r}}_{k-1},{\overrightarrow{r}}_{k-1})})$ (алгоритм Полака–Рибьера). После чего найдём минимум в направлении $\overrightarrow{S_k}$ и обозначим точку минимума ${\overrightarrow{x}}_{k+1}$. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив ${\omega }_k=0$ и повторив шаг.

Формализация

1. Задаются начальным приближением и погрешностью: ${\overrightarrow{x}}_0,\epsilon ,k=0$
2. Рассчитывают начальное направление: $j=0,{\overrightarrow{S}}_k^j=-\mathrm{\nabla }f({\overrightarrow{x}}_k),{\overrightarrow{x}}_k^j={\overrightarrow{x}}_k$
3. ${\overrightarrow{x}}_k^{j+1}={\overrightarrow{x}}_k^j+\lambda {\overrightarrow{S}}_k^j,\lambda =\arg \underset{\lambda }{min}f({\overrightarrow{x}}_k^j+\lambda {\overrightarrow{S}}_k^j),{\overrightarrow{S}}_k^{j+1}=-\mathrm{\nabla }f({\overrightarrow{x}}_k^{j+1})+\omega {\overrightarrow{S}}_k^j,\omega =\frac{||\mathrm{\nabla }f({\overrightarrow{x}}_k^{j+1})|{|}^2}{||\mathrm{\nabla }f({\overrightarrow{x}}_k^j)|{|}^2}$
   • Если $||{\overrightarrow{S}}_k^{j+1}||<\epsilon$ или $||{\overrightarrow{x}}_k^{j+1}-{\overrightarrow{x}}_k^j||<\epsilon$, то $\overrightarrow{x}={\overrightarrow{x}}_k^{j+1}$ и остановка.
   • Иначе
     • если $(j+1)<n$, то $j=j+1$ и переход к 3;
     • иначе ${\overrightarrow{x}}_{k+1}={\overrightarrow{x}}_k^{j+1},k=k+1$ и переход к 2.

Литература

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга
4. Шаблон:Книга
5. Шаблон:Книга
6. Шаблон:Книга