Метод сопряженного градиента Флетчера-Ривса

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

,

причем коэффициенты выбираются так, чтобы сделать направления поиска сопряженными. Доказано, что

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

Алгоритм Флетчера-Ривса.

1. В X⁰вычисляется .

2. На k-ом шаге с помощь одномерного поиска в направлении находится минимум f(X), который и определяет точку Xk+1.

3. Вычисляются f(X^k+1) и .

4. Направление определяется из соотношения:

5. После (n+1)-й итерации (т.е. при k=n) производится рестарт: полагается X0=Xn+1и осуществляется переход к шагу 1.

6. Алгоритм останавливается, когда , где e - произвольная константа.

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

Алгоритм Флетчера-Ривса чувствителен к точности одномерного поиска, поэтому при его использовании необходимо устранять любые ошибки округления, которые могут возникнуть. Кроме того, алгоритм может отказать в ситуациях, где Гессиан становится плохо обусловленным. Гарантии сходимости всегда и везде у алгоритма нет, хотя практика показывает, что почти всегда алгоритм дает результат.