Методы Оптимизации Систем Автоматизированного Проектирования

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

Стратегия поиска.Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции.
Определение. Два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.
Стратегия метода Флетчера-Ривса состоит в построении последовательности точек , k=0, 1, 2, ... таких, что, k=0, 1, 2, ...
Точки последовательности вычисляются по правилу:

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

Отметим, что при данном выборев случае квадратичной функции f(x)= (х, Нх) + (b, х) + а направления будут H-сопряженными, т.е.
При этом в точках последовательности градиенты функции f(x) взаимно перпендикулярны, т.е.
При минимизации неквадратичных функций метод Флетчера-Ривса не является конечным. Для неквадратичных функций используется следующая модификация метод Флетчера-Ривса (метод Полака-Рибьера), когда величинавычисляется следующим образом:

Здесь I- множество индексов: I = {0, n, 2n, Зn, ...}, т. е. метод Полака-Рибьера предусматривает использование итерации наискорейшего градиентного спуска через каждые n шагов с заменой на.
Построение последовательностизаканчивается в точке, для которой .
Геометрический смысл метода сопряженных градиентов состоит в следующем. Из заданной начальной точки осуществляется спуск в направлении.В точке определяется вектор-градиент.Поскольку является точкой минимума функции в направлении , тоортогонален вектору . Затем отыскивается вектор , H-сопряженный к . Далее отыскивается минимум функции вдоль направления и т. д.

Стр.: ..., 2, 3, 4