Метод сопряжённых градиентов | это... Что такое Метод сопряжённых градиентов? (original) (raw)

Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в \mathbb{R}^n минимум находится за n шагов.

Содержание

Основные понятия

Определим терминологию:

Пусть \vec{S_1},\ldots,\vec{S_n} \in \mathbb{X} \subset \mathbb{R}^n\!.

Введём на \mathbb{X}\! целевую функцию f(\vec{x})\in \mathrm{C^2}(\mathbb{X})\!.

Векторы \vec{S_1},\ldots,\vec{S_n}\! называются сопряжёнными, если:

где H\! — матрица Гессе f(\vec{x})\!.

Обоснование метода

Нулевая итерация

Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.

Пусть \vec{S_0}=-\nabla f(\vec{x_0})\qquad (1)\!

Тогда \vec{x_1}=\vec{x_0}+\lambda_1 \vec{S_0} \qquad \!.

Определим направление

\vec{S_1}=-\nabla f(\vec{x_1})+\omega_1 \vec{S_0}\ \qquad (2)\!

так, чтобы оно было сопряжено с \vec{S_0}\!:

\vec{S_0}^T H \vec{S_1}=0 \qquad (3)\!

Разложим \nabla f(\vec{x})\! в окрестности \vec{x_0}\! и подставим \vec{x}=\vec{x_1}\!:

\nabla f(\vec{x_1})-\nabla f(\vec{x_0})=H \, (\vec{x_1}-\vec{x_0})=\lambda_1 H \vec{S_0}\!

Транспонируем полученное выражение и домножаем на H^{-1}\! справа:

(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}=\lambda_1 \vec{S_0}^T H^T H^{-1}\!

В силу непрерывности вторых частных производных H^T=H\!. Тогда:

\vec{S_0}^T=\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}}{\lambda_1}\!

Подставим полученное выражение в (3):

\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}H\vec{S_1}}{\lambda_1}=0\!

Тогда, воспользовавшись (1) и (2):

(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T (-\nabla f(\vec{x_1})-\omega_1\nabla f(\vec{x_0})))=0\qquad (4)\!

Если \lambda=\arg\min_\lambda f(\vec{x_0}+\lambda \vec{S_0})\!, то градиент в точке \vec{x_1}=\vec{x_0}+\lambda \vec{S_0}\! перпендикулярен градиенту в точке \vec{x_0}\!, тогда по правилам скалярного произведения векторов:

(\nabla f(\vec{x_0}),\nabla f(\vec{x_1}))=0\!

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления \omega\!:

\omega_1=\frac{||\nabla f(\vec{x_1})||^2}{||\nabla f(\vec{x_0})||^2}\!

К-я итерация

На k-й итерации имеем набор \vec{S_0},\ldots,\vec{S_{k-1}}\!.

Тогда следующее направление вычисляется по формуле:

\vec{S_k}=-\nabla f(\vec{x_k}) - \|\nabla f(\vec{x_k})\|^2 {\cdot} \left( \frac{\nabla f(\vec{x}_{k-1})}{\|\nabla f(\vec{x}_{k-1})\|^2} + \ldots + \frac{\nabla f(\vec{x_0})}{\|\nabla f(\vec{x}_0)\|^2} \right)\!

Это выражение может быть переписано в более удобном итеративном виде:

\vec{S_k}=-\nabla f(\vec{x_k})+\omega_k \vec{S}_{k-1},\qquad \omega_i=\frac{\|\nabla f(\vec{x_i})\|^2}{\|\nabla f(\vec{x}_{i-1})\|^2},\!

где \omega_k\! непосредственно рассчитывается на k-й итерации.

Алгоритм

Формализация

  1. Задаются начальным приближением и погрешностью: \vec{x}_0,\quad \varepsilon, \quad k=0\!
  2. Рассчитывают начальное направление: j=0,\quad \vec{S}_k^j=-\nabla f(\vec{x}_k),\quad \vec{x}_k^j=\vec{x}_k\!
  3. \vec{x}_k^{j+1}=\vec{x}_k^j+\lambda\vec{S}_k^j,\quad \lambda=\arg\min_\lambda f(\vec{x}_k^j+\lambda \vec{S}_k^j),\quad \vec{S}_k^{j+1}=-\nabla f(\vec{x}_k^{j+1})+\omega \vec{S}_k^j,\quad \omega=\frac{||\nabla f(\vec{x}_k^{j+1})||^2}{||\nabla f(\vec{x}_k^{j})||^2}\!

Случай квадратичной функции

Литература

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