1. Алгоритмы сопряженных градиентов

В алгоритме наискорейшего спуска на каждом этапе поиска используется только текущая информация о функции и градиенте . В алгоритмах сопряженных градиентов используется информация о поиске на предыдущих этапах спуска.

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

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

В начальной точке направление спуска :

,                                                     (1)

где выбирается из соображений минимальности целевой функции в данном направлении . Новое направление поиска

,                                                (2)

где выбирается так, чтобы сделать направления и сопряженными по отношению к матрице :

.                                              

Полностью алгоритм описывается следующей последовательностью действий:

1. В точке начального приближения вычисляется .

2. На -м шаге с помощью одномерного поиска в направлении определяется минимум функции, то есть решается задача

и находится очередное приближение .

3. Вычисляется и .

4. Определяется направление .

5. Алгоритм заканчивается, если , где – заданная величина.

После итераций (), если не произошел останов алгоритма, процедура циклически повторяется с заменой на и возвратом на первый пункт алгоритма. Если исходная функция является квадратичной, то ()-е приближение даст точку экстремума данной функции.

Описанный алгоритм с построением по формулам (6) соответствует методу сопряженных градиентов Флетчера-Ривса.

.                                                   (6)

В модификации Полака-Рибьера (Пшеничного) метод сопряженных градиентов отличается только вычислением

.                                           (7)

В случае квадратичных функций обе модификации примерно экви­ва­лент­ны, однако в модификации Полака-Рибьера алгоритм иногда оказывается не­сколь­ко эффективнее.