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

Методы безусловной минимизации, использующие произвольные функции

Пусть функция f(x) дифференцируема в Еn. Рассмотрим итерационные процедуры min-ии вида:

х=х+p, k=1,…, хЄЕ (1)

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

f(х)<f(х), k=1,2,… (2)

Положим (1) на каждом шаге p=-f(х).

Если f(х)0, то условие: <f(х), p> <0 очевидно выполнено, т.е. направление вектора pявляется направлением убывания функции f(x), причем в малой окрестности точки хнаправление pобеспечивает наискорейшее убывание этой функции.

Поэтому можно найти такое >0, что будет обеспечено выполнение условия (2).

Приведем алгоритм метода градиентного спуска:

ШАГ 0:

Задать параметр точности >0, начальный шаг >0, выбрать хЄЕ. Вычислить f(x).

ШАГ1:

Найти f(х) и проверить условие достижения точности: ||f(х)||<. Если оно выполнено, вычисления завершить, полагая х*=х, f*=f(x). Иначе – перейти к шагу 2.

ШАГ2:

Найти у=х-f(х) и f(у). Если f(у)<f(x), то положить х=у, f(х)=f(у) и перейти к шагу 1, иначе – перейти к шагу 3.

ШАГ3:

Положить =/2 и перейти к шагу 2.

Замечание:

Вблизи стационарной точки функции f(x) величина ||f(х)|| становится малой. Это может приводить к замедлению сходимости последовательности {х}.

Теорема:

Пусть симметрическая матрица А квадратичной функции f(x) положительно определена, l и L – ее наименьшее и наибольшее собственные значения (0<lL). Тогда при любых Є(0;2/L) и хЄЕn итерационная последовательность х=х-f(х) сходится к единственной точке глобального min-ма х* функции f(x) линейно (со скоростью геометрической прогрессии):

||х-х*||q||х-x*||

где q=max {|1-l|,|1-L|}.

Дата добавления: 2014-01-07