К градиентным методам может быть условно отнесен и метод релаксации [26]. Такий метод объединяет идеи, реализуемые в методе покоординатного спуска, с идеей использования первых производных ЦФ. В этом методе, как и в методе покоординатного спуска, пошаговое движение осуществляется в направлении координатных осей. Однако выбор координат для каждого шага осуществляется не в жестко заданном порядке, а в направлении, противоположном той оси, для которой компонента вектора градиента на данном шаге имеет наибольшее значение (другими словами, выбирается ось, в направлении которой имеет место наибольшее убывание ЦФ). При этом изменяющаяся компонента вектора Xk определяется из следующего соотношения:
x k+1 j = x k j - hk (¶z(Xk)/¶xj ) , (4.30)
где j - номер компоненты вектора grad z(Xk), имеющей наибольшее по модулю значение (это значение совпадает с номером выбираемой координатной оси).
Очевидно, что рассматриваемый метод более эффективен, чем метод покоординатного спуска, поскольку он более точно учитывает особенности целевой функции, отражаемые в градиенте. Однако по сравнению с другими градиентными методами он имеет меньшую эффективность, поскольку не обеспечивает ту степень убывания ЦФ, которая достигается при использовании направления градиента.
Рассмотрим далее подгруппу методов первого порядка, приближающиеся по своей эффективности к методам второго порядка.
Метод сопряженных градиентов.
(Другие названия – метод сопряженного градиента, метод Флетчера-Ривса).
Градиентные методы, базирующиеся на вычислении градиента ЦФ, являются методами первого порядка. Более эффективными, как было отмечено ранее, могут быть методы второго порядка, при вычислении которых используются не только первые, но и вторые производные ЦФ в текущей точке. Однако у этих методы требуют трудоемких вычислений вторых производных в точке.
Метод сопряженных градиентов является попыткой объединения достоинств методов первого и второго порядка с исключением их недостатков. Рассматриваемый метод основан на том факте, что минимум квадратичной функции n переменных может быть найден за n просмотров или шагов, выполненных вдоль взаимно сопряженных направлений [ …].
З а м е ч ан и е 4.26. Понятие сопряженности двух и более n-мерных векторов рассматривается по отношению к некоторой матрице, с использованием которой строятся скалярные произведения, обладающие определенным свойством. Так, ортогональные векторы S0, S1, S2, … , Sn-1 называются сопряженными (относительно матрицы А), если выполняются соотношения
< S i , AS j
> = 0 , i ¹ j , i, j = 0, n-1 .
( В последнем выражении S i - вектор-строка, A – симметричная матрица, S j - вектор-столбец). Частным случаем сопряженности векторов является их ортогональность. В этом случае в роли матрицы А выступает единичная матрица.
На основании рассмотренного факта разработан ряд методов сопряженных направлений. Во всех этих методах в качестве матрицы выступает матрица Гессе G (см. (4.4)). Решение задачи оптимизации осуществляется в процессе итерационной процедуры, предусматривающей последовательное построение G-сопряженных векторов и выполнение шагов оптимальной длины по направлению этих векторов, минимизирующих значение критерия оптимальности. Последовательность сопряженных векторов строится на базе некоторых исходных векторов, служащих “строительным материалом” для их построения. (В качестве таких векторов могут выступать единичные векторы или векторы – градиенты).
В методе сопряженных градиентов в качестве исходных векторов используются векторы – градиенты ЦФ. При этом каждое последующее направление определяется как линейная комбинация текущего градиента и вектора предшествующего направления. Такая последовательность описывается следующей рекуррентной формулой
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.