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

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

Пусть ${\displaystyle {\vec {S_{1}}},\ldots ,{\vec {S_{n}}}\in \mathbb {X} \subset \mathbb {R} ^{n}\!}$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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