Метод сопряжённых градиентов

Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в $\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}}}\!$ называются сопряжёнными, если:

• ${\vec {S_{i}}}^{T}H{\vec {S_{j}}}=0,\quad i\neq j,\quad i,j=1,\ldots ,n\!$
• ${\vec {S_{i}}}^{T}H{\vec {S_{i}}}\geqslant 0,\quad i=1,\ldots ,n\!$
  

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

Теорема (о существовании). Существует хотя бы одна система $n\!$ сопряжённых направлений для матрицы $H\!$, т.к. сама матрица $H\!$ (её собственные вектора) представляет собой такую систему.

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

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

Файл:Conjugate gradient illustration.svg

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

Пусть ${\vec {S_{0}}}=-\nabla f({\vec {x_{0}}})\qquad (1)\!$

Тогда ${\vec {x_{1}}}={\vec {x_{0}}}+\lambda _{1}{\vec {S_{0}}}\qquad (2)\!$.

Определим направление ${\vec {S_{1}}}=-\nabla f({\vec {x_{1}}})+\omega _{1}{\vec {S_{0}}}\!$ так, чтобы оно было сопряжено с ${\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}}})+\omega _{1}{\vec {S_{0}}}+\ldots +\omega _{k}{\vec {S}}_{k-1},\quad \omega _{i}={\frac {||\nabla f({\vec {x_{i}}})||^{2}}{||\nabla f({\vec {x}}_{i-1})||^{2}}},\!$

где $\omega _{k}\!$ непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.

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

${\vec {S_{k}}}=-\nabla f({\vec {x_{k}}})+\omega _{k}{\vec {S}}_{k-1}\!$

Алгоритм

• Пусть ${\vec {x}}_{0}\!$ — начальная точка, ${\vec {r}}_{0}\!$ — направление антиградиента и мы пытаемся найти минимум функции $f({\vec {x}})\!$. Положим ${\vec {S}}_{0}={\vec {r}}_{0}\!$ и найдем минимум вдоль направления ${\vec {S}}_{0}\!$. Обозначим точку минимума ${\vec {x}}_{1}\!$.

• Пусть на некотором шаге мы находимся в точке ${\vec {x}}_{k}\!$, и ${\vec {r}}_{k}\!$ — направление антиградиента. Положим ${\vec {S}}_{k}={\vec {r}}_{k}+\omega _{k}{\vec {S}}_{k-1}\!$, где $\omega _{k}\!$ выбирают либо ${\frac {({\vec {r}}_{k},{\vec {r}}_{k})}{({\vec {r}}_{k-1},{\vec {r}}_{k-1})}}\!$ (стандартный алгоритм), либо $\max(0,{\frac {({\vec {r}}_{k},{\vec {r}}_{k}-{\vec {r}}_{k-1})}{({\vec {r}}_{k-1},{\vec {r}}_{k-1})}})\!$ (алгоритм Полака–Райбера). После чего найдем минимум в направлении ${\vec {S_{k}}}\!$ и обозначим точку минимума ${\vec {x}}_{k+1}\!$. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив $\omega _{k}=0\!$ и повторив шаг.

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

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}}}\!$
   • Если $||{\vec {S}}_{k}^{j+1}||<\varepsilon \!$ или $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon \!$, то ${\vec {x}}={\vec {x}}_{k}^{j+1}\!$ и останов.
   • Иначе
     • если $(j+1)<n\!$, то $j=j+1\!$ и переход к 3;
     • иначе ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1\!$ и переход к 2.

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

Теорема. Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за $n$ шагов, по одному в каждом направлении, причём порядок несущественен.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.

1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.

1. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.

1. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

1. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.

1. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

См. также

Градиентные методы:

• Метод градиента
• Метод покоординатного спуска

Ссылки

Поиск глобального оптимума для задач оптимального проектирования систем или определения оптимальных законов управления.

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Метод сопряжённых градиентов. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---