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

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

f(x[k] –akf’(x[k])) = f(x[k] – af'(x[k])).

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
(a) = f(x[k] - af'(x[k])) . Геометрическая интерпретация такого метода приведена на рис 1.17. Причем на выносных элементах рисунка приведены графики одномерных функций, подлежащих оптимизации с целью определения шага.

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

1. Задаются координаты начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k])=g.

3. Определяется величина шага ak, путем одномерной минимизации по а функции (a) = f(x[k] - af'(x[k])).

4. Определяются координаты точки х[k+1]:

хi[k+1] = xi[k] – аkf’i(х[k]), i = 1 ,..., п.

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

Рис. 1.17. Геометрическая интерпретация метода наискорейшего спуска (с решением задачи одномерной оптимизации на каждой итерации)

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

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

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

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

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

Рис. 1.18. Схема сходимости метода наискорейшего спуска для овражной функции

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