Метод сопряжённых градиентов
Материал из MachineLearning.
Содержание |
Постановка задачи оптимизации
Пусть задано множество и на этом множестве определена целевая функция (objective function) . Задача оптимизации состоит в нахождении на множестве точной верхней или точной нижней грани целевой функции.
Множество точек, на которых достигается нижняя грань целевой функции обозначается .
Если , то задача оптимизации называется безусловной (unconstrained). Если , то задача оптимизации называется условной (constrained).
Метод сопряжённых градиентов
Метод сопряжённых градиентов (conjugate gradient method) первоначально был разработан для решения систем линейных уравнений с положительно определённой матрицей. Позже этот метод обобщили для решения задач безусловной оптимизации в
Линейный метод сопряжённых градиентов
Изложение метода
Рассмотрим сначала метод сопряжённых градиентов для решения следующей задачи оптимизации:
Здесь - симметричная положительно определённая матрица размера .
Такая задача оптимизации называется квадратичной.
Заметим, что . Условие экстремума функции эквивалентно системе
Функция достигает своей нижней грани в единственной точке , определяемой уравнением . Таким образом, данная задача оптимизации сводится к решению системы линейных уравнений
Идея метода сопряжённых градиентов состоит в следующем:
Пусть - базис в . Тогда для любой точки вектор раскладывается по базису
Таким образом, представимо в виде
Каждое следующее приближение вычисляется по формуле:
Определение. Два вектора и называются сопряжёнными относительно симметричной матрицы B, если
Опишем способ построения базиса в методе сопряжённых градиентов
В качестве начального приближения выбираем произвольный вектор.
На каждой итерации выбираются по правилу:
Базисные вектора вычисляются по формулам:
Коэффициенты выбираются так, чтобы векторы и были сопряжёнными относительно А.
Если обозначить за , то после нескольких упрощений получим окончательные формулы, используемые при применении метода сопряжённых градиентов на практике:
Анализ метода
Для метода сопряжённых градиентов справедлива следующая теорема:
Теорема
Пусть , где - симметричная положительно определённая матрица размера . Тогда метод сопряжённых градиентов сходится не более чем за шагов
и справедливы следующие соотношения:
Сходимость метода
Если все вычисления точные, и исходные данные точны то метод сходится к решению системы не более чем за итераций, где - размерность системы. Более тонкий анализ показывает, что число итераций не превышает , где - число различных собственных значений матрицы A.
Для оценки скорости сходимости верна следующая (довольно грубая) оценка:
- , где
. Она позволяет оценить скорость сходимости, если известны оценки для максимального и минимального собственных значений матрицы На практике чаще всего используют следующий критерий останова:
- .
Вычислительная сложность
На каждой итерации метода выполняется операций. Такое количество операций требуется для вычисления произведения - это самая трудоёмкая процедура на каждой итерации. Отальные вычисления требуют O(n) операций. Суммарная вычислительная сложность метода не превышает - так как число итераций не больше n.
Численный пример
Применим метод сопряжённых градиентов для решения системы , где
C помощью метода сопряжённых градиентов решение этой системы
получается за две итерации. Собственные числа матрицы - 5, 5, -5 - среди них два различных, поэтому, согласно теоретической оценке, число итераций не могло превышать двух
Заключение
Метод сопряжённых градиентов - один из наиболее эффективных методов решения СЛАУ с положительно определённой матрицей. Метод гарантирует сходимость за конечное число шагов, а нужная точность может быть достигнута значительно раньше. Основная проблема заключается в том, что из-за накопления погрешностей может нарушаться перпендикулярность базисных веторов , что ухудшает сходимость
Нелинейный метод сопряжённых градиентов
Расссмотрим теперь модификацию метода сопряжённых градиентов, для случая, когда минимизируемый функционал не является квадратичным: Будем решать задачу:
- .
- непрерывно дифференцируемая в функция. Чтобы модифицировать метод сопряжённых градиентов для решения этой задачи, необходимо получить для формулы, в кторые не входит матрица А:
можно вычислять по одной из трёх формул:
- - Метод Флетчера - Ривса (Fletcher–Reeves method)
- - Метод Полака - Райбера (Polak–Ribi`ere method)
Если функция - квадратичная и строго выпуклая, то все три формулы дают одинаковый результат. Если -
произвольная функция, то каждой из формул cоответствует своя модификация метода сопряжённых градиентов. Третья формула используется редко, так как она требует, чтобы функция и вычисления гессиана функции на каждом шаге метода.
Анализ метода
Если функция - не квадратичная, метод сопряжённых градиентов может и не сходиться за конечное число шагов. Кроме того, точное вычисление на каждом шаге возможно только в редких случаях. Поэтому накопление погрешностей приводит к тому, что вектора перестают указывать направление убывания функции . Тогда на какои-то шаге полагают . Совокупность всех номеров , при которых принимается обозначим за . Номера называются моментами обновления метода. На практике часто выбирают , где - размерность пространства.
Сходимость метода
Для метода Флетчера - Ривса существует теорема о сходимости, накладывающая не слишком жёсткие условия на минимизируемую функцию :
Теорема.
Пусть и выполняются следующие условия:
- удовлетворяет строгим условиям Вольфа:
-
- где
-
- Множество ограничено
- Производная удовлетворяет условию Липшица с константой в некоторой окрестности
множества M: .
Тогда
Для метода Полака-Райбера доказана сходимость в предположении, что - строго выпуклая функция. В общем случае доказать сходимость метода Полака - Райбера невозможно. Напоротив, верна следующая теорема:
Теорема
Предположим, что в методе Полака-Райбера значения на каждом шаге вычисляются точно. Тогда
существует функция , и начальное приближение , такие что
.
Тем не менее, на практике метод Полака-Райбера работает лучше.
Наиболее распространённые критерии останова на практике:
Норма градиента становится меньше некоторого порога
Значение функции в течении m последовательных итераций почти не изменилось
Вычислительная сложность
На каждой итерации методов Полака-Райбера или Флетчера-Ривса по одному разу вычисляются функция и её градиент , решается задача одномерной оптимизации . Таким образом, сложность одного шага метода споряжённых градиентов имеет тот же порядок что и сложность шага метода скорейшего спуска. На практике, метод сопряжённых градиентов показывает лучшую скорость сходимости.
Рекомендации программисту
Линейный метод сопряженных градиентов, исходный код [1кб]
Нелинейный метод сопряжённых градиентов, исходный код [1кб]
Библиотека алгоритмов линейной алгебры [180кб]
Список литературы
- Васильев Ф. П. Методы оптимизации - Издательство «Факториал Пресс», 2002
- Nocedal J., Wright S.J. Numerical Optimization ,Springer, 1999