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