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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод сопряженных градиентовметод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в \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})\!.

Logo arte.jpg Теорема (о существовании).
Существует хотя бы одна система 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.

Случай квадратичной функции[править | править исходный текст]

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

Литература[править | править исходный текст]

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