Участник:Slimper/Песочница

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

Версия от 19:54, 23 ноября 2008; Slimper (Обсуждение | вклад)

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

Содержание

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

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

Пусть задано множество $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_0 = b - Ax_0$

$p_0 = r_0$

$\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} <Ax, x>$

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

Если все вычисления точные, и исходные то метод сходится к решению системы не более чем за $m$ итераций, где $m$ - число различных собственных значений матрицы A. На практике чаще всего используют следующий критерий останова: норма погрешности $r_k$ становится меньше некоторого заданного порога $r_0$ .

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

На каждой итерации метода выполняется $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$ формулы, в кторые не входит матрица А: