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

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Постановка задачи оптимизации

Пусть задано множество  X \subset R^n и на этом множестве определена целевая функция (objective function) f : R^n \mapsto R. Задача оптимизации состоит в нахождении на множестве X точной верхней или точной нижней грани целевой функции.
Множество точек, на которых достигается нижняя грань целевой функции обозначается X_* .

X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \}

Если  X = R^n , то задача оптимизации называется безусловной (unconstrained). Если  X \neq R^n , то задача оптимизации называется условной (constrained).

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

Метод сопряжённых градиентов (conjugate gradient method) первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения задач безусловной оптимизации в R^n

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

Изложение метода

Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации:

F(x) = \frac{1}{2} \langle Ax, x \rangle - \langle b, x \rangle \to inf, \quad x \in R^n

Здесь A - симметричная положительно определённая матрица размера n \times n. Такая задача оптимизации называется квадратичной. Заметим, что F'(x) = Ax - b. Условие экстремума функции F'(x) = 0 эквивалентно системе  Ax - b = 0 Функция F достигает своей нижней грани в единственной точке x_*, определяемой уравнением  Ax_* = b . Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений  Ax = b
Идея метода сопряжённых градиентов состоит в следующем:
Пусть  \{p_k \} _{k = 1}^n - базис в R^n . Тогда для любой точки  x_0 \in R^n вектор x_* - x_0 раскладывается по базису x_* - x_0 = \alpha_1 p_1 + \dots \alpha_n p_n Таким образом, x_* представимо в виде

x_* = x_0 + \alpha_1 p_1 + \dots \alpha_n p_n

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

x_k = x_0 + \alpha_1 p_1 + \dots \alpha_n p_k

Определение. Два вектора p и q называются сопряжёнными относительно симметричной матрицы B, если  \langle Bp,q \rangle = 0

Опишем способ построения базиса  \{p_k \}_{k = 1}^n в методе сопряжённых градиентов В качестве начального приближения  x_0 выбираем произвольный вектор. На каждой итерации \alpha_k выбираются по правилу:

\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k  p_k)

Базисные вектора  \{p_k \} вычисляются по формулам:

 p_1 = -F'(x_0)
 p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k}

Коэффициенты \beta_k выбираются так, чтобы векторы p_k и p_{k + 1} были сопряжёнными относительно А.

\beta_k =  \frac{ \langle F'(x_{k}), Ap_k \rangle}{ \langle Ap_k,  p_k \rangle}


Если обозначить за r_k = b - Ax_k = -f'(x_{k}) , то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике:

r_1 = b - Ax_0
 p_1 = r_1

\begin{equation*}
\alpha_k  = \frac{ \langle r_k, r_k \rangle }{ \langle Ap_k, p_k \rangle } \\
x_{k + 1} = x_k + \alpha_k p_k \\
r_{k + 1} = r_k - \alpha_k Ap_k \\
\beta_k = \frac{ \langle r_{k + 1}, r_{k + 1} \rangle }{\langle r_k,  r_k \rangle} \\
p_{k + 1} = r_{k + 1} + b_k p_k \\ 
\end{equation*}

Анализ метода

Для метода сопряжённых градиентов справедлива следующая теорема:
Теорема Пусть F(x) = \frac{1}{2}  \langle Ax, x \rangle - \langle b, x \rangle , где A - симметричная положительно определённая матрица размера n. Тогда метод сопряжённых градиентов сходится не более чем за n шагов и справедливы следующие соотношения:

  1. \langle A p_k, p_m \rangle = 0 \quad \forall k, m, \quad k \neq m
  2. \langle F'(x_k), F'(x_m)  \rangle = 0 \quad \forall k, m, \quad k \neq m
  3. \langle F'(x_k),p_m)  \rangle = 0 \quad \forall k, m, \quad m < k

Сходимость метода

Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за n итераций, гдеn - размерность системы. Более тонкий анализ показывает, что число итераций не превышает m, где m - число различных собственных значений матрицы A. Для оценки скорости сходимости верна следующая (довольно грубая) оценка:

 || x_k - x_* ||_A \leq  ( \frac{ \sqrt  {\kappa(A) } - 1}{ \sqrt { \kappa(A) } + 1} ) || x_0 - x_* ||_A , где

 \kappa(A) = || A || \: || A^{-1} || = \lambda_1 / \lambda_n . Она позволяет оценить скорость сходимости, если известны оценки для максимального \lambda_1 и минимального \lambda_n собственных значений матрицы A На практике чаще всего используют следующий критерий останова:

|| r_k || < \eps.

Вычислительная сложность

На каждой итерации метода выполняется O(n^2) операций. Такое количество операций требуется для вычисления произведения Ap_k - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций. Суммарная вычислительная сложность метода не превышает O(n^3) - так как число итераций не больше n.

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

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

F(x) \to min, \quad x \in R^n .

F(x) - непрерывно дифференцируемая в R^n функция. Чтобы модифицировать метод сопряжённых градиентов для решения этой задачи, необходимо получить для p_k, \alpha_k, \beta_k формулы, в кторые не входит матрица А:

\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k  p_k)
 p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k}

 \beta_k можно вычислять по одной из трёх формул:

  1.  \beta_k = - \frac{\langle F'(x_{k + 1} ), F'(x_{k + 1}) \rangle}{\langle F'(x_k), F'(x_k) \rangle} - Метод Флетчера - Ривса (Fletcher–Reeves method)
  2.  \beta_k = \frac{\langle F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} ) \rangle}{\langle F'(x_k), F'(x_k) \rangle} - Метод Полака - Райбера (Polak–Ribi`ere method)
  3.  \beta_k = \frac{\langle F''(x_{k+1} )p_{k},F'(x_{k + 1}) \rangle}{\langle F''(x_{k})p_k, p_k \rangle}

Если функция F(x) - квадратичная и строго выпуклая, то все три формулы дают одинаковый результат. Если F(x) - произвольная функция, то каждой из формул cоответствует своя модификация метода сопряжённых градиентов. Третья формула используется редко, так как она требует, чтобы функция F(x) \in C^2(R^n) и вычисления гессиана функции F(x) на каждом шаге метода.

Анализ метода

Если функция F(x) - не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление \alpha_k на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора  p_k перестают указывать направление убывания функции F(x). Тогда на какои-то шаге полагают \beta_k = 0. Совокупность всех номеров k, при которых принимается \beta_k = 0 обозначим за I_0. Номера k \in I_0 называются моментами обновления метода. На практике часто выбирают I_0 = \{n, 2n, 3n, \dots \}, где n - размерность пространства.

Сходимость метода

Для метода Флетчера - Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию F(x):
Теорема.
Пусть  F(x) \in C^1(R^n) и выполняются следующие условия:

  1.  \alpha_k удовлетворяет строгим условиям Вольфа:
    1.  F(x_{k -1} + \alpha_k p_k ) \leq F(x_{k - 1}) +  c_1 \alpha_k \langle F'(x_{k - 1}), p_k \rangle
    2.  | \langle F'(x_{k -1} + \alpha_k p_k), p_k \rangle  \leq c_2 |\langle F'(x_{k - 1}), p_k \rangle| где  0 < c_1 < c_2 < 1/2
  2. Множество  M = \{ x | F(x) \leq F(x_0) \} ограничено
  3. Производная F'(x) удовлетворяет условию Липшица с константой L в некоторой окрестности  N

множества M: ||F'(x_1) - F'(x_2)|| \leq L ||x_1 - x_2|| \qquad \forall x_1, x_2 \in N .
Тогда

 \lim \limits_{k \to \infty} inf ||F'(x_k)| = 0

Для метода Полака-Райбера доказана сходимость в предположении, что F(x) - строго выпуклая функция. В общем случае доказать сходимость метода Полака - Райбера невозможно. Напоротив, верна следующая теорема:
Теорема Предположим, что в методе Полака-Райбера значения \alpha_k на каждом шаге вычисляются точно. Тогда существует функция F \: R^3 \mapsto R, \quad F(x) \in C^2(R^3), и начальное приближение x_0 , такие что \exists \delta > 0, \forall k = 0, 1, 2, ... \quad ||f(x_k)|| > \delta.

Тем не менее, на практике метод Полака-Райбера работает лучше.
Наиболее распространённые критерии останова на практике: Норма градиента становится меньше некоторого порога
Значение функции в течении m последовательных итераций почти не изменилось

Вычислительная сложность

На каждой итерации методов Полака-Райбера или Флетчера-Ривса по одному разу вычисляются функция F(x) и её градиент F'(x), решается задача одномерной оптимизации F(x_{k - 1} + \alpha_k p_k) \to min \limits_{\alpha_k \geq 0} . Таким образом, сложность одного шага метода споряжённых градиентов имеет тот же порядок что и сложность шага метода скорейшего спуска. На практике, метод сопряжённых градиентов показывает лучшую скорость сходимости.

Численные примеры

Рекомендации программисту

Линейный метод сопряженных градиентов, исходный код [1кб]
Нелинейный метод сопряжённых градиентов, исходный код [1кб]
Библиотека алгоритмов линейной алгебры [180кб]


Список литературы

  • Васильев Ф. П.   Методы оптимизации - Издательство «Факториал Пресс», 2002
  • Nocedal J., Wright S.J.   Numerical Optimization ,Springer, 1999
Личные инструменты