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

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

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

Версия 19:54, 23 ноября 2008

Содержание

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

$\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}$

$\beta_k = \frac{\langle F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} ) \rangle}{\langle F'(x_k}), F'(x_k) \rangle}$

$\beta_k = \frac{\langle F''(x_{k+1} )p_{k},F'(x_{k + 1}) \rangle}{\langle F''(x_{k})p_k, p_k \rangle}$

Литература

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

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Slimper/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 1: / Строка 1: @@
 ==Постановка задачи оптимизации==
-Пусть задано множество <tex> X \subset R^n </tex> и на этом множестве определена ''целевая функция'' (''objective function'') <tex>f : R^n \mapsto R</tex>. Задача оптимизации состоит в нахождении на множестве <tex>X</tex>  точной верхней или точной нижней грани ''целевой функции''.
+Пусть задано множество <tex> X \subset R^n </tex> и на этом множестве определена ''целевая функция'' (''objective function'') <tex>f : R^n \mapsto R</tex>. Задача оптимизации состоит в нахождении на множестве <tex>X</tex>  точной верхней или точной нижней грани ''целевой функции''. <br/>
 Множество точек, на которых достигается нижняя грань целевой функции обозначается  <tex>X_* </tex>. <br/>
-::<tex>X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \} </tex>
+::<tex>X_* = \{x \in X| f(x) = inf \limits_{x \in X} f(x) \} </tex> <br/>
-<br/>
 Если <tex> X = R^n </tex>, то задача оптимизации называется ''безусловной'' (''unconstrained'').
 Если <tex> X \neq R^n </tex>, то задача оптимизации называется ''условной'' (''constrained'').
-==Метод сопряжённых направлений==
+==Метод сопряжённых градиентов==
-''Метод сопряжённых направлений'' (''conjugate direction method'')  первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в <tex>R^n</tex>
+''Метод сопряжённых градиентов'' (''conjugate gradient method'')  первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения задач безусловной оптимизации в <tex>R^n</tex>
 ==Линейный метод сопряжённых градиентов ==
 === Изложение метода ===
 Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации: <br/>
-<tex>F(x) = \frac{1}{2}<Ax, x> - <b, x> \to inf, \quad x \in R^n</tex> <br/>
+<tex>F(x) = \frac{1}{2} \langle Ax, x \rangle - \langle b, x \rangle \to inf, \quad x \in R^n</tex> <br/>
 Здесь <tex>A</tex> - симметричная положительно определённая матрица размера <tex>n \times n</tex>.
 Такая задача оптимизации называется квадратичной.
@@ Строка 21: / Строка 21: @@
 Таким образом, <tex>x_*</tex> представимо в виде <br/>
 ::<tex>x_* = x_0 + \alpha_1 p_1 + \dots \alpha_n p_n </tex>
 Каждое следующее приближение вычисляется по формуле: <br/>
 ::<tex>x_k = x_0 + \alpha_1 p_1 + \dots \alpha_n p_k </tex> <br/>
-Два вектора <tex>p</tex> и <tex>q</tex> называются ''сопряжёнными'' относительно симметричной матрицы B, если <tex> <Bp,q> = 0</tex>
+'''Определение.''' Два вектора <tex>p</tex> и <tex>q</tex> называются ''сопряжёнными'' относительно симметричной матрицы B, если <tex> \langle Bp,q \rangle = 0</tex>
 Опишем способ построения базиса <tex> \{p_k \}_{k = 1}^n </tex> в методе  сопряжённых градиентов
@@ Строка 37: / Строка 36: @@
 <br/>
 Коэффициенты <tex>\beta_k</tex> выбираются так, чтобы векторы <tex>p_k</tex> и <tex>p_{k + 1} </tex>были сопряжёнными относительно А. <br/>
-::<tex>\beta_k =  \frac{ <F'(x_{k}), Ap_k>}{Ap_k p_k} </tex>
+::<tex>\beta_k =  \frac{ \langle F'(x_{k}), Ap_k \rangle}{ \langle Ap_k,  p_k \rangle} </tex>
 <br/>
-Если обозначить за <tex>r_k = b - Ax_k = -f'(x_{k})</tex> , то после нескольких упрощений получим окончательные формулы, используемые применении метода сопряжённых градиентов на практике: <br/>
+Если обозначить за <tex>r_k = b - Ax_k = -f'(x_{k})</tex> , то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике: <br/>
 ::<tex>r_0 = b - Ax_0</tex> <br/>
 ::<tex> p_0 = r_0 </tex> <br/>
 <tex>
 \begin{equation*}
-\alpha_k  = \frac{ <r_k, r_k> }{ <Ap_k, p_k> } \\
+\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{ < r_{k + 1}, r_{k + 1} > }{r_k r_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*}
 </tex>
+<br/>
 === Анализ метода ===
+Для метода сопряжённых градиентов справедлива следующая теорема:
+Пусть <tex>F(x) = \frac{1}{2} <Ax, x> </tex>
 ==== Сходимость метода ====
 Если все вычисления точные, и исходные то метод сходится к решению системы не более чем за <tex>m</tex> итераций, где
@@ Строка 62: / Строка 64: @@
 == Общий  случай ==
 Расссматриваем задачу <tex>F(x) \to min, \quad x \in R^n </tex>.
-<tex>F(x) </tex> - непрерывно дифференцируемая в R^n функция.
+<tex>F(x) </tex> - непрерывно дифференцируемая в <tex>R^n </tex> функция.
 Чтобы получить из метода сопряжённых градиентов метод для решения данной задачи, нужно получить для <tex>p_k, \alpha_k, \beta_k </tex> формулы, в кторые не входит матрица А:
 ::<tex>\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k  p_k)</tex>
@@ Строка 68: / Строка 70: @@
 <tex> \beta_k </tex> можно вычислять по одной из трёх формул:
-::<tex> \beta_k = - \frac{<F'(x_{k + 1} ), F'(x_{k + 1})>}{<F'(x_k), F'(x_k)>} </tex>
+::<tex> \beta_k = - \frac{\langle F'(x_{k + 1} ), F'(x_{k + 1}) \rangle}{\langle F'(x_k), F'(x_k) \rangle} </tex>
-::<tex> \beta_k = \frac{<F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} )>}{<F'(x_k}), F'(x_k)>} </tex>
+::<tex> \beta_k = \frac{\langle F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} ) \rangle}{\langle F'(x_k}), F'(x_k) \rangle} </tex>
-::<tex> \beta_k = \frac{<F''(x_{k+1} )p_{k},F'(x_{k + 1} )>}{<F''(x_{k})p_k, p_k>} </tex>
+::<tex> \beta_k = \frac{\langle F''(x_{k+1} )p_{k},F'(x_{k + 1}) \rangle}{\langle F''(x_{k})p_k, p_k \rangle} </tex>