14. Метод наискорейшего спуска. Вычисление длины шага и методы наискорейшего спуска

1 Методы безусловной минимизации. Градиентные методы (метод наискорейшего спуска).

Будем рассматривать задачу

f(x)min; xD = Eⁿ, (1)

предполагая, что функция f(x) непрерывно дифференцируема на Е^п, т. е. согласно определению дифференцируемой функции

f(x + h)  f(x)= <f '(x), h> + o(h; x), (2)

где . Если f '(x)0, то при достаточно малых h главная часть приращения (2) будет определяться дифференциалом функции df(x)= <f '(x), h>. Справедливо неравенство Коши  Буняковского

-|f '(x) h  <f ' (x), h>  |f '(x)  h,

причем если f '(u)0, то правое неравенство превращается в равенство только при h = f '(u), а левое неравенство  только при f'(u)0, где  = const>0. Отсюда ясно, что при f '(x)0 направление наибыстрейшего возрастания функции f(x) в точке и, совпадает с направлением градиента f '(x), а направление наибыстрейшего убывания — с направлением антиградиента (f '(x)).

Это замечательное свойство градиента лежит в основе ряда итерационных методов минимизации функций. Одним из таких методов является градиентный метод, к описанию которого мы переходим. Этот метод, как и все итерационные методы, предполагает выбор начального приближения  некоторой точки x₀ Общих правил выбора точки x₀ в градиентном методе, как, впрочем, и в других методах, к сожалению, нет. В тех случаях, когда из геометрических, физических или каких-либо других соображений может быть получена априорная информация об области расположения точки (или точек) минимума, то начальное приближение x₀ стараются выбрать поближе к этой области.

Будем считать, что некоторая начальная точка x₀ уже выбрана. Тогда градиентный метод заключается в построении последовательности {x^k} по правилу

x^k+1 = x^k  _kf '(x^k), _k>0, k = 0, 1, ... (3)

Число _k из (3) часто называют длиной шага или просто шагом градиентного метода. Если f '(x^k)0, то шаг _k>0 можно выбрать так, чтобы f(x^k+1)< f(x^k). В самом деле, из равенства (2), имеем

f(x^k+1) – f(x^k) = _k[- |f '(x^k) |² + o(_k) _k^-1] < 0

при всех достаточно малых _k>0. Если f '(x^k) = 0, то x^k  стационарная точка. В этом случае процесс (3) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точки x^k для выяснения того, достигается ли в точке x^k минимум функции f(x) или не достигается. В частности, если f(x)  выпуклая функция, то в стационарной точке всегда достигается минимум. Существуют различные способы выбора величины _k в методе (3). В зависимости от способа выбора _k можно получить различные варианты градиентного метода. Укажем несколько наиболее употребительных на практике способов выбора _k.

1) На луче {xЕⁿ: x = x^k  f '(x^k), 0}, направленном по антиградиенту, введем функцию одной переменной

_k() = f(x^k  f '(x^k))

и определим _k из условий

_k(_k) = inf _k () = _k*., _k>0. (4)

Метод (3), (4) принято называть методом скорейшего спуска. При f '(x^k ) 0 согласно формуле

_k' () = <f ' (x^k + h),h>

следует, что _k'(0) = - |f '(x^k)|² < О, поэтому нижняя грань в (4) может достигаться лишь при _k > 0. Приведем пример, когда величина _k, определяемая условием (4), существует и может быть выписана в явном виде.

Пример 1. Пусть дана квадратичная функция

f(x) = ½<Аx, x>  <b, x>, (5)

где A — симметричная положительно определенная матрица порядка nxn, b — вектор из Еⁿ. Выше было показано, что эта функция сильно выпукла и ее производные вычисляются по формулам

f '(x) = Ax-b; f "(x) = A.

Поэтому метод (3) в данном случае будет выглядеть так:

x^k+1 = x^k- _k(Ax^k-b), k = 0, 1, ...

Таким образом, градиентный метод для функции (5) представляет собой хорошо известный итерационный метод решения системы линейных алгебраических уравнений Аx = b. Определим _k из условий (4). Пользуясь формулой (4.2.10), имеем

_k () = f(x^k)- |f '(x^k)|² + (²/2)<Af '(x^k), f '(x^k)> , 0.

При f '(u^k ) 0 условие

_k'(_k) = -|f '(x^k)|² + _k<Af '(x^k), f '(x^k)> =0

дает

Поскольку функция _k(а) выпукла, то в найденной точке эта функция достигает своей нижней грани при >0. Метод скорейшего спуска для функции (5) описан, но для углубленного понимания приведем алгоритм.

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

Будем считать, что некоторая начальная точка x⁰ выбрана так, чтобы выполнялись условия теоремы Вейерштрасса, а именно множество С(x⁰) = {xRⁿ  f(x)  f(x⁰) } было замкнуто и ограничено.

Шаг 1. Полагаем k=0 (номер итерации), x^k = x⁰ = 0,  = 0,01.

Шаг 2. Вычисляем h(x^k) = f '(x^k), а также

_k = |f '(x^k) |.

Шаг 3. Если _k <, то перейти в шагу 6, иначе перейти к следующему шагу 4.

Шаг 4. Вычислим _k>0из условия

f(x^k - _kf '(x^k)) =

Шаг 5. Вычисляем следующее приближение

x^k+1 = x^k  _kf '(x^k).

Полагаем k:= k+1 и переходим к шагу 2.

Шаг 6. В качестве точки минимума возьмем последнее приближение

x_* = x^k,

а также в качестве минимального значения функции f(x_*) = f(x^k).