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

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

Как показано в [39, 167], вектор удовлетворяющий заданным выше условиям, имеет вид:

где обозначает фактическое значение вектора градиента.

Из формулы (3.46) следует, что новое направление минимизации зависит только от значения градиента в точке решения и» и от предыдущего направления поиска умноженного на коэффициент сопряжения Этот коэффициент играет очень важную роль, аккумулируя в себе информацию о предыдущих направлениях поиска. Существуют различные правила расчета его значения. Наиболее известны среди них [39, 170]

и

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

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