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