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

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

Перейти к: навигация, поиск

Содержание

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

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