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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 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> точной верхней или точной нижней грани ''целевой функции''.
-
Множество точек, на которых достигается нижняя грань целевой функции обозначается <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 = R^n </tex>, то задача оптимизации называется ''безусловной'' (''unconstrained'').
Строка 8: Строка 8:
==Метод сопряжённых направлений==
==Метод сопряжённых направлений==
-
''Метод сопряжённых направлений'' (''conjugate direction method'') первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в <tex>R^n</tex>
+
''Метод сопряжённых направлений'' (''conjugate direction method'') первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в <tex>R^n</tex>
-
==Минимизация квадратичного функционала==
+
==Линейный метод сопряжённых градиентов ==
-
Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации:
+
=== Изложение метода ===
-
<tex>f(x) = \frac{1}{2}<Ax, x> - <b, x> \to inf, \quad x \in R^n</tex> <br/>
+
Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации: <br/>
-
<tex>A</tex> - симметричная положительно определённая матрица размера <tex>n \times n</tex>.
+
<tex>F(x) = \frac{1}{2}<Ax, x> - <b, x> \to inf, \quad x \in R^n</tex> <br/>
-
Такая задача оптимизации называется квадратичной. Функция <tex>f</tex> достигает своей нижней грани в единственной точке <tex>x_*</tex>, определяемой уравнением <tex> Ax_* = b</tex> . Таким образом, данная задача оптимизации сводится к решению линейной системы
+
Здесь <tex>A</tex> - симметричная положительно определённая матрица размера <tex>n \times n</tex>.
-
<tex> Ax = b</tex>
+
Такая задача оптимизации называется квадратичной.
-
=== Общий случай ===
+
Заметим, что <tex>F'(x) = Ax - b</tex>. Условие экстремума функции <tex>F'(x) = 0</tex> эквивалентно системе <tex> Ax - b = 0</tex>
 +
Функция <tex>F</tex> достигает своей нижней грани в единственной точке <tex>x_*</tex>, определяемой уравнением <tex> Ax_* = b</tex> . Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений <tex> Ax = b</tex> <br/>
 +
Идея метода сопряжённых градиентов состоит в следующем: <br/>
 +
Пусть <tex> \{p_k \} _{k = 1}^n </tex> - базис в <tex>R^n </tex> . Тогда для любой точки <tex> x_0 \in R^n </tex> вектор <tex>x_* - x_0</tex> раскладывается по базису <tex>x_* - x_0 = \alpha_1 p_1 + \dots \alpha_n p_n </tex>
 +
Таким образом, <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_k \}_{k = 1}^n </tex> в методе сопряжённых градиентов
 +
В качестве начального приближения <tex> x_0 </tex> выбираем произвольный вектор.
 +
На каждой итерации <tex>\alpha_k</tex> выбираются по правилу: <br/>
 +
::<tex>\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k p_k)</tex>
 +
<br/>
 +
Базисные вектора <tex> \{p_k \} </tex> вычисляются по формулам: <br/>
 +
<tex> p_1 = -F'(x_0) </tex>
 +
<br/>
 +
<tex> p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k} </tex>
 +
<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>
 +
<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> } \\
 +
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} \\
 +
p_{k + 1} = r_{k + 1} + b_k p_k \\
 +
\end{equation*}
 +
</tex>
 +
=== Анализ метода ===
 +
==== Сходимость метода ====
 +
Если все вычисления точные, и исходные то метод сходится к решению системы не более чем за <tex>m</tex> итераций, где
 +
<tex>m</tex> - число различных собственных значений матрицы A. На практике чаще всего используют следующий критерий останова:
 +
норма погрешности <tex>r_k</tex> становится меньше некоторого заданного порога <tex>r_0</tex>.
 +
==== Вычислительная сложность ====
 +
На каждой итерации метода выполняется <tex>O(n^2)</tex> операций. Такое количество операций требуется для вычисления произведения
 +
<tex>Ap_k</tex> - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций.
 +
Суммарная вычислительная сложность метода не превышает <tex>O(n^3)</tex> - так как число итераций не больше n.
 +
== Общий случай ==
 +
Расссматриваем задачу <tex>F(x) \to min, \quad x \in R^n </tex>.
 +
<tex>F(x) </tex> - непрерывно дифференцируемая в R^n функция.
 +
Чтобы получить из метода сопряжённых градиентов метод для решения данной задачи, нужно получить для <tex>p_k, \alpha_k, \beta_k </tex> формулы, в кторые не входит матрица А:
 +
::<tex>\alpha_k = argmin \limits_{\alpha_k} F(x_{k-1} + \alpha_k p_k)</tex>
 +
::<tex> p_{k+1} = - F'(x_{k}) + \beta_{k} p_{k} </tex>
 +
<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{<F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} )>}{<F'(x_k}), F'(x_k)>} </tex>
 +
::<tex> \beta_k = \frac{<F''(x_{k+1} )p_{k},F'(x_{k + 1} )>}{<F''(x_{k})p_k, p_k>} </tex>
 +
 
 +
 
== Литература ==
== Литература ==
-
Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002
+
Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002 <br/>
Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999
Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999

Версия 22:18, 17 ноября 2008

Содержание

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

Пусть задано множество 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 direction method) первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения безусловных задач оптимизации в R^n

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

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

Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации:
F(x) = \frac{1}{2}<Ax, x> - <b, x> \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, если <Bp,q> = 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{ <F'(x_{k}), Ap_k>}{Ap_k p_k}


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

r_0 = b - Ax_0
p_0 = r_0

\begin{equation*} \alpha_k = \frac{ <r_k, r_k> }{ <Ap_k, p_k> } \\ 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} \\ p_{k + 1} = r_{k + 1} + b_k p_k \\ \end{equation*}

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

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

Если все вычисления точные, и исходные то метод сходится к решению системы не более чем за 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{<F'(x_{k + 1} ), F'(x_{k + 1})>}{<F'(x_k), F'(x_k)>}
\beta_k = \frac{<F'(x_{k + 1}), F'(x_k) - F'(x_{k + 1} )>}{<F'(x_k}), F'(x_k)>}
\beta_k = \frac{<F''(x_{k+1} )p_{k},F'(x_{k + 1} )>}{<F''(x_{k})p_k, p_k>}


Литература

Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 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»
Личные инструменты