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

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

Версия от 15:57, 2 сентября 2010; Валентин Голодов (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Введение
2 Постановка задачи оптимизации
3 Метод сопряжённых градиентов для квадратичного функционала
4 Метод сопряжённых градиентов в общем случае
- 4.1 Анализ метода
  - 4.1.1 Сходимость метода
  - 4.1.2 Вычислительная сложность
- 4.2 Числовой пример
5 Рекомендации программисту
6 Заключение
7 См. также
8 Список литературы

Введение

Метод сопряжённых градиентов — итерационный метод для безусловной оптимизации в многомерном пространстве. Основным достоинством метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов. Поэтому, сначала описывается метод сопряжённых градиентов для оптимизации квадратичного функционала, выводятся итерационные формулы, приводятся оценки скорости сходимости. После этого показывается, как метод сопряжённых обобщается для оптимизации произвольного функционала, рассматриваются различные варианты метода, обсуждается сходимость.

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

Пусть задано множество $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).

Метод сопряжённых градиентов для квадратичного функционала

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

Рассмотрим следующую задачу оптимизации:

$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.

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

Применим метод сопряжённых градиентов для решения системы $Ax = b$ , где
$A = \begin{bmatrix} 3 & 4 & 0 \\ \\ 4 & -3 & 0 \\ \\ 0 & 0 & 5 \end{bmatrix}, \qquad b = \begin{bmatrix} 1 \\ \\ \\ \\ 5 \\ \\ 9 \end{bmatrix}$
C помощью метода сопряжённых градиентов решение этой системы $x =\begin{bmatrix} 0.92 \\ \\ -0.44 \\ \\ 1.80 \end{bmatrix},$ получается за две итерации. Собственные числа матрицы $A$ - 5, 5, -5 - среди них два различных, поэтому, согласно теоретической оценке число итераций не могло превышать двух

Заключение

Метод сопряжённых градиентов - один из наиболее эффективных методов решения СЛАУ с положительно определённой матрицей. Метод гарантирует сходимость за конечное число шагов, а нужная точность может быть достигнута значительно раньше. Основная проблема заключается в том, что из-за накопления погрешностей может нарушаться ортогональность базисных веторов $p_k$ , что ухудшает сходимость

Метод сопряжённых градиентов в общем случае

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

$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} ), F'(x_{k}) \rangle}{\langle F'(x_{k-1}), F'(x_{k-1}) \rangle}$ - Метод Флетчера - Ривса (Fletcher–Reeves method)
$\beta_k = \frac{\langle F'(x_{k}), F'(x_k) - F'(x_{k-1}} ) \rangle}{\langle F'(x_{k - 1}), F'(x_{k - 1}) \rangle}$ - Метод Полака - Райбера (Polak–Ribi`ere method)
$\beta_k = \frac{\langle F''(x_k) p_k, F'(x_k) \rangle}{\langle F''(x_{k - 1})p_k, p_k \rangle}$

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