Рассмотренные выше градиентные способы отыскивают точку минимума функции в общем случае только за нескончаемое число итераций. Способ сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это значительно увеличивает скорость их сходимости и разрешает, к примеру, минимизировать квадратичную функцию
f(x) = (х, Нх) + (b, х) + а
с симметрической положительно определенной матрицей Н за конечное число шагов п , равное числу переменных функции. Каждая ровная функция в окрестности точки минимума прекрасно аппроксимируется квадратичной, исходя из этого способы сопряженных градиентов удачно используют для неквадратичных функций и минимизации. При таких условиях они перестают быть конечными и становятся итеративными.
По определению, два n-мерных вектора х и у именуют сопряженными по отношению к матрице H (либо H-сопряженными), в случае если скалярное произведение (x, Ну) = 0. Тут Н — симметрическая положительно определенная матрица размером пхп.
Одной из самые существенных неприятностей в способах сопряженных градиентов есть неприятность действенного построения направлений. Способ Флетчера-Ривса решает эту проблему методом преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее отысканными направлениями р[0], р[1], …, р[k-1]. Разглядим сперва данный способ применительно к задаче минимизации квадратичной функции.
Направления р[k] вычисляют по формулам:
p[k] = -f’(x[k])+?k-1p[k-l], k = 1;
p[0] = -f’(x[0известный).
Величины ?k-1 выбираются так, дабы направления p[k], р[k-1] были H-сопряженными:
(p[k], Hp[k-1])= 0.
В следствии для квадратичной функции
,
итерационный процесс минимизации имеет форму
x[k+l] =x[k] +akp[k],
где р[k] — направление спуска на k-м шаге; аk — величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении перемещения, т. е. в следствии ответа задачи одномерной минимизации:
f(х[k] + аkр[k]) =
f(x[k] + ар [k]).
Для квадратичной функции
Метод способа сопряженных градиентов Флетчера-Ривса пребывает в следующем.
1. В точке х[0] вычисляется p[0] = -f’(x[0]).
2. На k-м шаге по вышеприведенным формулам определяются ход аk. и точка х[k+1].
3. Вычисляются величины f(x[k+1]) и f’(x[k+1]).
4. В случае если f’(x[k+1]) = 0, то точка х[k+1] есть точкой минимума функции f(х). В другом случае определяется новое направление p[k+l] из соотношения
и осуществляется переход к следующей итерации. Эта процедура отыщет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций способ Флетчера-Ривса из конечного делается итеративным. При таких условиях по окончании (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при
, где
— заданное число. Наряду с этим используют следующую модификацию способа:
x[k+l] = x[k] +akp[k],
p[k] = -f’(x[k])+?k-1p[k-l], k = 1;
p[0] = -f’(x[0]);
f(х[k] + akp[k]) =
f(x[k] + ap[k];
.
Тут I- множество индексов: I = {0, n, 2п, Зп, …}, т. е. обновление способа происходит через каждые п шагов.
Геометрический суть способа сопряженных градиентов пребывает в следующем (Рис. 2.11). Из заданной начальной точки х[0] осуществляется спуск в направлении р[0] = -f'(x[0]). В точке х[1] определяется вектор-градиент f'(x [1]). Потому, что х[1] есть точкой минимума функции в направлении р[0], то f’(х[1]) ортогонален вектору р[0]. После этого отыскивается вектор р [1], H-сопряженный к р [0] . Потом отыскивается минимум функции на протяжении направления р[1] и т. д.
Рис. 2.11. Траектория спуска в способе сопряженных градиентов
Способы сопряженных направлений являются одними из самые эффективных для ответа задач минимизации. Но направляться подчернуть, что они чувствительны к неточностям, появляющимся в ходе счета. При солидном числе переменных погрешность может так возрасти, что процесс нужно будет повторять кроме того для квадратичной функции, т. е. процесс для нее не всегда укладывается в п шагов.
Лекция 19: Многомерная оптимизация (часть 2)
