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