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

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

(Различия между версиями)

Версия 16:52, 24 ноября 2008

Содержание

1 Постановка задачи оптимизации
2 Метод сопряжённых градиентов
3 Линейный метод сопряжённых градиентов
- 3.1 Изложение метода
- 3.2 Анализ метода
  - 3.2.1 Сходимость метода
  - 3.2.2 Вычислительная сложность
4 Нелинейный метод сопряжённых градиентов
- 4.1 Анализ метода
  - 4.1.1 Сходимость метода
  - 4.1.2 Вычислительная сложность
5 Рекомендации программисту
6 Список литературы

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

Пусть задано множество $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$ шагов и справедливы следующие соотношения:

$\langle A p_k, p_m \rangle = 0 \quad \forall k, m, \quad k \neq m$
$\langle F'(x_k), F'(x_m) \rangle = 0 \quad \forall k, m, \quad k \neq m$
$\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$ можно вычислять по одной из трёх формул:

$\beta_k = - \frac{\langle F'(x_{k + 1} ), F'(x_{k + 1}) \rangle}{\langle F'(x_k), F'(x_k) \rangle}$ - Метод Флетчера - Ривса (Fletcher–Reeves method)
$\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)
$\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)$ на каждом шаге метода.