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

При использовании метода наискорейшего спуска на каждой итерации величина шага а_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] (рис. 7.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

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

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

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

(7.12)

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

(7.13)

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

Рис. 7.10 ‑ Овражная функция

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