Метод коллинеарных градиентов

Метод коллинеарных градиентов (МКГ) — итерационный метод направленного поиска локального экстремума гладкой функции многих переменных $J(u):{ℝ}^n\to ℝ$ с движением к экстремуму вдоль вектора $d\in {ℝ}^n$ такого, где градиенты $\mathrm{\nabla }J(u)$ и $\mathrm{\nabla }J(u+d)$ коллинеарные. Это метод перового порядка (использует только первые производные $\mathrm{\nabla }J$) с квадратичной скоростью сходимости. Может применяться к функциям высокой размерности $n$ с несколькими локальными экстремумами. МКГ можно отнести к семейству методов Truncated Newton method

Коллинеарные векторы $\mathrm{\nabla }J(u^k)$ и $\mathrm{\nabla }J(u^{k_{\ast }})$ с направлением минимизации $d^k$ для выпуклой квадратичной функции, $n=2$

Идея метода

Для гладкой функции $J(u)$ в относительно большой окрестности точки $u^k$ найдётся точка $u^{k_{\ast }}$, где градиенты $\mathrm{\nabla }{J}^k\stackrel{\text{def}}{=}\mathrm{\nabla }J(u^k)$ и $\mathrm{\nabla }{J}^{k_{\ast }}\stackrel{\text{def}}{=}\mathrm{\nabla }J(u^{k_{\ast }})$ коллинеарные. Направлением на экстремум $u_{\ast }$ из точки $u^k$ будет направление $d^k=(u^{k_{\ast }}-u^k)$. Вектор $d^k$ указывает на максимум или на минимум в зависимости от положения точки $u^{k_{\ast }}$. Она может быть спереди или сзади от $u^k$ относительно направления на $u_{\ast }$ (см. рисунок). Далее будем рассматривать минимизацию.

Очередная Шаблон:Font color:

(1) $u^{k+1}=u^k+b^k{d}^k,k\in \{0,1\dots \},$

где оптимальное $b^k\in ℝ$ находится аналитически из предположения квадратичности одномерной функции $J(u^k+b{d}^k)$:

(2) $b^k={(1-\frac{⟨\mathrm{\nabla }J(u^{k_{\ast }},d^k⟩}{⟨\mathrm{\nabla }J(u^k),d^k⟩})}^{-1},\mathrm{\forall }{u}^{k_{\ast }}.$

Угловые скобки — это скалярное произведение в евклидовом пространстве ${ℝ}^n$. Если $J(u)$ выпуклая функция в окрестности $u^k$, то для передней точки $u^{k_{\ast }}$ получаем число $b^k>0$, для задней $b^k<0$. Делаем шаг (1).

Для строго выпуклой квадратичной функции $J(u)$ Шаблон:Font color

 $b^k{d}^k=-H^{-1}\mathrm{\nabla }{J}^k,$

т.е. Шаблон:Font color (метод второго порядка с квадратичной скоростью сходимости), где $H$ — матрица Гессе. Такие шаги обеспечивают МКГ квадратичную скорость сходимости.

В общем случае, если $J(u)$ имеет переменную выпуклость и возможны седловые точки, то следует контролировать направление минимизации по углу $\gamma$ между векторами $\mathrm{\nabla }{J}^k$ и $d^k$. Если $\cos (\gamma )=\frac{⟨\mathrm{\nabla }{J}^k,d^k⟩}{||\mathrm{\nabla }J(u^k)||||d^k||}\ge 0$, то $d^k$ — это направление максимизации и в (1) следует брать $b^k$ с обратным знаком.

Поиск коллинеарных градиентов

Шаблон:Font color оценивается невязкой их ортов, которая имеет вид системы $n$ уравнений для поиска корня $u=u^{k_{\ast }}$:

(3) $r^k(u)=\frac{\mathrm{\nabla }J(u)}{||\mathrm{\nabla }J(u)||}s-\frac{\mathrm{\nabla }J(u^k)}{||\mathrm{\nabla }J(u^k)||}=0\in {ℝ}^n,$

где знак $s=\mathrm{sgn}⟨\mathrm{\nabla }J(u),\mathrm{\nabla }J(u^k)⟩$ позволяет одинаково оценивать коллинеарность градиентов по одну или разные стороны от минимума $u_{\ast }$, $||r^k(u)||\le \sqrt{2}$.

Система (3) решается итерационно (подитерации $l$) методом сопряжённых градиентов в предположении, что она линейна в окрестности $u^k$:

(4) $u^{k_{l+1}}=u^{k_l}+{\tau }^l{p}^l,l=1,2\dots ,$

где вектор $p^l\stackrel{\text{def}}{=}p(u^{k_l})=-r^l+{{\beta }^{l}p}^{l-1}$, $r^l\stackrel{\text{def}}{=}r(u^{k_l})$, ${\beta }^l=||r^l|{|}^2/||r^{l-1}|{|}^2,{\beta }^{1,n,2n\mathrm{...}}=0$, ${\tau }^l=||r^l|{|}^2/⟨p^l,H^l{p}^l⟩$, произведение матрицы Гессе $H^l$ на $p^l$ находится численным дифференцированием:

(5) $H^l{p}^l\approx \frac{r(u^{k_h})-r(u^{k_l})}{h/||p^l||},$

где $u^{k_h}=u^{k_l}+h{p}^l/||p^l||$, $h$ — малое положительное число такое, что $⟨p^l,H^l{p}^l⟩\ne 0$.

Начальное приближение задаётся под 45° ко всем осям координат длинной ${\delta }^k$:

(6) $u_i^{k_1}=u_i^k+\frac{{\delta }^k}{\sqrt{n}}\mathrm{sgn}{{\mathrm{\nabla }}_{i}J}^k,i=1\dots n.$

Начальный радиус ${\delta }^k$-окрестности точки $u^k$ корректируется:

(7) ${\delta }^k=max[min({\delta }^{k-1}\frac{||\mathrm{\nabla }J(u^k)||}{||\mathrm{\nabla }J(u^{k-1})||},{\delta }^0),{\delta }_m],k>0.$

Необходимо $||u^{k_l}-u^k||\ge {\delta }^m,l\ge 1$. Здесь малое положительное число ${\delta }_m$ заметно больше машинного эпсилон.

Подитерации $l$ завершаются при выполнении хотя бы одного из условий:

1. $||r^l||\le c_1\sqrt{2},0\le c_1<1$ — достигнута точность;
2. $\left|\frac{||r^l||-||r^{l-1}||}{||r^l||}\right|\le c_1,l>1$ — прекратилась сходимость;
3. $l\le l_{max}=\mathrm{integer}|c_2\ln c_1\ln n|,c_2\ge 1$ — избыточность подитераций.

Алгоритм выбора направления минимизации

• Параметры: $c_1,c_2,{\delta }^0,{\delta }_m=10^{-15}{\delta }^0,h=10^{-5}$.
• Входные данные: $n,k=0,u^k,J(u^k),\mathrm{\nabla }J(u^k),\mathrm{\nabla }{J}^k$.

1. $l=1$. Если $k>0$ задаём ${\delta }^k$ из (7).
2. Находим $u^{k_l}$ из (6).
3. Вычисляем $\mathrm{\nabla }{J}^l,||\mathrm{\nabla }{J}^l||$ и находим $r^l$ из (3) при $u=u^{k_l}$.
4. Если $||r^l||\le c_1\sqrt{2}$ или $l\ge l_{max}$, или $||u^{k_l}-u^k||<{\delta }_m$, или {$l>1$ и $\left|\frac{||r^l||-||r^{l-1}||}{||r^l||}\right|\le c_1$}, то принимаем $u^{k_{\ast }}=u^{k_l}$, возвращаем $\mathrm{\nabla }J\left(u^{k_{\ast }}\right)$, $d^k={(u^{k_{\ast }}-u}^k)$, Шаблон:Font color.
5. Если $l\ne 1,n,2n,3n\dots$, задаём ${\beta }^l=||r^l|{|}^2/||r^{l-1}|{|}^2$, иначе ${\beta }^l=0$.
6. Вычисляем $p^l=-r^l+{\beta }^l{p}^{l-1}$.
7. Находим шаговый множитель ${\tau }^l$ для подитераций:
   1. запоминаем $u^{k_l}$, $\mathrm{\nabla }{J}^l$, $||\mathrm{\nabla }{J}^l||$, $r^l$, $||r^l||$;
   2. задаём $u^{k_h}=u^{k_l}+h{p}^l/||p^l||$, вычисляем $\mathrm{\nabla }J(u^{k_h})$, $r\left(u^{k_h}\right)$ и находим $H^l{p}^l$ из (5), присваиваем $w\leftarrow ⟨p^l,H^l{p}^l⟩$;
   3. если $w=0$, тогда $h\leftarrow 10h$, возвращаемся к шагу 7.2;
   4. восстанавливаем $u^{k_l}$, $\mathrm{\nabla }{J}^l$, $||\mathrm{\nabla }{J}^l||$, $r^l$, $||r^l||$;
   5. находим ${\tau }^l=||r^l|{|}^2/w$.
8. Делаем подитерацию $u^{k_{l+1}}$ из (4).
9. $l\leftarrow l+1$, переходим к шагу 3.

Параметр $c_2=3÷5$. Для функций без седловых точек рекомендуется $c_1\approx 10^{-8}$, $\delta \approx {10}^{-5}$. Для «обхода» седловых точек рекомендуется $c_1\approx 0.1$, $\delta \approx 0.1$.

Описанный алгоритм позволяет приблизительно найти коллинеарные градиенты из системы уравнений (3). Полученное направление $b^k{d}^k$ для алгоритма МКГ (1) будет Шаблон:Font color (truncated Newton method).

Демонстрации

Во всех демонстрациях МКГ показывает сходимость не хуже, а иногда и лучше (для функций переменной выпуклости), чем метод Ньютона.

Тестовая функция «повёрнутый эллипсоид»

Строго выпуклая квадратичная функция:

Минимизация МКГ, $n=2$

$J(u)=\sum _{i=1}^n{\left(\sum _{j=1}^i{u}_j\right)}^2,u_{\ast }=(\mathrm{0...0}).$

На рисунке для $n=2$ заданы три чёрные стартовые точки $u^0$. Серые точки — подитерации $u^{0_l}$ с ${\delta }^0=0.5$ (показано пунктиром, завышено для демонстрации). Параметры $c_1=10^{-8}$, $c_2=4$. Для всех $u^0$ потребовалась одна итерация и подитераций $l$ не более двух.

При $n=1000$ (параметр ${\delta }^0={10}^{-5}$) с начальной точкой $u^0=(-\mathrm{1...1})$ МКГ достиг $u_{\ast }$ с точностью 1 % за 3 итерации и 754 вычисления $J$ и $\mathrm{\nabla }J$. Другие методы первого порядка: Квазиньютоновский BFGS (работа с матрицами) потребовал 66 итераций и 788 вычислений; сопряжённых градиентов (Fletcher-Reeves) — 274 итерации и 2236 вычислений; конечно-разностный метод Ньютона — 1 итерация и 1001 вычислений. Метод Ньютона второго порядка — 1 итерация.

С ростом размерности $n$, вычислительные погрешности при реализации условия коллинеарности (3), могут заметно возрастать. Поэтому МКГ, по сравнению с методом Ньютона, в рассматриваемом примере потребовал более одной итерации.

Минимизация МКГ и методом Ньютона: 3 итерации. МКГ сделал 16 вычислений $J$ и $\mathrm{\nabla }J$

Тестовая функция Розенброка

$J(u)=100(u_1^2-u_2{)}^2+(u_1-1{)}^2,u_{\ast }=(1,1).$

Параметры $c_1=10^{-8}$, $c_2=4$, ${\delta }^0={10}^{-5}$. Траектория спуска МКГ полностью совпадает с методом Ньютона. На рисунке синяя начальная точка $u^0=(-0.8;-1.2)$, красная — $u_{\ast }$. В каждой точке нарисованы орты градиентов.

Тестовая функция Химмельблау

$J(u)=(u_1^2+u_2-11{)}^2+(u_1+u_2^2-7{)}^2.$

Параметры $c_1=0.1$, $c_2=4$, ${\delta }^0=0.05$.

Минимизация МКГ: 7 итераций и 22 вычисления $J$ и $\mathrm{\nabla }J$. Красные линии — $\cos \gamma \ge 0$.	Минимизация методом Ньютона: 9 итераций ($b^k=1$)
Метод сопряжённых градиентов (Fletcher-Reeves): 9 итерации и 62 вычисления $J$ и $\mathrm{\nabla }J$	Квазиньютоновский BFGS: 6 итераций и 55 вычислений $J$ и $\mathrm{\nabla }J$. Красная линия (нарушение условия кривизны) — метод наискорейшего спуска.

Шаблон:Font color по количеству вычислений $J$ и $\mathrm{\nabla }J$. Благодаря формуле (2), он не требует затратных вычислений шагового множителя $b^k$ посредством линейного поиска (например, методом золотого сечения и т.п.).