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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Введение: викификация)
(См. также: поправил ссылку)
Строка 203: Строка 203:
== См. также ==
== См. также ==
* [[Метод Нелдера-Мида]]
* [[Метод Нелдера-Мида]]
-
* [[Метод Ньютона. Метод Стеффенсена.]]
+
* [[Метод Ньютона. Метод Стеффенсена]]
== Список литературы ==
== Список литературы ==

Версия 18:32, 17 мая 2010

Содержание

Введение

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

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

Пусть задано множество  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 шагов и справедливы следующие соотношения:

  1. \langle A p_k, p_m \rangle = 0 \quad \forall k, m, \quad k \neq m
  2. \langle F'(x_k), F'(x_m)  \rangle = 0 \quad \forall k, m, \quad k \neq m
  3. \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 можно вычислять по одной из трёх формул:

  1.  \beta_k = - \frac{\langle F'(x_{k} ), F'(x_{k}) \rangle}{\langle F'(x_{k-1}), F'(x_{k-1}) \rangle} - Метод Флетчера - Ривса (Fletcher–Reeves method)
  2.  \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)
  3.  \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) на каждом шаге метода.

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

Если функция F(x) - не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление \alpha_k на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора  p_k перестают указывать направление убывания функции F(x). Тогда на каком-то шаге полагают \beta_k = 0. Совокупность всех номеров k, при которых принимается \beta_k = 0, обозначим за I_0. Номера k \in I_0 называются моментами обновления метода. На практике часто выбирают I_0 = \{n, 2n, 3n, \dots \}, где n - размерность пространства.

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

Для метода Флетчера - Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию F(x):
Теорема.
Пусть  F(x) \in C^1(R^n) и выполняются следующие условия:

  1.  \alpha_k удовлетворяет строгим условиям Вольфа:
    1.  F(x_{k -1} + \alpha_k p_k ) \leq F(x_{k - 1}) +  c_1 \alpha_k \langle F'(x_{k - 1}), p_k \rangle
    2.  | \langle F'(x_{k -1} + \alpha_k p_k), p_k \rangle  \leq c_2 |\langle F'(x_{k - 1}), p_k \rangle| где  0 < c_1 < c_2 < 1/2
  2. Множество  M = \{ x | F(x) \leq F(x_0) \} ограничено
  3. Производная F'(x) удовлетворяет условию Липшица с константой L в некоторой окрестности  N

множества M: ||F'(x_1) - F'(x_2)|| \leq L ||x_1 - x_2|| \qquad \forall x_1, x_2 \in N .
Тогда

 \lim \limits_{k \to \infty} inf ||F'(x_k)| = 0

Для метода Полака-Райбера доказана сходимость в предположении, что F(x) - строго выпуклая функция. В общем случае доказать сходимость метода Полака - Райбера невозможно. Напоротив, верна следующая теорема:
Теорема.
Предположим, что в методе Полака-Райбера значения \alpha_k на каждом шаге вычисляются точно. Тогда существует функция F \: R^3 \mapsto R, \quad F(x) \in C^2(R^3), и начальное приближение x_0 , такие что \exists \delta > 0, \forall k = 0, 1, 2, ... \quad ||f(x_k)|| > \delta.

Тем не менее, на практике метод Полака-Райбера работает лучше.
Наиболее распространённые критерии останова на практике: Норма градиента становится меньше некоторого порога
Значение функции в течении m последовательных итераций почти не изменилось

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

На каждой итерации методов Полака-Райбера или Флетчера-Ривса по одному разу вычисляются функция F(x) и её градиент F'(x), решается задача одномерной оптимизации F(x_{k - 1} + \alpha_k p_k) \to min \limits_{\alpha_k \geq 0} . Таким образом, сложность одного шага метода сопряжённых градиентов имеет тот же порядок, что и сложность шага метода скорейшего спуска. На практике метод сопряжённых градиентов показывает лучшую скорость сходимости.

Числовой пример

Будем искать методом сопряжённых градиентов минимум функции F(x_1, x2) = (x_1 - 5)^2 (x_2 - 4)^2 + (x_1 - 5)^2 + (x_2 - 4)^2 + 1. Минимум этой фнкции равен 1 и достигается в точке (5, 4). Сравним на примере этой функции методы Полака-Райбера и Флетчера-Ривса. Итерации в обоих методах прекращаются, когда на текущем шаге квадрат нормы градиента становится меньше \varepsilon. Для выбора  \alpha_k используется метод золотого сечения

 \varepsilon Метод Флетчера - Ривса Метод Полака - Райбера
Число итераций Найденное решение Значение функции Число итераций Найденное решение Значение функции
0.01 18 (5.01382198,3.9697932) 1.00110367 15 (5.03942877,4.00003512) 1.00155463
0.001 20 (5.01056482,3.99018026) 1.00020805 18 (4.9915894,3.99999044) 1.00007074
0.0001 24 (4.9979991,4.00186173) 1.00000747 20 (5.00336181,4.0000018) 1.0000113
0.00001 25 (4.99898277,4.00094645) 1.00000193 22 (4.99846808,3.99999918) 1.00000235
0.00001 29 (4.99974658,4.0002358) 1.00000012 26 (4.99955034,3.99999976) 1.0000002

Рекомендации программисту

Реализовано два варианта метода сопряжённых градиентов: для минимизации квадратичного функционала, и для минимизации произвольной функции. В первом случае метод реализуется функцией
vector<double> FindSolution(matrix<double> A, vector<double> b)
Здесь A и b - матрица и вектор, фигурирющие в определении квадратичной задачи оптимизации.
Для минимизации произвольного функционала можно использовать одну из двух функций:
vector<double> FletcherRievesMethod(int spaceSize, Function F, vector<double> (*GradF) (vector<double>))
vector<double> PolakRibiereMethod(int spaceSize, Function F, vector<double> (*GradF) (vector<double>))
Параметры для обеих функций совпадают и имеют следующий смысл:
spaceSize - размерность пространства( число переменных, от которых зависит минимизируемый функционал)
F - указатель на минимизируемую функцию. Функция должна иметь вид double <имя функции>( vector<double>)
GradF - указатель на функцию, вычисляющую градиент минимизируемого функционала
Оба метода используют вспомогательную функцию для решения задачи одномерной оптимизации. В программе реализована одномерная оптимизация методом золотого сечения.

Исходный код программ: Линейный метод сопряженных градиентов, исходный код [1кб]
Нелинейный метод сопряжённых градиентов, исходный код [1кб]
При написании программ использовалась библиотека Boost, скачать которую можно по адресу http://www.boost.org

Заключение

В методе сопряжённых градиентов используется информация только о линейной части приращения в точке, как и в методах градиентного спуска. При этом метод сопряжённых градиентов позволяет решать квадратичные задачи за конечное число шагов. На многих других задачах метод сопряжённого градиента также превосходит метод градиентного спуска. Сходимость метода градиентов существенно зависит от того, насколько точно решается задача одномерной оптимизации F(x_{k - 1} + \alpha_k p_k) \to min \limits_{\alpha_k \geq 0} . Возможные зацикливания метода устраняются с помощью обновлений. Тем не менее, если метод попадёт в локальный минимум функции, скорее всего, ему не удастся из него выбраться.

См. также

Список литературы

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