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

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

. (1.17)

Пусть – фиксированная начальная точка поиска, – приращение аргумента, которое обеспечивает убывание функции, причем длина этого приращения постоянна. При достаточно малых значениях , пренебрегая в (1.17) слагаемыми высшего порядка малости, имеем изменение функции

. (1.18)

В первом приближении изменение функции (1.18) равно скалярному произведению векторов и . Пусть – угол между этими векторами. Тогда

.

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

Направление антиградиента наиболее быстрого убывания функции в точке называется Направлением наискорейшего спуска. Градиент же функции определяет направление наиболее быстрого возрастания функции в точке .

Пусть – такой малый шаг вдоль линии уровня , что . Тогда , и по формуле (1.18) с точностью до бесконечно малых первого порядка . То есть в любой точке направление градиента перпендикулярно линии уровня, проходящей через эту точку, поскольку вдоль этой линии функция постоянна (рис. 1.8). Это замечание касается и антиградиента .

Метод минимизации целевой функции , в котором направление поиска определяется антиградиентом , называется Методом наискорейшего спуска. Это означает, что если на некотором шаге процесса оптимизации получена точка , то поиск минимума функции осуществляется вдоль направления . В данном методе итерации выполняются по формуле (1.13)

, (1.19)

Где – значение переменной , которое доставляет минимум функции . Обозначая и учитывая (1.19), запишем формулы итерации метода наискорейшего спуска:

, . (1.20)

Итерации продолжаются до тех пор, пока выполняется условие

,

Где – допустимая погрешность, . По формулам (1.20) составим алгоритм метода наискорейшего спуска.

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

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

Выходной параметр – конечная точка поиска.

1. Вычислить .

2. Вычислить , .

3. Положить .

4. Если , то перейти к шагу 1.

5. Остановиться.

В этом алгоритме на шаге 2 выполняется одномерный поиск минимума из текущей точки поиска в направлении антиградиента . Для повышения эффективности численной процедуры одномерного поиска производят масштабирование направления поиска и используют вектор направления единичной длины. Шаг перехода в следующую точку поиска обозначен через . Итерации продолжаются, пока длина больше заданной допустимой погрешности.

Пример 1.7. На рис. 1.9 представлена траектория минимизации квадратичной функции (1.3) методом наискорейшего спуска, состоящая из лучших точек итераций. Градиент вычислялся по формулам конечных разностей. В соответствии с замечаниями примера 1.5 о проведении одномерного поиска начальное значение шага одномерного поиска на каждой итерации вычисляется на основании двух выполненных предыдущих итераций, а вектор направления поиска масштабирован по формуле . Для нахождения точки минимума с погрешностью 10–3 затрачено 13 итераций и 80 вычислений функции.

Рис. 1.9. Минимизация квадратичной функции методом наискорейшего спуска

При выполнении точного одномерного поиска из точки в направлении вектора по (1.15) получим , то есть вектор направления ортогонален градиенту функции в точке минимума этой функции в данном направлении. Для метода наискорейшего спуска это означает, что , то есть градиенты в последовательных точках поиска ортогональны. Следовательно, траектория метода состоит из последовательности ортогональных отрезков , , , …, где – шаг перехода из точки в точку (рис. 1.9).

Пример 1.8. На рис. 1.10 представлена траектория поиска минимума функции Розенброка методом наискорейшего спуска. Процесс минимизации занял 306 итераций при 2060 вычислениях функции и прекратился при уменьшении величины шага многомерного поиска ниже значения 10-3. Точка минимума не была найдена.

Рис. 1.10. Минимизация функции Розенброка методом наискорейшего спуска

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

Метод наискорейшего спуска является простейшим, наиболее известным и самым фундаментальным методом безусловной минимизации дифференцируемых функций нескольких переменных. Поскольку в нем используется отрицательный градиент как направление спуска, он также называется Градиентным методом. Этот метод основан на первых производных целевой функции, поэтому он является методом первого порядка. Достоинством метода является его простота, но он обладает тем же основным недостатком, что и метод циклического покоординатного спуска, – низкой эффективностью при минимизации овражных функций (рис. 1.10).

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

< Предыдущая		Следующая >