Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов.
Содержание |
Определим терминологию:
Пусть .
Введём на целевую функцию .
Вектора называются сопряжёнными, если:
где — матрица Гессе .
Теорема (о существовании). Существует хотя бы одна система сопряжённых направлений для матрицы , т.к. сама матрица (её собственные вектора) представляет собой такую систему. |
Пусть
Тогда .
Определим направление
так, чтобы оно было сопряжено с :
Разложим в окрестности и подставим :
Транспонируем полученное выражение и домножаем на справа:
В силу непрерывности вторых частных производных . Тогда:
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :
На k-й итерации имеем набор .
Тогда следующее направление вычисляется по формуле:
Это выражение может быть переписано в более удобном итеративном виде:
где непосредственно рассчитывается на k-й итерации.
Теорема. Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за шагов, по одному в каждом направлении, причём порядок несущественен. |
Методы оптимизации | |
---|---|
Одномерные | Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск |
Прямые методы | Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка |
Первого порядка | Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта |
Второго порядка | Метод Ньютона • Метод Ньютона — Рафсона |
Стохастические | Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц |
Методы линейного программирования |
Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов |
Методы нелинейного программирования |
Последовательное квадратичное программирование |
Метод сопряжённых градиентов.