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

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

Правила ввода функции

В методе наискорейшего спуска в качестве направления поиска выбирается вектор, направление которого противоположно направлению вектора градиента функции ▽f(x). Из математического анализа известно, что вектор grad f(x)=▽f(x) характеризует направление наиболее быстрого возрастания функции (см. градиент функции). Поэтому вектор - grad f (X) = -▽f(X) называется антиградиентом и является направлением наиболее быстрого ее убывания. Рекуррентное соотношение, с помощью которого реализуется метод наискорейшего спуска, имеет вид X k +1 =X k - λ k ▽f(x k), k = 0,1,...,
где λ k >0 - величина шага. В зависимости от выбора величины шага можно получить различные варианты градиентного метода. Если в процессе оптимизации величина шага λ фиксирована, то метод носит название градиентного метода с дискретным шагом. Процесс оптимизации на первых итерациях можно значительно ускорить, если λ k выбирать из условия λ k =min f(X k + λS k) .
Для определения λ k используется любой метод одномерной оптимизации. В этом случае метод называется методом наискорейшего спуска. Как правило, в общем случае недостаточно одного шага для достижения минимума функции, процесс повторяют до тех пор, пока последующие вычисления позволяют улучшать результат.
Если пространство очень вытянуто по некоторым переменным, то образуется “овраг”. Поиск может замедлиться и идти зигзагами поперек дна “оврага”. Иногда решение невозможно получить за приемлемое время.
Еще одним недостатком метода может быть критерий остановки ||▽f(X k)|| <ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.

Пример . Начиная из точки x k =(-2, 3) определите точку x k +1 методом наискорейшего спуска для минимизации функции .
В качестве направления поиска выберем вектор градиент в текущей точке

Проверим критерий остановки . Имеем
Вычислим значение функции в начальной точке 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

Пример 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 - .

Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага k выбирается из условия минимума функции f(x) в направлении спуска, т.е.

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f (x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по функции

()=f (x (k) -f (x (k)))

Воспользуемся для этого методом золотого сечения.

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

Задаются координаты начальной точки x (0) .

В точке x (k) , k = 0, 1, 2, …, вычисляется значение градиентаf (x (k)).

Определяется величина шага k путем одномерной минимизации по функции

()=f (x (k) -f (x (k))).

Определяются координаты точки x (k) :

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Проверяется условие останова итерационного процесса:

||f (x (k +1))|| .

Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.

Рис. 2.1. Блок схема метода наискорейшего спуска.

Реализация метода в программе:

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

Рис. 2.2. Реализация метода наискорейшего спуска.

Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума. Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.

Назовем некоторое направление исопряженными по отношению к некоторой положительно определенной матрице ГессаH, если выполняется:

Тогда т.е.. Значит при единичнойH, сопряженное направление означает их перпендикуляр. В общем же случае H неединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору - означает поворот этого вектора на некоторый уголи его растяжение или сжатие.

А теперь вектору векторортогонален т. е. сопряженность это не ортогональность векторови, а ортогональность повернутого векторат.е.и.

Рис. 2.3. Блок-схема метода сопряженных направлений.

Реализация метода в программе: Метод сопряженных направлений.

Рис. 2.4. Реализация метода сопряженных направлений.

Рис. 2.5. График метода сопряженных направлений.

Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.

3. Анализ методов определения минимального, максимального значения функции при наличии ограничений

Напомним, что общая задача условной оптимизациивыглядит так

f(x) ® min, x Î W,

где W - собственное подмножество R m . Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида

f i (x) = 0, где f i: R m ®R (i = 1, …, k).

Таким образом,W = {x Î R m: f i (x) = 0, i = 1, …, k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде

f 0 (x) ® min, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Если обозначить теперь через f функцию на R m со значениями в R k , координатная запись которой имеет вид f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можно также записать в виде

f 0 (x) ® min, f(x) = Q.

Геометрически задача с ограничениями типа равенств - это задача о поиске наинизшей точки графика функции f 0 над многообразием  (см. рис. 3.1).

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f 0 при ограничениях f i (x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точкахx f 0 (x*)  f 0 (x). (3.3)

Если (3.3)выполняется только для допустимыхx, лежащих в некоторой окрестности V x * точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.

Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .

Описание [ | ]

Усовершенствования [ | ]

Метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Для борьбы с этим явлением используется, суть которого очень проста. Сделав два шага градиентного спуска и получив три точки, третий шаг следует сделать в направлении вектора, соединяющего первую и третью точку, вдоль дна оврага.

Для функций, близких к квадратичным, эффективным является метод сопряжённых градиентов .

Применение в искусственных нейронных сетях [ | ]

Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.

Ссылки [ | ]

• J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)

Литература [ | ]

• Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
• С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.