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

Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в $\mathbb{R}^n$ минимум находится за $n$ шагов.

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

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

Пусть $\vec{S_1},\ldots,\vec{S_n} \in \mathbb{X} \subset \mathbb{R}^n\!$.

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

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

• $\vec{S_i}^T H \vec{S_j}=0, \quad i\neq j, \quad i,j=1,\ldots,n\!$
• $\vec{S_i}^T H \vec{S_i}\geqslant 0, \quad i=1,\ldots,n\!$
  

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

Теорема (о существовании). Существует хотя бы одна система $n\!$ сопряжённых направлений для матрицы $H\!$, т.к. сама матрица $H\!$ (её собственные вектора) представляет собой такую систему.

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

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

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

Пусть $\vec{S_0}=-\nabla f(\vec{x_0})\qquad (1)\!$

Тогда $\vec{x_1}=\vec{x_0}+\lambda_1 \vec{S_0} \qquad \!$.

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

$\vec{S_1}=-\nabla f(\vec{x_1})+\omega_1 \vec{S_0}\ \qquad (2)\!$

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

$\vec{S_0}^T H \vec{S_1}=0 \qquad (3)\!$

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

$\nabla f(\vec{x_1})-\nabla f(\vec{x_0})=H \, (\vec{x_1}-\vec{x_0})=\lambda_1 H \vec{S_0}\!$

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

$(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}=\lambda_1 \vec{S_0}^T H^T H^{-1}\!$

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

$\vec{S_0}^T=\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}}{\lambda_1}\!$

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

$\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}H\vec{S_1}}{\lambda_1}=0\!$

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

$(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T (-\nabla f(\vec{x_1})-\omega_1\nabla f(\vec{x_0})))=0\qquad (4)\!$

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

$(\nabla f(\vec{x_0}),\nabla f(\vec{x_1}))=0\!$

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

$\omega_1=\frac{||\nabla f(\vec{x_1})||^2}{||\nabla f(\vec{x_0})||^2}\!$

К-я итерация

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

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

$\vec{S_k}=-\nabla f(\vec{x_k}) - \|\nabla f(\vec{x_k})\|^2 {\cdot} \left( \frac{\nabla f(\vec{x}_{k-1})}{\|\nabla f(\vec{x}_{k-1})\|^2} + \ldots + \frac{\nabla f(\vec{x_0})}{\|\nabla f(\vec{x}_0)\|^2} \right)\!$

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

$\vec{S_k}=-\nabla f(\vec{x_k})+\omega_k \vec{S}_{k-1},\qquad \omega_i=\frac{\|\nabla f(\vec{x_i})\|^2}{\|\nabla f(\vec{x}_{i-1})\|^2},\!$

где $\omega_k\!$ непосредственно рассчитывается на k-й итерации.

Алгоритм

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

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

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

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

Случай квадратичной функции

Теорема. Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за $n$ шагов, по одному в каждом направлении, причём порядок несущественен.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.