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