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

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

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

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

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

${\displaystyle {\vec {S_{1}}}=-\nabla f({\vec {x_{1}}})+\omega _{1}{\vec {S_{0}}}\ \qquad (2)}$

так, чтобы оно было сопряжено с ${\displaystyle {\vec {S_{0}}}}$:

${\displaystyle {\vec {S_{0}}}^{T}H{\vec {S_{1}}}=0\qquad (3)}$

Разложим ${\displaystyle \nabla f({\vec {x}})}$ в окрестности ${\displaystyle {\vec {x_{0}}}}$ и подставим ${\displaystyle {\vec {x}}={\vec {x_{1}}}}$:

${\displaystyle \nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}})=H\,({\vec {x_{1}}}-{\vec {x_{0}}})=\lambda _{1}H{\vec {S_{0}}}}$

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

${\displaystyle (\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}H^{-1}=\lambda _{1}{\vec {S_{0}}}^{T}H^{T}H^{-1}}$

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

${\displaystyle {\vec {S_{0}}}^{T}={\frac {(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}H^{-1}}{\lambda _{1}}}}$

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

${\displaystyle {\frac {(\nabla f({\vec {x_{1}}})-\nabla f({\vec {x_{0}}}))^{T}H^{-1}H{\vec {S_{1}}}}{\lambda _{1}}}=0}$

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

${\displaystyle (\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)}$

Если ${\displaystyle \lambda =\arg \min _{\lambda }f({\vec {x_{0}}}+\lambda {\vec {S_{0}}})}$, то градиент в точке ${\displaystyle {\vec {x_{1}}}={\vec {x_{0}}}+\lambda {\vec {S_{0}}}}$ перпендикулярен градиенту в точке ${\displaystyle {\vec {x_{0}}}}$, тогда по правилам скалярного произведения векторов:

${\displaystyle (\nabla f({\vec {x_{0}}}),\nabla f({\vec {x_{1}}}))=0}$

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

${\displaystyle \omega _{1}={\frac {||\nabla f({\vec {x_{1}}})||^{2}}{||\nabla f({\vec {x_{0}}})||^{2}}}}$

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

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

${\displaystyle {\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)}$

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

${\displaystyle {\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}}},}$

где ${\displaystyle \omega _{k}}$ непосредственно рассчитывается на k-й итерации.

1. Задаются начальным приближением и погрешностью: ${\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0}$
2. Рассчитывают начальное направление: ${\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}}$
3. ${\displaystyle {\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}}}}$
   • Если ${\displaystyle ||{\vec {S}}_{k}^{j+1}||<\varepsilon }$ или ${\displaystyle ||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon }$, то ${\displaystyle {\vec {x}}={\vec {x}}_{k}^{j+1}}$ и остановка.
   • Иначе
     • если ${\displaystyle (j+1)<n}$, то ${\displaystyle j=j+1}$ и переход к 3;
     • иначе ${\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1}$ и переход к 2.