Метод наискорейшего спуска

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

f (x[k] -a_kf'(x[k])) = f (x[k] - af'(x[k])).

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

j(a) = f (x[k] — af'(x[k])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

• 1. Задаются координаты начальной точки х[0].
• 2. В точке х[k], k = 0, 1, 2, … вычисляется значение градиента f'(x[k]).
• 3. Определяется величина шага a_k, путем одномерной минимизации по а функции j(a) = f (x[k] — af'(x[k])).
• 4. Определяются координаты точки х[k+1]:

х_i[k+1] = x_i[k] - а_kf'_i(х[k]), i = 1 ,…, п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f (x[k] — af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f'(x[k+1]f'(x[k]) = 0.

Рис. 2.9. Геометрическая интерпретация метода наискорейшего спуска

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе).

мало отличаются друг от друга, т. е. матрица Н (х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения.

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными.Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

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