Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 74
Текст из файла (страница 74)
вся последовательность (хь) сходится к точке е,. Отсюда и нэ (29), (30) следуют неравенства (23). Как видно из (29), равенство в (23) возможно лишь при /'(хь) = О. Тогда в силу теоремы 4.2.3 хь — — о, е Х„, и процесс (3), (21), (22) на этом заканчивается. Докажем оценку (24). Обозначим аь — †/(хь) — /„. Из (28),(ЗО) при х, = е, имеем (г/2)аг[/'(хг)[~ ( аг — а , аг < [/'(хг)[[хв — о„[, Ь = О, 1,... Отсюда с Учетом (27) полУчаем аь — аь ! > (з/2) ш!п((2 — е)/(25 ); а)[то-о,[ хая., Ь =О, 1,... Из леммы 2.6.4 тогда следует оценка (24). а|п Наконец, пУсть Х, — аффинное мнозкество, ПРи Ь вЂ” ~ со из (30) имеем [о„— х,[э ( [хо — х„[э при любам х, еХ„. В частности, в этом неравенстве можно взять х, =е, + а(Р (хо) — е,)= х, хо =о еХ,, а >О, Получим [т -о [э > [и, — о [э =[(о, — хо) — (о — хо)[э =[о — хо[э+[о — х [э — 2(о, — т, о — х ) = [о — т [з — [о„- т [з — 2а(о„— хо, Р г (хо) — е,) или [е* — хо[') 2а[о.
— Р» ( о)[ь ь за(Р» (~о) — хо о„-Рх ( о)). Отсюда с учетом равенства (4 4 2) имеем [е, — хо[э > 2а [о,-Р„(хо)[х при всех а >О. Разделив это неравенство на а > 0 и устремив а -~ оо, получим о, ='Р» (хо). Теорема 4 доказана. |З 5. Следуя [5251, рассмотрим метод, представляющий собой комбинацию несколько модифицированного метода (3), (2!), (22) и овражного метода. Возьмем начальные пРиближениЯ: со Е Е", Ьо — — 1, а ! > О, положим х ! — — ь . ПУсть длЯ некотоРого Ь ) 0 Уже известны оь Е Е", Ь„> 1, аь ! > О, х. ! Е Е". ОпРеделим наименьший номер з > О, для которого выполняется неравенство /("ь) /(оь 2 аь - |/ (оь)) > 2 "ь — |[/ ("ь Нэ.
(31) аь = аз — |/2 хь ="ь аь/("ь) (32) г —— кг( ч-у4Ьь+1/, оь ! — — х, + ь — (х — х ). у' / -~- ь Ь„, ь ь — ! . (зз) Таким образом, в описанном методе (31)-(33) спуск из точки оь на гдно оврвгаь осуществляется по формулам (31), (32) с помощью одного шага градиентного метода (3) с правилом выбора параметра аь, близким к (21),(22).
Здесь возможно использование некоторых других вариантов градиентного метода: по аналогии с (8) в (32) моькно взять аь — — 1/Ь. Как видно из (ЗЗ), пересчет точки оь осуществляется с помощью овражного метода по формуле, близкой ). р р ( ) представляет собой правило пересчета длины овражного шага; что величина Ьь ь ! являетсв полозкительным корнем квадратного уравнения э — — Ьэ — О, х — х — ь — —, так Ььх„-бьг,=Ь„Ьо=1, Ьь>О, А=О,|,... э (34) С помощью индукции нетрудно получить оценку ь.>ь, (35) Теорема 5.
Пусть функция /(х) выпукла наЕ, /(х) ЕОП'(Е"), /„> — со, Х э!Я, последовательность (хь) определена методом (31)-(33). Тогда О(/(хь) — /. <(ш|п(1/(25); а !)) '(2ао(/(х ) /) 4 + !п1 [х — х [Э)/(2ЬЭ) = О(1/ЬЭ), |г =1,2,... (36) Доказательство. П сть '> о 246 Гл. 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЪ|Х $1. ГРАДИЕНТНЪ|Й МЕТОД 247 это неравенство доказывается так же, как (26) при з = 1. Отсюда следует существование номера г < г, удовлетворяющего неравенству (31). Рассуждая так же, как при доказательстве оценки (27), из (31), (32), (37), (ЗЗ) с помощью индукции получаем а„> пнп(1/(25); а |], й = О, 1,... Обозначим р = (Ьь — 1)(х. | — хь).
Тогда из (ЗЗ) следует (40) эы, — — хь — рь/Ьь и рь — — Ьь+ |(хь — оь „) Далее, с учетом (32), (40) имеем рь а | — хь т | — — (Ъ| + | — 1)(хь — хь ~ | ) — хь т | — — Ьь т | (хь — ха + г ) — ха —— = Ь„(х — оы -~- аь,/'(оа „)) — хь — — рь — хь + аь, г Ьы/'(оь + |) Тогда для любого х„е Х„получаем ]Рь н — х |+х„]2=]Р, — хь+х„]2+2а | ьы (/ (оы), Рь — хь+х„)ч-о~с | 62 | ]/ (е |)]2, или с учетом (40) !Р „— х +х„!2 — ]Р„-хь-1-т ]2=2аь+|(/г(эа |),(ьыРь-Рь)+(Рь — ььэ|хь)+6ых„)ь Ч- ог,,Ь2, |]/г(оьтг)]2=2а.,(6,|-1)(/ (оы),Рь) + +2аь„гьы(/(оь+|), х,-чы)го~ьщь~ь.
|]/(хь„~)]2, й =О, 1,... (41) Заметим, что (31) с учетом (32) можно переписать в виде Пеь)-/(хь) > (а /2)]/ (оь)]2, Для й + 1-й итерации это неравенство имеет вид 1 /( ь+|) > Лхь+г)+йоьэ|]/( ьт|)! Из теоремы 4.2.2 с учетом (42) получаем (/(эьт|) х оьт1)</(х) — /(еь+~)</„ /(хь+~) 2аьэ|!/(эь+|)! . ( 3) Далее, из теоремы 4.2.2 и из (40), (42) следует (аь „/2)]/г(оь ы)]г < /(о„,) — /(х„+,) < /(хь) — (/'(эь „), х„— о„+,) — /(хь „) = = /(хь) — /(хы) — (/~(па + |), рь)/Ьь+ | откуда (/ (е г), р ) < Ь„+ |!(/(хь) — /(ха+ г)) — (ай+ |/2)]/(ей а |)]~]. (44) Обозначим аь — — /(хь) — /,, Подставим оценки (43), (44) в (41).
С учетом (32), (34) получим Ч;! ]Рь ха+ х.! < < 2оы(ьы — 1)6а „~(оь — оь „~ — (аь„~/2)]/'(еь „г)]~)Ч- 2 2 2 г + 2аь+ | Ьь+ г( — кь+ | — (аь ь г/2)]/ (еь+ ~ 5 ) + оь+1Ьы]/ (оь+ ~)! г 2 2 2 =2а, |Ььаь — 2а „~ай+|(ба+62+|)<2аьЬьоь — 2аь+|Ь +|оь+|. Таким образом !Рю „| — х „-1- х,]2 — ]р — х + х !2 < 2о Ьг о — 2а |6~~ |ахь и т=0,1,... Суммируя эти неравенства по гп от 0 до некоторого пг = й — 1, получим !Рь — хь + х ]2 + 2аь 6~~аз < 2ооьогао.|- ]Ро — хо + х]2.
Отсюда с учетом равенств Ь = 1, ро = О, оценок (35), (39), произвольности выбора точки х„ из Х„ прикодим к оценке (35), Теорема 5 доказана. О Отметим, что метод (31)-(33) не обеспечивает монотонное убывание функции /(х) на последовательностях (хь], (оь). Сравнение оценок (24) и (Зб)показывает, что для выпуклых гладких задач овражный лгетод имеет более высокую скорость скодимостн, чем градиентный метод (3), (9). В !523] показано, что оценка /(хь) — /, = 0(1/йг) является неулучшаемой на этом классе функции среди всех методов, использующик лишь значения /(х), /'(х). 6. Остановимся на непрерывном варианте градиентного метода. В этом методе вместо итерационного процесса (3), порождающего траекторию (х„), которая зависит от дискретного времени й = О, 1, , за основу берется система дифференциальных уравнений: *(С) = -а(6) /'(х(6)), 6 > О, (45) где сг(6) > 0 заданная функция (парамету метода).
Эта система описывает движение материальнои точки, движущеися в силовом поле, задаваемом антиградиентом ( — /'(х)), со скоростью х(6), пропорциональной антиградиенту в точке х(6). Сразу заметим„что итерационный процесс (3) представляет собой известный метод ломаных Эйлера для приближенного определения траектории системы (45), выходящей из точки х(0) = х . По аналогии с теоремами 1-3 можно надеяться, что при некоторых ограничениях на функцию /(х), сг(г) траектории х(6), 6 > О, системы (45) при больших 6 притягиваются ко множеству Я, = (х 6 Е";,/'(х,) = 0) стационарных точек задачи (1) или, в лучшем случае, ко множеству Х„решений задачи (1).
Очевидно, все точки множеств Я„Х являются точками равновесия (стационарными решениями) системы (45). Приведем две теоремы о сходимости метода (45), Теорема 6. Пусть функция /(х) е С' '(Е"), выпукла на Ж", /„> — со, Х.фЯ, а функция сг(6) непрерывно дифференцируема при 6 >О, сг(6) > а >О, сг'(6) <0 ЧЬ > О. Тогда траектория х(6) системы (45) с любьик начальным условием х(0) = х определена при всех 6 > 0 и существует точка гг, е Х, такая, что !пп х(6)=о„ !пп х(1)=0, г э Г +со !пп /(х(6))= /(и„)=/., ]!щ /'(х(6))= /'(п„)=0.
Доказательство. При выполнении условий теоремыО< аз( се(6)( < а(0) и правая часть ( — сг(6)/'(х)) дифференциального уравнения (45) удовлетворяет условию Липшица по х, непрерывна по совокупности аргументов (Й х). Тогда задача Коши для уравнения (45) с начальным условием х(0) = х имеет решение х = х(6), определенное при всех 6 > 0 (см, ниже теорему 6.1.1).
Возьмем Чх, 6 Х, и умножим (45) скалярно на х(6) — х,: (*(6),х(6» - . = -2' "2!х(6) - х.>' = --(6)(/'(х(6)), х(6) - х.> Отсюда с учетом равенства /'(х,) = О, условия сг(6) > 0 и теоремы 4.2.4 имеем: — „2)х(Ь) — х,]2= — 2<г(6)(/'(х(6))-/"(х,), х(6) — х,) (О ЧЬ >О. Таким образом, функция ]х(6) — х.!2 не возрастает при 6 > О, т. е. ]х(6) — х,>2 ( ]х(т) — х,]~ ЧЬ > т > О, Чх, Е Х„.
(46) В частности, при т=О: ]х(6)-х,]<]хо-х,!, т. е. траектория х(2) ограничена равномерно на 6 > О. Далее, умножим уравнение (45) скалярно на х(6): ]х(2)!' = — сг(6)(/'(х(6)), х(6)> = — а( ь) †(/(х(6) †/(х„)), 6 > О. 249 248 Гл. 5. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $1, ГРАДИЕНТНЫЙ МЕТОД (48) Интегрируя зто равенство и преобразуя по частям, получим: с с с ') ]Х(т)]2С[т = — СС(т)(у(Х(т)) — у"(Х„))! + ) ас(т)(/'(Х(т)) — у" (Х.))С[т.
о т=е Так как 0 < ссо < ст(2) < сс(0), сх'( с) < О, 1'(х(о)) — 7(х.) > 0 ссс2 > О, то с 1 ]х(т)]™т < сс(0)(л (хо) л (х,)) Чо > О. о Это значит, что ) ]х(т)]зс[т < оо. Тогда найдется последовательность (гс)— о — +со, что (х((с)) — О. Так как ]х(т)] ограничено при 1 > О, то, пользуясь теоремой Больцано — Вейерпстрасса, можем считать, что х(4,.) — о у., Из (46) при 2 = йс — о со с учетом !!|п сх(1) > ао > 0 получим 7"'(п„) = О. Отсюда и из выпУклости У"(х) слеДУет, что У„Е Х„, Из (46) пРи т = Ьс, х, = ью имеемс ]х(2) — у„]2 < ]х((с) — у,]2 172 > (с Переходя к пределу сначала при 2 — +со, затем з — о со, отсюда получим 1пп х(2) = у„. Тогда 1нп Г(х(Ь)) =7(у,) = С оо * с х — 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
