Русская Википедия:Метод сопряжённых градиентов
Шаблон:Другие значения Метод сопряжённых градиентов (Метод Флетчера — Ривcа) — метод нахождения локального экстремума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в <math>\mathbb{R}^n</math> минимум находится не более чем за <math>n</math> шагов.
Основные понятия
Определим терминологию:
Пусть <math>\vec{S_1},\ldots,\vec{S_n} \in \mathbb{X} \subset \mathbb{R}^n</math>.
Введём на <math>\mathbb{X}</math> целевую функцию <math>f(\vec{x})\in \mathrm{C^2}(\mathbb{X})</math>.
Векторы <math>\vec{S_1},\ldots,\vec{S_n}</math> называются сопряжёнными, если:
- <math>\vec{S_i}^T H \vec{S_j}=0, \quad i\neq j, \quad i,j=1,\ldots,n</math>
- <math>\vec{S_i}^T H \vec{S_i}\geqslant 0, \quad i=1,\ldots,n</math>
где <math>H</math> — матрица Гессе <math>f(\vec{x})</math>.
Обоснование метода
Нулевая итерация
Пусть <math>\vec{S_0}=-\nabla f(\vec{x_0})\qquad (1)</math>
Тогда <math>\vec{x_1}=\vec{x_0}+\lambda_1 \vec{S_0} \qquad</math>.
Определим направление
<math>\vec{S_1}=-\nabla f(\vec{x_1})+\omega_1 \vec{S_0}\ \qquad (2)</math>
так, чтобы оно было сопряжено с <math>\vec{S_0}</math>:
- <math>\vec{S_0}^T H \vec{S_1}=0 \qquad (3)</math>
Разложим <math>\nabla f(\vec{x})</math> в окрестности <math>\vec{x_0}</math> и подставим <math>\vec{x}=\vec{x_1}</math>:
- <math>\nabla f(\vec{x_1})-\nabla f(\vec{x_0})=H \, (\vec{x_1}-\vec{x_0})=\lambda_1 H \vec{S_0}</math>
Транспонируем полученное выражение и домножаем на <math>H^{-1}</math> справа:
- <math>(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}=\lambda_1 \vec{S_0}^T H^T H^{-1}</math>
В силу непрерывности вторых частных производных <math>H^T=H</math>. Тогда:
- <math>\vec{S_0}^T=\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}}{\lambda_1}</math>
Подставим полученное выражение в (3):
- <math>\frac{(\nabla f(\vec{x_1})-\nabla f(\vec{x_0}))^T H^{-1}H\vec{S_1}}{\lambda_1}=0</math>
Тогда, воспользовавшись (1) и (2):
- <math>(\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)</math>
Если <math>\lambda=\arg\min_\lambda f(\vec{x_0}+\lambda \vec{S_0})</math>, то градиент в точке <math>\vec{x_1}=\vec{x_0}+\lambda \vec{S_0}</math> перпендикулярен градиенту в точке <math>\vec{x_0}</math>, тогда по правилам скалярного произведения векторов:
- <math>(\nabla f(\vec{x_0}),\nabla f(\vec{x_1}))=0</math>
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления <math>\omega</math>:
- <math>\omega_1=\frac{||\nabla f(\vec{x_1})||^2}{||\nabla f(\vec{x_0})||^2}</math>
К-я итерация
На k-й итерации имеем набор <math>\vec{S_0},\ldots,\vec{S_{k-1}}</math>.
Тогда следующее направление вычисляется по формуле:
- <math>\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)</math>
Это выражение может быть переписано в более удобном итеративном виде:
- <math>\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},</math>
где <math>\omega_k</math> непосредственно рассчитывается на k-й итерации.
Алгоритм
- Пусть <math>\vec{x}_0</math> — начальная точка, <math>\vec{r}_0</math> — направление антиградиента и мы пытаемся найти минимум функции <math>f(\vec{x})</math>. Положим <math>\vec{S}_0=\vec{r}_0</math> и найдём минимум вдоль направления <math>\vec{S}_0</math>. Обозначим точку минимума <math>\vec{x}_1</math>.
- Пусть на некотором шаге мы находимся в точке <math>\vec{x}_k</math>, и <math>\vec{r}_k</math> — направление антиградиента. Положим <math>\vec{S}_k=\vec{r}_{k}+\omega_k \vec{S}_{k-1}</math>, где <math>\omega_k</math> выбирают либо <math>\frac{(\vec{r}_k,\vec{r}_k)}{(\vec{r}_{k-1},\vec{r}_{k-1})}</math> (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с <math>H>0</math>), либо <math>\max(0,\frac{(\vec{r}_k,\vec{r}_k-\vec{r}_{k-1})}{(\vec{r}_{k-1},\vec{r}_{k-1})})</math> (алгоритм Полака–Рибьера). После чего найдём минимум в направлении <math>\vec{S_k}</math> и обозначим точку минимума <math>\vec{x}_{k+1}</math>. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив <math>\omega_k=0</math> и повторив шаг.
Формализация
- Задаются начальным приближением и погрешностью: <math>\vec{x}_0,\quad \varepsilon, \quad k=0</math>
- Рассчитывают начальное направление: <math>j=0,\quad \vec{S}_k^j=-\nabla f(\vec{x}_k),\quad \vec{x}_k^j=\vec{x}_k</math>
- <math>\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}</math>
- Если <math>||\vec{S}_k^{j+1}||<\varepsilon</math> или <math>||\vec{x}_k^{j+1}-\vec{x}_k^j||<\varepsilon</math>, то <math>\vec{x}=\vec{x}_k^{j+1}</math> и остановка.
- Иначе
- если <math>(j+1)<n</math>, то <math>j=j+1</math> и переход к 3;
- иначе <math>\vec{x}_{k+1}=\vec{x}_k^{j+1},\quad k=k+1</math> и переход к 2.
Случай квадратичной функции
Литература
