Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции f в точке x, если существует такое d > 0, что f(x+lym*d)<f(x) для всех lym принадлежащих интервалу (0, d). В частности, если
f(x+ld)-f(x)
lim -------------------< 0, при lym->0+
lym
то d - направление спуска. В методе наискорейшего спуска осуществляется движение вдоль направления d, для которого ||d|| = 1 и которое минимизирует приведенный выше предел. Если f дифференцируема в точке x и grad(f(x))!=0, то -grad(f(x))/||grad(f(x))|| является направлением наискорейшего спуска. В связи с этим метод наискорейшего спуска иногода называют градиентным методом.
Алгоритм метода наискорейшего спуска
При заданной точке x алгоритм наискорейшего спуска заключается в реализации линейного поиска вдоль направления -grad(f(x))/||grad(f(x))|| или, что то же самое, вдоль направления -grad(f(x)).
Начальный этап. Пусть eps > 0 - константа остановки. Выбрать начальную точку x1, положить k=1 и перейти к основному этапу.
Основной этап. Если ||grad(f(x))|| < eps , то остановиться; в противном случае положить dk = -grad(f(x)) и найти lym[k] - оптимальное решение задачи минимизации f(xk + lym*dk) при lym >= 0. Положить x[k+1]=xk+lym[k]*dk, заменить k на k+1 и повторить основной этап.
