Метод наискорейшего спуска
В этом варианте градиентного метода минимизирующая последовательность {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).