Ф.П. Васильев - Методы оптимизации (1125241), страница 82
Текст из файла (страница 82)
Предварительно докажем несколько лемм Лемм а 1. Пусть Х(х), д (х) с С! '(Х), ! = 1,, т, и Х вЂ” некоторое фиксированное множество номеров, гзять!х из (1, 2,..., т) (гозмотнности /= й! или 1 = (1,..., та) не исключаются). Для казхдого х с Х положим о(х) = ппп а, где С(х) = ((е, а) = (е ',... а(*1 ..., е", о) е Е» . (Х'(х), е) < о, (д (х), е) < о, ! с/; !ез! < 1, у = 1,..., и), Тогда )о(и) — а(е)! < Ьчгп!и — е/, е, е С Х, (1 где Ь вЂ” константа Липшида для градиентов Х'(е), д,.'(х), !' = 1,..., т До к аз а т ель с та о. Возьмем произвольные тачки и, ос Х.
Пусть (е, а) е С(е), т, е. (Х'(е),е)<а, (д/(е),е)<а, !'ей )ег!<1, !'=!,...,п. (Х!(и), е) = (Х~(е)> е) + (Х (и) — Х~(е), е) < а + Ь !и — е)!е ! < о ч-Ь )и — е! /и (д! (и), е) < (г + Ь !и — е)~/и, ! е А это значит, что при каясдом (е> о) е с(е) точка (е, а+ 7 егй!и — е!) прннадлехсит множеству С(и). Тогда о(и) = т!и о < а+ Ьчгп)и — е! для любых (е, о) е С(е). Следовательно, а(и) < о( ! < а(е) ь ь ч/и!и - е / поменяв в этих рассуждениях точки и е ролями, получим а(е) < о(и) + + ь |/и!и — е/, из последних двух неравенств следует неравенство (! б).
ш Лемма 2. Пусть Х(х), д!(х),, д,„(х) е С!' (Х), Ао —— тах зир )д! (х)! < оо, «Х а последовательности (хь), (ег), (аь), (!Зь), (гь), (аь) олределень! условиями (2), (3), (б), (13)-(15). Тогда /1, > А! и!п(гл, )оь!), Ь =О, 1,..., (17) где А! — — т!п(1/(Аот/п)11/(пЬВ > О, Ь вЂ” константа Липшиуа дгя градиентов Х'(х), д! (х),..., д (х). 276 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ До к а з а те л ьст а о.
Если /Уй =со, то неравенство (17) аерно. Поэтому пусть )Зй <са. Из определения (4) аеличины |3, и замкнутости Х следует, что х» 4 |За ей и Х н д (хй ч-|Зй ей) = 0 хотя бы для одного номера с. Зафиксируем один нз таких номероа с. Может оказаться, что д (х ) < — е Тогда г„<-д(х )=де(х..||3»е»)-дс(х»)=(д/(хй-|В/Уйе»),/Уйгй) <Ао/Уй)ей!< < Ао'/пдй, т.
е. дй > гй/(Аосгп) Если же оказалось, что -г, < д (хй) < О, то с ц 1» и (д/(х»), ей ) < а» < О. Допустим, что а» < < О. Тогда направление ей является возможным в точке хй н заведомо /Уй > О, По определению /)й имеем у(хй 4 аей) < 0 при всех а, 0 < а < /3». Кроме того, д(х» 4 /Уй ай) = 0 по выбору номера с, Тогда 0) д (хй + ае,) — д (х, -| Вйгй) = (у г(хй -| /Уйе»), е)(а — |3 ) |- а(!сг — |У !) нли (д,'(хй -|-/)йай), е») ) а((а — /Уй!)(дй — а) | при асех а, 0 < а < |У, Отсюда при а — г — г д — 0 полУчим (д (х. 4/У,гь), е ) >О.
Тогда !ай(= — а» < ( — д,'(х»), гй) < (ду(х»+|З»ей)- — д,.'(хй), е,) < Г/Уй(гй) < Г и/Уь, т, е. /У > /ай(/(п5), Если ໠— -О, та последнее неравенства также остается верным, так как согласно (4) асегда /)й ) О. Объединяя обе полученные оценки для )Зй, приходим к оценке (17). Лемма 2 доказана. О Лемма 3, Пусть /(х), д,.(х) ц С~ '(Х), с =1, .. ч т.
Пусть, кроме того, в процессе (2), (3), (6), (13) — (15) на некоторой й-й итерации оказалась ай < -гй. Тогда /(хй) — /(хй „|) > Аз т!п(ГУй(ай!; айз) — бй, (18) гдг Аз — — са!л(1/2; 1/(2пь)) > О. Доказательство. Из неравенства а» < — г» н определения г»,ай следует, что (/'(х,), г») < ай < -гй < О. Кроме того, ей является возможным направлением в точке х» и, следовательно, Вй > О, Иэ (6) н леммы 2.6.1 имеем /(хй) — /(х„+ |) > /(хй) — |п| д»(а) — 6» > /(х») — /(хй + агй) — 6» > О< а <с>, > — а(/'(х ), г,) — а~Г !г /з/2 — б, > -аа„— атп/2 — 6, (19) при всех сг, 0 < сг < |Уй, Положим здесь а = ш)п(дй,' !а»(/(пГ )).
Может случиться, что а = |З, < (ай(/(пГ ), Тогда из (19) получаем /(х,)-/(хй |))а(а,! — а ° а п5/2-бй > Д (ас,! — /)й((ай!/(пГ ))(пб/2)-бй —— |Зг,(ай(/2 — бс, Если же а = )ай(/(пГ ) < |3», то из (19) следует /(хй) — /(х» |) > ай/(пй) — (ай/(пО) )(пЦ2) — б = а»/(2пГ,) — бй Объединяя оба рассмотренных случая, приходим к оценке (18). П Теорема 2. Пусть функции /(х), дс(х), с =1,...,т определены и вьслунлы на Вь, выналнено Условие СлейтеРа (4 915); /(х), д(х) ц С|''(Х), Ао — — шах эиР(дс(х)( < |<с<' х < сю, Пусть задача (1) имеет решение, т. е. /, > — оо, Х, Т' сс>, и начальная тачка ха б Х такова, чтамнагхестго Мг(ха) =(х; х ОХ, /(х) </(хо)+б) ограничено, Тогда при любам выборе го > 0 для последовательности (х»), определяемой условиями (2), (3), (6), (13) — (15), снраввдлиеьс равенства 1|в /(хй)=~;, !пп р(х, Х„)=0.
(20) й со й сь До к аз а т ель ст во. Сначала установим, что йш (/(х») — /(хй |)) = О. й сю (21) /(х,, „ |) < /(х» ) -|- бй, й = О, 1, и 2, бй — †< со. й=о (22) и, кроме того, /(х ) > Г'„> -со, й =О, 1, Согласно лемме 2.6.2 тогда существует Вш /(хй) > /„. Ото|ода следует равенства (21) Если а» < — г», то иэ (14), (6) имеем /(хй |) = д»(ай) < д»(0) + Ỡ— †/(х») + бй. Если же -г» < ай < О, то из (1 5) следует /(х, „|) = /(хй) < /(хй ) ч- б, Таким образом, !|сс> г(хг, )= 1нп сгй =О=сг(х ), где а(х )= |и| а, О(х )=((е, а)<В +|; (/ ( ) е) < ~( а, (У, (х ) г е) (~ аг с ц Г; (гу) < 1, 3' = 1,, и) Рассмотрим задачу (7), соответстауюшую точке х = !сш х . Покажем, что И" С С(х,).
По й„' определению множеств 1=1й =(с: ! < с <г, -гй <д (хй ) <О), г= 1,2,... Отсюда при г — гоо получим д;(х,) = 0 для всех с ц 1. Это значит, что 1 С /„т, е. в определении мнолсествв Иг, число ограничений типа неравенств не меньше, чем число таких ограничений в определений С(хг). Тем самым установлено, что И', с С(х„) А тогда, замечая, что одна и та лсе функция на более широком множестве имеет меньшую нижнюю грань, получаем а, = |п1а > !п1 а = а(;) = сг(х,) = О, С другой стороны, (О, 0) я Иг„поэтому сг, < О, Следовательно, сг, = 0 и согласно теореме 1 имеем хг б Х,. Выше было доказано существование предела !нп /(хй). Теперь можем сказать, чему равен й ьь этот предел: !ип /(х») = !пп /(х ) = /(х,) = /,.
Таким образом, построенная последовательность (хй) минимизирует функцию /(х) на мно>кестве Х. Поскольку (хя) и Мг(тс>) — ограниченное множество, то из теоремы 2.1,2 следует, что 1нп р(хй, Х,) =О. Равенства (20) н, тем самым, теорема 2 доказаны. П 4, Для задачи $5. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 277 Далее, покажем, что 1ссп гй гхО, Согласно (14), (|5) последовательность (г») получается дроблением и не возрастает. Допустим, что 1|ш 㻠— — е > О. Это значит, что в процессе пой го)(ьг;!",:,: стРоениЯ (хй) было конечное число дРоблений и г = г > 0 пРи асех й > га.
Иэ (14) имеем ай < -㻠— — — г, т, е, (а»! > г, й > Ьо. В этом случае согласно лемме 2 имеем В» > А | а, й > Ьо, ПаэтомУ иэ леммы 3 полУчим /(хй) — /(х |) > Азвсп(А|га; гз) — 6,, й > йа, что противоречит равенству (21). Итак, показано, что )йй г = 0 й ьэ Пусть й! < Ьд «... й, <... — номера тех итераций, когда происходит дробление гй. Согласно (14), (1о) тогда -г» < с <О, г = 1,2,, Следовательно, |ип а =О.
Тем самым с у танавлена, что существует хотя бы одна падпоследовательность (ай ), сходящаяся к нулю. -Р~ ф Возьмем произвольную подпоследавательность (а» ) ->0. Покажем, что тогда любая пре. дельная точка соответствующей подпоследояательнасти (х ) принадлежит множе Х, й„ т мно еству Из (22) следует, что /(х, ы) < /(х>) + 6, й = О, 1,..., т. е. (х ) б М (х>). По условию мне * сс",!',"'. жество Мг(хо) ограничено, Поэтому можем считать, что взятая выше падпоследовательность (хй ) сходится к некоторой точке х„.
Далее, множество номеров 1», определяемое согласно (13), представляет собой подмножество конечного числа номеров (1, 2,...,>П, поэтому число различных множеств Гй конечно. Это значит, чта среди (Гй, г †- 1, 2,...) найдется хотя бы одно множество 1» = 1, которое повторяется бесконечно много рвз. Выбирая при необхо димости падпоследовательностн,можем, таким образом, считать, что (ай )->0, (хй ) — г х„1|, — -1 г= 1,2, Согласно лемме 1 при С(хй ) = Игй имеем (а — а(х„)) = (а(х> ) — а(х )! < Г,/п(х — х,(-ь О, 5), " сс(гу /(х)>|л1 хчХ=(хцВ"; д;(х)<0 >=1 ... т, дс(х)=(а.,х)-Ь =О, с=т+1,. г), содержащей линейные ограничения типа равенств, метод возможных направлений описывается так же, как выше, лишь в задаче (2) нужно добавить еще ограничения (ас, е) =О, с=т+1,...,э.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
