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

В этом варианте градиентного метода минимизирующая последовательность {Xk} также строится по правилу (2.22). Однако величина шага ak находится в результате решения вспомогательной задачи одномерной минимизации

min{jk(a) | a>0 }, (2.27)

где jk(a)=f(Xk - a· (Xk)). Таким образом, на каждой итерации в направлении антиградиента выполняется исчерпывающий спуск. Для решения задачи (2.27) можно воспользоваться одним из методов одномерного поиска, изложенных в разделе 1, например, методом поразрядного поиска или методом золотого сечения.

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

Шаг 0. Задать параметр точности e>0, выбрать X0ÎEn, положить k=0.

Шаг 1. Найти (Xk) и проверить условие достижения заданной точности || (xk) ||£ e. Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2.

Шаг 2. Решить задачу (2.27), т.е. найти ak. Найти очередную точку , положить k=k+1 и перейти к шагу 1.

Шаг 3 Завершить вычисления, положив X*= Xk, f *= f(Xk).

 

Типовой пример

Минимизировать функцию

f(x)=x12 +4x22 -6x1 -8x2 +13; (2.28)

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

Решив ее, получим стационарную точку X*=(3;1). Далее проверим выполнение достаточного условия, для чего найдем матрицу вторых производных

f ¢¢(X)=

Так как, согласно критерию Сильвестра, эта матрица положительно определена при " , то найденная точка X* является точкой минимума функции f(X). Минимальное значение f *=f(X*)=0. Таково точное решение задачи (11).

Выполним одну итерацию метода градиентого спуска для (2.28). Выберем начальную точку X0 =(1;0), зададим начальный шаг a=1 и параметр l=0,5. Вычислим f(X0)=8.

Найдем градиент функции f(X) в точке X0

(X0)= = (2.29)

Определим новую точку X=X0-a· (X0), вычислив ее координаты

x1=

x2= (2.30)

Вычислим f(X)= f(X0-a· (X0))=200. Так как f(X)>f(X0), то выполняем дробление шага, полагая a=a·l=1·0,5=0,5. Снова вычисляем по формулам (2.30) x1=1+4a=3; x2=8a=4 и находим значение f(X)=39. Так как опять f(X)>f(X0), то еще уменьшаем величину шага, полагая a=a·l=0,5·0,5=0,25. Вычисляем новую точку с координатами x1=1+4·0,25=2; x2=8·0,25=2 и значение функции в этой точке f(X)=5. Поскольку условие убывания f(X)<f(X0) выполнено, то считаем, что найдена очередная точка минимизирующей последовательности X1=(2;2). Первая итерация градиентного спуска завершена.

Выполним одну итерацию по методу наискорейшего спуска для (2.28) с той же начальной точкой X0=(1;0). Используя уже найденный градиент (2.29), находим

X= X0-a· (X0)

и строим функцию j0(a)=f(X0-a· (X0))=(4a-2)2+4(8a-1)2. Минимизируя ее с помощью необходимого условия

j 0¢(a)=8·(4a - 2)+64·(8a - 1)=0

находим оптимальное значение величины шага a0=5/34.

Определяем точку минимизирующей последовательности

X1= X0-a0· (X0) .

Первая итерация завершена. Подсчитав компоненты вектора (X1)

можно убедиться, что скалярное произведение

< (X0), (X1)> ,

то есть что Х1 – точка минимума функции (2.28).