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

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

Итерационная формула процесса наискорейшего спуска имеет вид

,

или

.

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

,

решая одномерную задачу минимизации с использованием некоторого одномерного метода. В этом случае получаем алгоритм наискорейшего спуска.

Рис.

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

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

Эффективность алгоритма зависит от вида минимизируемой функции. Алгоритм наискорейшего спуска сойдется за одну итерацию при любом начальном приближении для функции , но схо­димость будет очень медленной, например, в случае функции вида . В тех ситуациях, когда линии уровня минимизируемой функции представляет собой прямолинейный или, хуже того, криволинейный "овраг" эффективность алгоритма оказывается очень низкой. Очевидно, что хорошие результаты может давать пред­варительное масштаби­рование функций.

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