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

11.10.3.1. Сопряженные направления
Методы наискорейшего спуска или спуска по координатам даже для квадратичной функции требуют большого числа итераций. Однако можно построить такие направления спуска, что для квадратичной функции
Ф(r)=(r,A r)+(b, r)+c,
где r есть n-мерный вектор с симметричной положительно определенной матрицей А процесс спуска сойдется точно к минимуму за конечное число шагов.
Положительно определенная матрица А позволяет ввести норму вектора следующим образом:
|| x ||=(x,A x)>0 при x ≠0
Введенное определение означает, что под скалярным произведением двух векторов x и y теперь понимается величина (x,А y). Векторы, ортогональные в смысле этого скалярного произведения (x,А y)=0, называют сопряженными по отношению к матрице А. Оказывается, что спуск по сопряженным направлениям особенно выгоден при поиске минимума.
На этом основана большпая группа методов: сопряженныъх градиентов, сопряженных направлений, паралелльных касательных и другие. Для квадратичной формы они применяются с одинаковым успехом.
Метод сопряженных градиентов − один из популярных в последние годы методов минимизации функции многих переменных, который довольно широко используется на практике и даже вошел в состав стандартных средств программы Excel.
На произвольные функции наиболее хорошо обобщается метод сопряженных направлений, у котрого детали алгоритма тщательно отработаны. Метод сопряженных направлений является, по-видимому, одним из наиболее эффективных методов спуска. Он неплохо работает и при вырожденном минимуме, и при разрешимых оврагах, и при наличии слабо наклонных участков рельефа − "плато", и при большом числе переменных − до двух десятков.
Если имеется некоторая система попарно сопряженных векторов x _i, то они линейно-независимы: x _i y _j=δ_ij, где δ_ij − символ Кронеккера. Тогда любое движение из произвольной точки r ₀ можно разложить по сопряженному базису: r = r ₀+Σα_i r _i. Подставляя это выражение в правую часть выражения Ф(r)=(r,A r)+(b, r)+c, получим
Ф(r) = Ф(r ₀) + Σ[(α_i)² + 2α_i(x _i,A r)₀) + α_i(x _i, b)]
Полученная сумма состоит из членов, каждый из которых соответствует только одной компоненте из движения, описанонго в сопряженном базисе. Поэтому поочередные спуски по каждому из сопряженных направлений x _i минимизирует свой член суммы в Ф(r), так что минимум квадратичной функции точно достигается после выполнения одного цикла спусков, т.е. за конечное число действий.
Заметим, что термин "метод сопряженных градиентов" − один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.

11.10.3.2. Геометрическая интерпретация метода сопряженных градиентов
Рассмотрение метода сопряженных градиентов целесообразно начать с рассмотрения более простого метода поиска экстремума функции − метода наискорейшего спуска. На рисунке 16.9a изображена траектория движения в точку минимума методом наискорейшего спуска.

Вербальное описание алгоритма метода наискорейшего спуска следующее:

• в начальной точке x ⁽⁰⁾ вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция;
• в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении;
• процесс повторяется до достижения точки минимума.

В данном случае каждое новое направление движения ортогонально предыдущему. Не существует ли более разумного способа выбора нового направления движения? Существует, и он называется метод сопряженных направлений. А метод сопряженных градиентов как раз относится к группе методов сопряженных направлений. На рисунке 16.9b изображена траектория движения в точку минимума при использовании метода сопряженных градиентов. Сопряженность можно считать обобщением понятия ортогональности. Действительно, когда матрица А − единичная матрица, векторы x и y – ортогональны. Можно и иначе продемонстрировать взаимосвязь понятий ортогональности и сопряженности: мысленно растяните рисунок 16.9b таким образом, чтобы линии равного уровня из эллипсов превратились в окружности, при этом сопряженные направления станут просто ортогональными.

Рис. 16.9а. Траектория движения в точку минимума методом наискорейшего спуска	Рис. 16.9b. Траектория движения в точку минимума при использовании метода сопряженных градиентов

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

Метод Хука-Дживса

Процедура поиска Хука-Дживса представляет собой комбинацию "исследующего поиска" и "ускоряющего поиска по образцу".
Исследующий поиск ориентирован на выявление локального характера поведения целевой функции и определение направлений вдоль "оврагов". Для проведения исследующего поиска необходимо задать величину шага, которая может быть различной для разных координатных направлений и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превышает значение функции в исходной точке, то шаг поиска рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположное направление с последующей проверкой значения целевой функции. После перебора всех N координат исследующий поиск завершается. Полученную в результате точку называют "базовой точкой".
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки x^k вдоль прямой, соединяющей эту точку с предыдущей базовой точкой x^k−1. Новая точка образца x^k+1 определяется в соответствии с формулой
x^k+1 = x^k + a_k(x^k − x^k−1)
где параметр a_k называется ускоряющим множителем. Его величина подбирается так, чтобы в направлении спуска значение целевой функции уменьшалось.