XIV Аттетков и др. Методы оптимизации (1081420), страница 27
Текст из файла (страница 27)
~ ягас1 1 (х ) ~ -+ 0 при 7п — + ос. Замечание 4.1. Из теоремы 4.6 не следует сходимость метода градиентного спуска, в котором используется (4.40),.к какой-либо точке. Например, функция 1" (х) = 1Д1+ ~х~з) удовлетворяет условиям теоремы, но при любом выборе начальной точки х Е Ко имеем ~х ~ — ~ оо при й — ~ оо.
Приведенный пример показывает, что функция вообще может не достигать наименьшего значения. Однако если к условиям теоремы 4.6 добавить требование ограниченности множества Хо = (х Е К"; 1(х) ( 1(хо)1, то, согласно теореме 7.1 в случае Й = К", функция 1(х) будет достигать наименьшего значения. Можно показать, что при этом последовательность 1хк1 будет сходиться к какой-либо стационарной точке функции. Некоторые особенности рассматриваемого варианта метода градиентного спуска можно выявить, если допустить нарушение отдельных условий теоремы 4.6. Так, если функция 1'(х) не является ограниченной снизу, .то нельзя утверждать, что ~8тас11(х~)~ — ~ 0 при га — ~ оо. Действительно, для линейной функции ~(х) = (с, х) при с ~ 0 имеем ! ягаб11х) ( = )с! > О.
Если выбрать х > 2/Ь, то в процессе итераций минимизируемая функция может не убывать. В самом деле, для ограниченной снизу функции )'1х) = Ьхз/2., х Е К, выполнено условие (4.41), а (4.40) принимает вид х" = хк ' — ог1''(хк ') = (1 — осЬ)хк '., но при выборе тс > 2/А получим т.е. последовательность (х ) не является релаксационной. Наконец, рассмотрим последствия нарушения условия (4.41). Функция 1(х) = ~х~ш~, где д б (О, 1), имеет точку минимума 182 4. чйсд~Б11ы~ 1~1'с1дб1 Б~~гс'.1ООБг~Й атияйии~л14ии х* = О, дифференцируема в К", но ее градиент не удовлетворя- ет условию (4.41), поскольку ~рас1((х) — цгас1~(0)) 1+6 р ~~ О. Для этой функции Ф вЂ” 6 х~ 1 д и~ь = — дгадДх~ ') = — (1+б)~х~ '~~ „, = —,, х" Поэтому при достаточно малых значениях ~х~ ~ ~, соответству- ющих приближению к точке х* минимума, из (4.40) имеем ь~ ! й 1 ~'(1+4) ь ~ (1 н(1+4) ~ ь 1~ ~ й 1~ х — ~х — ~,зх — ~ — ~,з х >х и 1(х ) > у(х ), т.е.
последовательность ((х !) не сходится к нулю. Можно показать, что предел этой последовательности > 1+4~1 — 6 равен (и ) . Не удовлетворяет условию (4.41) и диффе- 2,) ренцируемая на К" функция 1(х) = ~х~з+', е > О, имеющая ту же точку х* = 0 минимума, .так как = (2+ е) ~х(- — ~ оо при ~х~ -+ оо. (х — 0( В этом случаешь = — (2+с))х~ '!'хв ~ и в соответствии с (4.40) находим ~хь~ = )х" ~ — и(2+с)~хь ~~ х~ ~( = (1 — х(2+с)~х~ ~! ( )х~ ~/ Отсюда видно, что последовательность (х~1 сходится лишь при условии ~1 — и(2+с)~х~ ~~'~ ( 1, те. если начальная точка хв удовлетворяет неравенству х(2+ с) ~х" ~' ( 2. Один из недостатков метода градиентного спуска с фиксированным значением х в (4.40) состоит в том, что в окрестности стационарной точки х дифференцируемой функции 1 (х) 4.3.
Метод градиентного спуска 183 шаг спуска на некоторой й-й итерации может оказаться больше расстояния х — щ, т.е. при этом алгоритм .,проскакивает' искомую точку. Более того, этот шаг может быть настолько большим., что 1"(в~) > 1(а" 1) и последовательность ~жа) перестанет быть релаксационной. Избежать такой ситуации позволяет выполнение условия (4.41), существенно ограничивающее класс рассматриваемых функций, а также выбор тки б (О, 2/Л) (см.
теорему 4.6), который порождает второй недостаток этого метода: по мере приближения к стационарной точке шаг спуска тс~8тас1~(ж )~ уменьшается, что сильно замедляет сходимость последовательности 1,в ) к этой точке. Из оценки (4.42) следует, что можно избежать „прогкакивания" искомой стационарной точки, если выбрать и = 1/Л из условия максимума выражения н(1 — тгЦ2).
Однако в прикладных задачах проверить выполнение условия (4.41) и найти константу 1' обычно не удается. Поэтому вместо (4.40) используют рекуррентное соотношение ж = ж + тсьтп = жь ' — тсь дгас1~(ж~ ), Й Е 14, (4.43) и подбирают значение иа > О на каждой 1с-й итерации из условия, которое в меньшей степени, чем (4.41), ограничивает класс минимизируемых функций. В случае ограниченной снизу функции 1'(ж) для обеспечения сходимости последовательности ~~ игаса г(вк) ~) к нулю достаточно, чтобы на каждой к-й итерации для некоторого числа ые > О выполнялись неравенства Дх ) — ~(ж ) > ме(и> ~ = ссз~дгас1~(х ')~, Й Е И (4.44) В самом деле, суммируя неравенства (4.44) для 1с = 1, ти, полу- чаем ~(ж ) — ~(х ) > ще~ ~8гас1~(х" ')~ .
ь=1 Поэтому знакоположительный ряд ~„~ ягас1 1(хь ) ~~ сходится, а=1 а в силу необходимого признака сходимости его общий член стремится к нулю, т.е. ~8гас11(;вк)~ — ~ О при к — > со. 184 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАНИИ Следовательно, условие (4.44) в сочетании с (4.43) можно использовать для выбора значения кь. Существуют разные способы такого выбора*. Ограничимся рассмотрением двух из них. Если функция ~(х) непрерывно дифференцируема в 2Р, то скалярное произведение (Егат1~(х), то~) = — (Егэл1 7(х), дгае1~(х~ 1)) ее градиента на антиградиент шн = — ягас1 ~(х ' ') является непрерывной функцией.
В точке хя ' оно равно — ~ше~г < О, причем равенство нулю возможно лишь в случае, когда х ь-1 стационарная точка. Ясно,что функция )'(х) убывает в направлении антиградиента до тех пор, пока это произведение остается отрицатольным. Поэтому один из способов выбора значения же на й-й итерации состоит в том, чтобы в (4.43) х~ была ближайшей к х"-1 точкой, в которой производная функции Дх) по направлению антиградиента обращается в нуль, т.е.
(даст~(хя), ш~) =О, к Е К (4 4б) Указанный способ называют исчерпывающим спуском (движение в направлении антиградиента щ происходит до тех пор, пока не будут исчерпаны „подряд идущие" отрицательные значения производной функции ~(х) по направлению этого вектора). "Смл Волин Э., а также: Лшенииный Б.Н., Данилин КЭ.М. Замечание 4.2.
Отметим, что точка х", найденная при помощи исчерпывэлощего спуска, может не совпадать с соответствующей точкой, найденной по мегаоду наискорейшего спуска. Показано (см. 4.4), что в случае квадратичной функиин эти точки совпадают на каждой итерации. Если функция Дх) строго выпукла в К", то в силу теоремы 3.7 функция 'еь(ж) = ~(х~ 1+ кто~) также строго выпукла. Поэтому, если стационарная точка функции фь(х) существует, то, согласно 185 4.3. Метод градиентного спуска теоремам 3.14 и 3.15, эта точка единственна и в ней функция достигает наименьшего значения.
Из (4.45) следует, что на (й+1)-й итерации новое направление исчерпывающего спуска, определяемое антиградиентом ш е = — 8гас11(ак), ортогонально предыдущему направлению. Так как 8гЫ 1(жй) коллинеарен вектору нормали в точке жй к поверхности (линии) уровня 1(а) = ~(ж ), то луч, исходящий из точки ж по направлению вектора ю = — 8гЫ 1(а ), вдоль которого на Й-й итерации происходит исчерпывающий спуск, лежит в плоскости, касательной к этой поверхности уровня в точке хй, т.е. луч касается поверхности уровня функции, проходящей через точку а~. Отметим,что если при переходе через эту точку производная по направлению йо не изменяет знак, то луч пересекает поверхность (линию) уровня ~(х) = = 1'(жй). Эти ситуации в плоском случае показаны на рис.
4.1 и 4.2. Рис. 4.2 Рис. 4гт Замечание 4.3. Покажем, что для функции, удовлетворяющей условиям теоремы 4.6, существует такое число ыо, что при исчерпывающем спуске на каждой итерации будут выполняться неравенства (4.44). Для этого используем формулу Тейлора с остаточным членом в форме Лагранжа зт( й) зт( й — 1) ( „а1У( й — 1 +Д( й й — ~)) й й — 1) 186 4.
ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ где с9 Е (О, 1). Отсюда, учитывая (4.43), получаем 9" (хь ') — 9" (х~) = — нь(бгас1Д1хь ~+с9(х~ — х~ ~)),. со~). Точка х~ 1+ д(х~ — хь 1) на прямой исчерпывающего спуска является промежуточной между х~ ~ и х~. Производная по направлению св в этой точке отрицательна, и поэтому (рас19(х +с9(х — х )), св ) = с = !се~/ (8гас1~(х~ '+д(хя — х~ ')), ) < О. Следовательно, выбор ьсо > — нь(бгас1~(х~ '+д(х~ — х~ '))...1 > О (сссс)2 р обеспечивает выполнение неравенства (4.44).