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

Рассматриваемый градиентный метод носит также название метода Коши, поскольку Коши первым использовал аналогичный алгоритм для решения систем линейных уравнений.

Стратегия данного метода состоит в построении последовательности точек , таких, что

.

Точку задаёт пользователь. Остальные точки последовательности вычисляются по правилу:

,

где - градиент функции , вычисленный в точке .

Величина шага определяется для каждого значения k из условия

.

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

Другой путь решения этой задачи связан с использованием численных методов, когда ищется

.

Границы интервала [a, b] задаются пользователем. При этом степень близости найденного значения к оптимальному значению , удовлетворяющему условиям , зависит от задания интервала [a, b] и точности методов одномерной минимизации.

Теорема 2 Пусть функция удовлетворяет условиям теоремы 1. Тогда при произвольной начальной точке для метода наискорейшего градиентного спуска имеем

.

Эта теорема гарантирует сходимость последовательности к стационарной точке , где . Следовательно, найденную в результате применения метода точку нужно дополнительно исследовать с целью ее классификации.

Метод наискорейшего спуска гарантирует сходимость последовательности к точке минимума для сильно выпуклых функций.

Оценки скорости сходимости получены только для сильно выпуклых функций, когда последовательность сходится к точке минимума со скоростью геометрической прогрессии (линейная сходимость):

где M и m – оценки наибольшего и наименьшего собственных значений матрицы H(x) функции .

Если функция является строго выпуклой, то поиск глобального минимума аналогичен поиску локального минимума этой функции. Если же имеет несколько локальных минимумов, то поиск глобального минимума осуществляется в результате перебора всех локальных минимумов.

Метод обеспечивает высокую надежность по сравнению с простейшим градиентным методом, однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку изменения переменных непосредственно зависят от величины градиента, которая стремится к нулю в окрестности точки минимума, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из главных преимуществ метода Коши связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага итерации обеспечивают выполнение неравенства

.

С учетом этого свойства заметим, что метод Коши, как правило, позволяет уменьшить значение целевой функции при движении из точек, расположенных на значительных расстояниях от точки минимума, и поэтому часто используется при реализации градиентных методов в качестве начальной процедуры.

Также важной отличительной особенностью этого метода является равенство

,

согласно которому используемые на соседних итерациях направления убывания и взаимно ортогональны. Таким образом, спуск в данном методе происходит «зигзагообразно».

Алгоритм:

Шаг 1. Задать: начальную точку -малые положительные числа, M – предельное число итераций. Найти градиент в произвольной точке.

Шаг 2. Положить k=0.

Шаг 3. Вычислить .

Шаг 4. Проверить выполнение критерия окончания :

а) если критерий выполняется, , расчет окончен;

б) если нет, то перейти к шагу 5.

Шаг 5. Проверить условие :

а) если неравенство выполняется, то , расчет окончен;

б) если нет, перейти к шагу 6.

Шаг 6. Вычислить величину шага из условия

.

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условий

:

а) если выполняются оба условия в двух последовательных итерациях с номерами k и k-1, то расчет окончен, найдена точка ;

б) если не выполняется хотя бы одно из условий, то положить k = k + 1 и перейти к шагу 3.

Геометрическая интерпретация метода для n = 2 приведена на рисунке 4.3.

Рисунок 4.3.

Пример: Методом Коши найти локальный минимум функции

Решение:

1. Зададим , M: , , M =10.

Найдем градиент функции в произвольной точке

2. Положим k = 0.

3⁰. Вычислим : .

4⁰. Проверим условие : .

5⁰. Проверим условие : .

6⁰. Следующая точка находится по формуле

.

Подставим полученные выражения для координат в : . Найдем минимум функции по с помощью необходимых условий безусловного экстремума:

Отсюда . Так как , найденное значение шага обеспечивает минимум функции по .

Заметим, что можно получить формулу для вычисления наилучшей величины шага на любой итерации из условия

.

Имеем

,

.

Из условия получаем

.

Определим : .

7⁰. Вычислим : .

8⁰. Вычислим и :

.

Вывод: полагаем k = 1 и переходим к шагу 3.

3¹. Вычислим : .

4¹. Проверим условие : .

5¹. Проверим условие : .

6¹. Определим (см. п. 6⁰).

7¹. Вычислим :

.

8¹. Вычислим и :

.

Вывод: полагаем k = 2 и переходим к шагу 3.

3². Вычислим : .

4². Проверим условие : .

5². Проверим условие : .

6². Определим (см. п. 6⁰).

7². Вычислим :

.

8². Вычислим и :

.

Вывод: полагаем k = 3 и переходим к шагу 3.

3³. Вычислим : .

4³. Проверим условие : . Расчет окончен. Найдена точка

Проанализируем полученную точку:

В примере 1 было показано, что функция является строго выпуклой и, следовательно, точка является найденным приближением точки глобального минимума .

Геометрическая интерпретация решения задачи представлена на рисунке 4.4.

Рисунок 4.4.