Метод сопряжённых градиентов — метод нахождения локального экстремума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в
минимум находится не более чем за
шагов.
Основные понятия
Определим терминологию:
Пусть
.
Введём на
целевую функцию
.
Векторы
называются сопряжёнными, если:
-
-
где
— матрица Гессе
.
|
Теорема (о существовании). Существует хотя бы одна система
сопряжённых направлений для матрицы
, т.к. сама матрица
(её собственные вектора) представляет собой такую систему. |
|
Обоснование метода
К-я итерация
На k-й итерации имеем набор
.
Тогда следующее направление вычисляется по формуле:
-
Это выражение может быть переписано в более удобном итеративном виде:
-
где
непосредственно рассчитывается на k-й итерации.
Алгоритм
- Пусть
— начальная точка,
— направление антиградиента и мы пытаемся найти минимум функции
. Положим
и найдём минимум вдоль направления
. Обозначим точку минимума
.
- Пусть на некотором шаге мы находимся в точке
, и
— направление антиградиента. Положим
, где
выбирают либо
(стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с
), либо
(алгоритм Полака–Райбера). После чего найдём минимум в направлении
и обозначим точку минимума
. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив
и повторив шаг.
Формализация
- Задаются начальным приближением и погрешностью:
- Рассчитывают начальное направление:
-
- Если
или
, то
и остановка.
- Иначе
- если
, то
и переход к 3;
- иначе
и переход к 2.
Случай квадратичной функции
|
Теорема. Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за
шагов, по одному в каждом направлении, причём порядок несущественен. |
|
Литература
- Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю. А.,Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .