Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 72
Текст из файла (страница 72)
Сделанное замечание о критериях окончания счета относится и к другим излагаемым ниже методам. В теоретических вопросах, когда исследуется сходимость метода, предпо- лагается, что процесс (3) продолжается неограниченно и приводит к после- довательности (хй), Здесь возникают вопросы, будет лн полученная после- довательность (хй ) минимизирующей для задачи (1), будет ли она сходиться к множеству точек минимума Х„= ( х е Е", /(х) = /„=!и! /(х)~ или, иначе говоря, выполняются ли соотношения 1пп /(хй)=/„, 1!ш р(х, Х,)=0. (11) Для положительного ответа на эти вопросы на функцию /(х), кроме усло- вия /(х) е С'(Е"), приходится накладывать дополнительные более жесткие ограничения.
2. Подробнее рассмотрим эти вопросы для метода скорейшего спуска, когда в (3) величина стй выбирается из условия (6). Теорема 1. Пусть /„=!и!/(Х) > — со, /(х) е С''(Е"), Тогда по- слгдозатгльность (хй), полученная методом (3), (6), при произзольном начальном приближении х такова, что !пп /'(хй) =О. Если при этом множество М (хь) = (х Е Е": /(х) < /(х0) + б), гдг б взято из (6), огра- ничено, то !!ш р(Х„Я„) = О, гдг Я, = (х е М,(х ): /'(х) = О) — множество й «« стационарных точек функции /(х) на М,(х,). Дока з а тел ьот в о. Если при некотором й ~0 окажется, что /'(хй) = = О, то из (3), (б) формально получаем хй = х,й, =... и утверждения тео- ремы становятся тривиальными. Поэтому будем считать, что ~'(хй) ф 0 при всех й =О, 1,... Так как Х(хй+,)=дй(стй)< !и! дй(а)+бй< Г(х — сйу'(хй)) (-бй при всех а >О, то из неравенства (2.6.7) при у=хй, х=хй-ст/'(х ) имеем /( й) — /( '' ) > /( .) — /( й — '/'(хй)) — б.
> > о)Х'(х )!' — Х ст')Х'(х )!'/2 — 6 > ст(! — ЕтХ/2ИГ'(х )! — 6 при всех а > 0 и й = О, 1,... Следовательно, /(хй) — /(хй„,) > шах ст(! — ЕтХ/2))Г'(хй)!т — бй «« «ьь = (1/(2Х ))!/'(Хй)!т — бй, й = О, 1,, (12) /(хйт,) </(хй)+ б, й =О, 1, Так как /(хй) > /. > — оо, й =О, 1,..., то из леммы 2.6.2 и (13) следует существованйе предела !пп /(хй) > /,. Тогда !пп (Х(хй) — /(хй„)) = 0 и й «« й «о из (12) будем иметь 1!ш /'(хй) =О. Наконец, пусть множество М,(х ) ограничено. Суммируя неравенст- ва (13) по й от 0 до тп — 1, получим /(х )</(Х0)+ ~, 'б </(те)+б, та=1,2,..., т. е.
(Хй) я М,(х ). По теореме Больцано — Вейерштрасса ограниченная последовательность (хй) имеет хотя бы одну предельнуто точку. Пусть х, — произвольная предельная точка (х,,) и (х, ) — х„. Пользуясь непрерывностью /'(х), отсюда имеем 1пп /'(хй ) =/'(х,) =О, т. е. х„е Я., Так как расстояние р(х, Я,) непрерывно (см, лемму 2.1.2), то !Ип р(хй, Я,) =р(Х„Я„) =О. Отсюда следует, что числовая последовательность (р(х„Я,)) имеет единственную предельную точку, равную нулю, т. е.
1пп р(Х„Я,) = О. Теорема 1 доказана. П Теорема 2, Пусть выполнены всг условия тгоргмьй 1 и, кроме того, функция /(х) выпукла на Е". Тогда, для последовательности (хй), определяемой условиями (3), (б), имеют место соотношения (11). Если, кроме того, з (6) (б„) = 0(й '), то справедлива оценка О < /(хй) — /. < с,й-', с0 = сопз( > О.
(14) Доказательство. Из ограниченности М„(х ), непрерывности /(х), согласно теореме 2.!.2, имеем /„> — со, Х„~ О, Х„с М,(х ). Тогда для любой точки х, е Х. с помощью неравенства (4.2.4) получаем 0 < Х(хй) — /„= /(х ) — /(х,) < (/'(хй), хй — х,) < < !/'(Хй)( )хй — х ! < д)/'(хй)~ й =0 1, (15) где й( > с!ашМ,(х0) = зпр )и — о) — диаметр множества М,(хь). В те, « « м ий) ореме 1 было доказано, что 1!тп /'(хй) = О.
Отсюда и из (15) следует, что й «« !Ип /(хй) =/.. Учитывая включение (хй) Е М,(х ), тогда с помощью теорей «« мы 2.1.2 получаем второе из равенств (11). Докажем оценку (14). Обозначим а, =/(хй) — /,. Из неравенств (12), (15) имеем а. — ай „= /(хй) — /(хй й,) > (1/(2Х )) 1/'(хй) )з — бй > азй/(2Х дз) — б,. По условию бй = 0(й з), т. е. 0 < бй < с, й ', й = 1, 2,..., с, = сопз1 > О.
Полагая А = шах(с,; 25д'), получим ай „, < ай — азй/А + Ай з, й = 1, 2,... Отсюда и из леммы 2.6.5 при Х =(1,2,...1, Х, = О следует оценка (14). Если бй ««О, й = О, 1,..., то оцейка (14) вытекает из неравенств (12), (15) и леммы 2.6А. Теорема 2 доказана, П 240 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МГ!ОГИХ ПЕРЕМЕННЫХ $ !. ГРАДИЕ|-!ТНЪ|Й МЕТОД 241 Теорема 3. Пусть /(х)Е Срл(Е"), Х(х) сильно выпукла на Е .
Тогда для последовательности (х„), получаемой из (3), (6) при любом начальном приближении х, справедливь! соотношения (11). Если при этом Б» = 0(й '), то имеет место оценка (14), Если 5» =О, й =О, 1, то верна более сильная, чем (14), оценка 0 < /(х») — /, < (Х(х ) — Х.)д", (16) |х„ — х,|Р ( (2/гр)(/(хь) — /„)д», й = О, 1,..., (17) где х, — точка минимума /(х) на Е", д = 1 — р/Х, 0 < д < 1, !р — посто янная из теоремы 4.3,3. Доказательство. Согласно теореме 4.3.! множество М,(х) огра ничено, /. > — оо, Х состоит из единственной точки х,.
Поэтому равенст ва (11) и оценка (14) следуют из теорем 1, 2, Докажем оценки (16), (17) Из (4.3.9) при о = х„, и = х, имеем а» =/(х„) — /(х,) ( (/'(х»), х — х„) — х|х» — х„|»/2 ( |/'(х»)||х, — х,(— — х (х„— х,!'/2 < зцр (|/'(х» ) |г — хг'/2) = |Х'(х» ) |'/(2х), р»0 т. е. а„= /(х») — /(х„) < |/'(х»)~»/(2х), й = О, 1,... (18) Подставив неравенство (18) в правую часть (12) при б» =О, получим 2» и ໠— а,„, > — а» = — а»л й =О, 1,. В $ 4.3 было установлено, что и = р < Х,.
Поэтому 0 < д =1 — (!»/Х,) < < 1, и предыдущее неравенство можно переписать в виде 0 < а, < а„(1— — Г»/Х )=да,. Отсюда имеем а,<да» |<д'а„,«...д'а, что равносильно оценке (16). Наконец, из неравенства (4.3.3) следует х|х — х,|з < /(х„) — /(х,) = а„, !с = О, 1, Отсюда и из (16) получим оценку (17). Теорема 3 доказана. П Метод скорейшего спуска имеет простой геометрический смысл: оказывается, точка х»«р, определяемая условиями (3), (4), лежит на луче Х „ = (х: х = х„ — ср/'(х ), сс > О) в точке его касания поверхности уровня Г„«! = (х Е Е": /(х) = /»(х»+!)), а сам луч Х, перпендикулярен к поверхности уровня Г, = (х е Е"; /(х) = /(х,)1 — см.
рис. 5.1 и 5.2. В самом деле, пусть х = х(з), а < ! < Ь вЂ” некоторое параметрическое уравнение кривой, принадлежащей Г„т. е. /(х(!)) = Г(х») =сонэ|, а< г (Ь, причем х(ги) =х„. Тогда — /(х(!)) = (/'(х(г)), х(т)) = О, а < ! < Ь. В частности, при ! = !и имеем («Х'(х,), х(! )) =О. Это означает, что градиент (или антиградиент) /'(х») перпендикулярен к касательному направлению поверхности уровня Г„в точке х, или, иначе говоря, луч Х» перпендикулярен к Г„.
Далее, из условия (4) при сс» > 0 получаем д„'(а„) = — (/'(х„— ср„/'(х»)), /'(х„)) = =-(Х(х„!), / (хь)) =О. Но вектор / (х» «!) перпендикулярен к Г,, в точке х»» „поэтому последнее равенство означает, что направление /'(х„) и, следовательно, луч Х,„являются касательными к поверхности уровня Г «! в точке х„«! 3. Из рис.
5.1 и 5.2 можно понять, что чем ближе поверхность уровня /(х) = сопз! к сфере, тем лучше сходится метод скорейшего спуска, Это же явление можно усмотреть и из оценок (16), (17) — чем ближе И/Х, к единице (для функции /(х) = |х!', у которой поверхностями уровня являются сферы, как раз имеем р/Х = 1), тем ближе д к нулю и тем лучше сходимость. Те же рнс. 5.1 и 5.2 показывают, а теоретические исследования н численные эксперименты подтверждают, что метод скорейшего спуска и другие Рис. 5.! Рис.
5.2 варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функции /(х) сильно вытянуты и функция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции — эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага>, функция меняется незначительно (на рис.
5.2 и 5.3 изображены линии уровня «овражной» ьр Рис. 5 3 функции двух переменных). Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», н в результате приближения (х,,), получаемые градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага», Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек х„могут сильно замедлить сходимость градиентного метода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
