При использовании метода наискорейшего спуска на каждой итерации величина шага а k выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x [k ] -a k f"(x [k ])) = f(x [k] - af"(x [k ])) .
Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j(a) = f(x [k ] - af"(x [k ])) .
Алгоритм метода наискорейшего спуска состоит в следующем.
- 1. Задаются координаты начальной точки х .
- 2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f"(x [k ]) .
- 3. Определяется величина шага a k , путем одномерной минимизации по а функции j(a) = f(x [k ] - af"(x [k ])).
- 4. Определяются координаты точки х [k+ 1]:
х i [k+ 1] = x i [k ] - а k f" i (х [k ]), i = 1 ,..., п.
5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.
В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:
d j(a)/da = -f"(x [k+ 1]f"(x [k ]) = 0.
Рис. 2.9.
Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)
мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения
Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.
Рис. 2.10.
Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.
В этом варианте градиентного метода минимизирующая последовательность {X k } также строится по правилу (2.22). Однако величина шага a k находится в результате решения вспомогательной задачи одномерной минимизации
min{j k (a) | a>0 }, (2.27)
где j k (a)=f(X k - a· (X k)). Таким образом, на каждой итерации в направлении антиградиента 
выполняется исчерпывающий спуск. Для решения задачи (2.27) можно воспользоваться одним из методов одномерного поиска, изложенных в разделе 1, например, методом поразрядного поиска или методом золотого сечения.
Опишем алгоритм метода наискорейшего спуска.
Шаг 0. Задать параметр точности e>0, выбрать X 0 ÎE n , положить k=0.
Шаг 1. Найти (X k) и проверить условие достижения заданной точности || (x k) ||£ e. Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2.
Шаг 2. Решить задачу (2.27), т.е. найти a k . Найти очередную точку , положить k=k+1 и перейти к шагу 1.
Шаг 3 Завершить вычисления, положив X * = X k , f * = f(X k).
Типовой пример
Минимизировать функцию
f(x)=x 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)
Вначале решим задачу классическим методом. Запишем систему уравнений, представляющих собой необходимые условия безусловного экстремума
Решив ее, получим стационарную точку X*=(3;1). Далее проверим выполнение достаточного условия, для чего найдем матрицу вторых производных
Так как, согласно критерию Сильвестра, эта матрица положительно определена при " , то найденная точка X* является точкой минимума функции f(X). Минимальное значение f *=f(X*)=0. Таково точное решение задачи (11).
Выполним одну итерацию метода градиентого спуска для (2.28). Выберем начальную точку X 0 =(1;0), зададим начальный шаг a=1 и параметр l=0,5. Вычислим f(X 0)=8.
Найдем градиент функции f(X) в точке X 0
(X 0)= = (2.29)
Определим новую точку X=X 0 -a· (X 0), вычислив ее координаты
x 1 = 
x 2 = 
(2.30)
Вычислим f(X)= f(X 0 -a· (X 0))=200. Так как f(X)>f(X 0), то выполняем дробление шага, полагая a=a·l=1·0,5=0,5. Снова вычисляем по формулам (2.30) x 1 =1+4a=3; x 2 =8a=4 и находим значение f(X)=39. Так как опять f(X)>f(X 0), то еще уменьшаем величину шага, полагая a=a·l=0,5·0,5=0,25. Вычисляем новую точку с координатами x 1 =1+4·0,25=2; x 2 =8·0,25=2 и значение функции в этой точке f(X)=5. Поскольку условие убывания f(X) Выполним одну итерацию по методу наискорейшего спуска
для (2.28) с той же начальной точкой X 0 =(1;0). Используя уже найденный градиент (2.29), находим X= X 0 -a· (X 0) и строим функцию j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2 . Минимизируя ее с помощью необходимого условия j 0 ¢(a)=8·(4a - 2)+64·(8a - 1)=0 находим оптимальное значение величины шага a 0 =5/34. Определяем точку минимизирующей последовательности X 1 = X 0 -a 0 · (X 0) Пример 6.8.3-1. Найти минимум функции Q(x,y) методом ГДШ.
Пусть Q(x,y) = x 2 +2y 2 ; x 0 = 2;y 0 = 1. Проверим достаточные условия существования минимума: Проделаем одну итерацию согласно алгоритму. 1.
Q(x 0 ,y 0) = 6. 2.
При х = x 0 и y = y 0 , 3.
Шаг l k = l 0 = 0,5 Таким образом, 4 < 8, следовательно, условие сходимости не выполняется и требуется, уменьшив шаг (l=l /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска. Суть метода состоит в следующем. Из выбранной точки (x 0 ,y 0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис. 6.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д. Выразим целевую функцию Q(x, y) через шаг l. При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага Величина шага на каждой итерации определяется из условия минимума : Min( (l)) l k = l*(x k , y k), l >0. Таким образом, на каждой итерации выбор шага l k предполагает решение задачи одномерной оптимизации. По способу решения этой задачи различают: · аналитический метод (НСА); · численный метод (НСЧ). В методе НСА значение шага получают из условия , а в методе НСЧ величину l k находят на отрезке c заданной точностью, используя один из методов одномерной оптимизации. Пример 6.8.4-1. Найти минимум функции Q(x,y)=x 2 + 2y 2 с точностью e=0.1, при начальных условиях: x 0 =2; y 0 =1.
Проделаем одну итерацию методом НСА
. =(x-2lx) 2 +2(y-4ly) 2 = x 2 -4lx 2 +4l 2 x 2 +2y 2 -16ly 2 +32l 2 y 2 . Из условия ¢(l)=0 найдем значение l*: Полученная функция l=l(x,y) позволяет найти значение l. При x=2 и y=1 имеем l=0.3333. Вычислим значения координат следующей точки: Проверим выполнение критерия окончания итераций при k=1: Поскольку |2*0.6666|>0.1 и |-0.3333*4|>0.1 , то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение l при x=x 1 и y=y 1 и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска. Отличие численного метода НС от аналитического состоит в том, что поиск значения l на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений l - . В методе наискорейшего спуска
в качестве направления поиска выбирается вектор, направление которого противоположно направлению вектора градиента функции ▽f(x). Из математического анализа известно, что вектор grad f(x)=▽f(x) характеризует направление наиболее быстрого возрастания функции (см. градиент функции). Поэтому вектор - grad f (X) = -▽f(X) называется антиградиентом
и является направлением наиболее быстрого ее убывания. Рекуррентное соотношение, с помощью которого реализуется метод наискорейшего спуска, имеет вид X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
Пример
. Начиная из точки x k =(-2, 3) определите точку x k +1 методом наискорейшего спуска для минимизации функции .
Метод наискорейшего спуска (в англ. литературе «method of steepest descent») - это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции: В соответствии с рассматриваемым методом экстремум (максимум или минимум) целевой функции определяют в направлении наиболее быстрого возрастания (убывания) функции, т.е. в направлении градиента (антиградиента) функции. Градиентом функции в точке где i, j,…, n - единичные векторы, параллельные координатным осям. Градиент в базовой точке Метод наискорейшего спуска является дальнейшим развитием метода градиентного спуска. В общем случае процесс нахождения экстремума функции является итерационной процедурой, которая записывается следующим образом: где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции; Единичный вектор направления, который определяется по формуле: Константа, определяющая размеры шага и одинаковая для всех i-х направлений. Величина шага выбирается из условия минимума целевой функции f(х) в направлении движения, т. е. в результате решения задачи одномерной оптимизации в направлении градиента или антиградиента: Другими словами, величину шага определяют при решении данного уравнения: Таким образом, шаг расчета выбирается такой величины, что движение выполняется до тех пор, пока происходит улучшение функции, достигая, таким образом, экстремума в некоторой точке. В этой точке вновь определяют направление поиска (с помощью градиента) и ищут новую точку оптимума целевой функции и т.д. Таким образом, в данном методе поиск происходит более крупными шагами, и градиент функции вычисляется в меньшем числе точек. В случае функции двух переменных данный метод имеет следующую геометрическую интерпретацию: направление движения из точки касается линии уровня в точке . Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Условие ортогональности векторов направлений спуска в соседних точках записывается следующим выражением: Траектория движения к точке экстремума при использовании метода наискорейшего спуска, изображенная на графике линии равного уровня функции f(x) Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев): Траектория поиска остается в малой окрестности текущей точки поиска: Приращение целевой функции не меняется: Градиент целевой функции в точке локального минимума обращается в нуль: Следует отметить, что метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Овраг представляет собой впадину, линии уровня которой приближенно имеют форму эллипсов с различающимися во много раз полуосями. При наличии оврага траектория спуска имеет вид зигзагообразной линии с малым шагом, вследствие чего результирующая скорость спуска к минимуму сильно замедляется. Это объясняется тем, что направление антиградиента этих функций существенно отклоняется от направления в точку минимума, что приводит к дополнительной задержке в расчете. В результате алгоритм теряет вычислительную эффективность. Овражная функция Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции. Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек. Так же скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Методика расчета
1 шаг:
Определение аналитические выражения (в символьном виде) для вычисления градиента функции 2 шаг
: Задаем начальное приближение 3 шаг:
Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.
.
Правила ввода функции
где λ k >0 - величина шага. В зависимости от выбора величины шага можно получить различные варианты градиентного метода. Если в процессе оптимизации величина шага λ фиксирована, то метод носит название градиентного метода с дискретным шагом. Процесс оптимизации на первых итерациях можно значительно ускорить, если λ k выбирать из условия λ k =min f(X k + λS k) .
Для определения λ k используется любой метод одномерной оптимизации. В этом случае метод называется методом наискорейшего спуска. Как правило, в общем случае недостаточно одного шага для достижения минимума функции, процесс повторяют до тех пор, пока последующие вычисления позволяют улучшать результат.
Если пространство очень вытянуто по некоторым переменным, то образуется “овраг”. Поиск может замедлиться и идти зигзагами поперек дна “оврага”. Иногда решение невозможно получить за приемлемое время.
Еще одним недостатком метода может быть критерий остановки ||▽f(X k)|| <ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
В качестве направления поиска выберем вектор градиент в текущей точке
Проверим критерий остановки . Имеем 
Вычислим значение функции в начальной точке f(X 1) = 35. Сделаем
шаг вдоль направления антиградиента
Вычислим значение функции в новой точке
f(X 2) = 3(-2 + 19λ 1) 2 + (3-8λ 1) 2 - (-2 + 19λ 1)(3-8λ 1) - 4(-2 + 19λ 1)
Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции
f’(X 2) = 6(-2 + 19λ 1) 19 + 2(3-8λ 1)(-8) – (73 - 304 λ 1) – 4*19
или f’(X 2) = 2598 λ 1 – 425 = 0.
Получим шаг λ 1 = 0.164
Выполнение этого шага приведет в точку
в которой значение градиента 
, значение функции f(X 2) = 0.23. Точность не достигнута, из точки делаем шаг вдоль направления антиградиента .
f(X 2) = 3(1,116 – 1,008λ 1) 2 + (1,688-2,26λ 1) 2 - (1,116 – 1,008λ 1)(1,688-2,26λ 1) - 4(1,116 – 1,008λ 1)
f’(X 2) = 11,76 – 6,12λ 1 = 0
Получаем λ 1 = 0.52
- это значения аргумента функции (управляемые параметры) на вещественной области. называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам:
строго ортогонален к поверхности, а его направление показывает направление наискорейшего возрастания функции, а противоположное направление (антиградиент), соответственно, показывает направление наискорейшего убывания функции.
- модуль градиента определяет скорость возрастания или убывания функции в направлении градиента или антиградиента:
