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

 

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

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

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

 

3.2.Многомерный поиск, использующий производные.

Пусть функция f(x) деференцируема в Еn . В этом разделе рассматривается итерационная процедура минимизации вида:

xk = x[k-1] + lym[k]*dk, k=1,... ,

где направление убывания dk определяется тем или иным способом с учетом информации о частных производных функции f(x), а величина шага lym[k] >0 такова, что

f(xk) < f(xk-1), k=1,2,....

Так как функция предполагается дифференцируемой, то в качестве критерия останова в случае бесконечной итерационной последовательности { xk }, как правило, выбирают условие ||grad(f(xk))||<eps, хотя, разумеется, могут быть использованы и другие критерии.

 

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

Метод наискорейшего спуска является одной из наиболее фундаментальных процедур минимизации дифференцируемой функции нескольких переменных. Вектор d называется направлением спуска для функции f в точке x, если существует такое d > 0, что f(x+lym*d)<f(x) для всех lym принадлежащих интервалу (0, d). В частности, если

то 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 и повторить основной этап.