Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 74
Текст из файла (страница 74)
Поскольку (ию) ез Мю(ию) — ограниченное множество, то из теоремы 2Л.2 следует, что 11ш р (и, ю»ю) = О. Равенства а-» ю» (20) и, тем самым, теорема 2 доказаны. 4. Для задачи » (и) -+ !и1; и»н (» = (и ш Ею: Г» (и) ( О, » = 1, ..., т, Г»(и) = (а», и) — Ь» = О, » = »и+ 1, ..., э), содержащей линейные ограничения типа равенств, метод возможных направлений описывается так же, как выше, лишь в задаче (2) нужно добавить еще ограничения (а», е) = 0 (» = т+ 1, ..., з). Можно заметить, что описанный в гл.
3 симплекс-метод для решения канонической задачи линейного программирования по существу является вариантом метода возможных направлений. Более того, опираясь на идеи ыетода возможных направлений, можно получить симплекс-метод непосредственно для основной аадачи линейного программирования (без ее сведения к канонической задаче). Выше во вспомогательной задаче (2) было принято условие нормировки )ю») <1 (! = 1, ..., и).
Возможны и другие условия нормировки, например, )е)ю с 1 или )Вюе) ( 1, где Вь — специально выбираемая матрица. Заметим, что при такой нормировке задача (2) уже не будет задачей линейного программирования. Тем не менее удачный выбор Вь мон»ет облегчить выбор возможного паправления убывания, ускорить сходимость метода. О других способах нормировки, о сходимости различных вариантов метода возможных направлений и других аспектах этого метода см., например, (11, 159 183 338( Упражнения. 1.
Сделать несколько итераций метода возможных направлений для аздачи минимиаации»(и) = х+ у на множестве П = (и = (х, у): Г»(и) = хю — р (О, Г»(и) = р — 1 (О) при различном вы боре начальной точки ию. 2. Вычислить несколько приближений по методу возможных направлений для задачи из примера 1 при различном начальном приближении ию, й 6. Метод линеаризации Этот метод на каждой итерации использует линейные аппроксимации минимизируемой функции и функций, задающих ограничения. Опишем его для задачи х(и) - !и(, и »н У = (и »ы (!ю: д,(и) < О, ..., д„(и) ( О), (й) предполагая, что (»', — выпуклое замкнутое множество на К" и »(»ункции з(и), я»(и)»п С'((!ю).
Пусть и, — начальное приближение, и, юи (»,. Предположим, что 1с-е приближение и„»п»»', при 310 методы минимизАции Функций мнОГих пегеменных [гл. д некотором к ) 0 уже известно. Введем функцию Фд(и) = —,) и — ид(д+ рд(у'(и»), и — ид'»» рд)0, (2) и множество Итд = ( и е= Уь: д1 (ид) + (у» (ид), и — ид)<~ О, 1 = 1, ..., т! . (3) Пусть Ит»чд 8.
В качестве й+ 1-го приближения и»т, возьмем ревпение следующей задачи минимизации: Ф,(и) -«1п1, и ~ И'». (4) Поскольку функция (2) сильно выпукла, множество (3) выпукло и замкнуто, то согласно теореме 4.3.1 задача (4) имеет, прптом единственное, решение. Задачу (4) необязательно решать точно: достаточно найти точку и«ы из условий и»+1 ен И'д.' Фд(и»+1) =. 1п1 Фд(и) + ед, ед' О. (5) к'д Если С, многогранное множество, то задача (4) представляет собой задачу квадратичного программирования и может быть решена конечношаговым методом (см. ниже э 7). Если И',— ограниченное множество, то для решения задачи (4) может быть использован, например, метод условного градиента, который будет сходиться и при з,) 0 позволит определить точку и»»» из (5) за конечное число шагов.
В общем случае аадача (5), конечно, не всегда просто решается. Метод линеаризации (5) обычно используют лишь в тех случаях, когда определение точки и,», из (5) не требует большого объема вычислений. Полезно заметить, что задача (4) равносильна задаче »уд(и) = Э ) и — (ид — ))дл (ид)) ) «1П1, из=†И'д, так как ~рд(и) — Фд(и) = рд) в" (ид)!э = сонэ», и~ Е".
Это значит, что точное решение Р» задачи (4) представляет собой проекцию точки и,— р»»'(и») на множество И'», а точка и»», иэ (5) является приближением для о». Отсюда следует, что если в (1) ограничения д»(и)<0 отсутствуют (т=О), то С=К, И'„и метод линеаризацип превратится в метод проекции градиента. Теорема 1. Пусть П» — выпуклое вал»кнутое множество иэ Е" (в частности, возможно П» = Е"); функции в'(и), у,(и) ш »и С'(П»), выпуклы на П, и птах()Г(и) — л'(о)~; шах )у»(и) — д1(о)~)<Ь)и — о)»ти, оенП»; 1В» В»» существует такая точка й ш П, что у,(й)<0, ..., д (й)<0; (6) адетод иинелРиз,щиИ 311 ,?„~ — со, У чья; числа р», е, в (2), (5) таковы, что д > О, ~лл~ У ее < ~ О < усс <~ рд < )], (7) д-е где р определяется ниже формулой (22), Тогда множество (3) непусто при всех В~О, последовательность (и,), определяемая методом (5), сходится к некоторой точке и ви От .
Доказательство. Согласно теореме 4.2.2 Вс(ид)+(Вс(ад), и — ис,) (вс(и) Уиди 1У . (8) Отсюда следует, что если и ш У, то и си Ис», так что Ус В'». По условию П Ф со, поэтому ]т» Ф Я (Д = О, 1, ...). Таким образом, при каждоы д ) О, е» ) 0 существует точка и»ас, удовлетворяющая условияас (5): например, можно взять и»ас = о», где оа — точнов решение вадачи (4]. Применяя теорему 43.1 к задаче (4) с учетом (5) иыееы (и»ас — с»1»с2 ~ < Ф»(щ+,) — Ф»(и») ( е», так что ]и»ас — о»] (]с2е». (9) Возьмем произвольпусо точку и, си Уе.
При сделанных предположениях о выпуклости и регуляеоности задачи (1) цо теореме 4.9.2 и лемме 4.9.2 напдутся такие числа Л ~ )О, ..., Л ) О, что (У'(и») + ~ ЛСВС (и»), и — и») ~0 Уиди П, с-д Л;Вс(и»)=0, 1=1, ...,да, и сиУ». (10) Подчеркнем, что в силу замечания, сделанного после формулировки следствия 2 к теореме 4.9.6, числа Л, ...,Л в (10), (11) могут быть выбраны одни н те же для всех ие си У». Далее, из условия регулярности (6) и неравенств (8] следует ВС(ид)+(г (и ), и — ид)К,В;(и) <О, 1=1, ..., зс.
(12) Возьмем в (10) и = о», уынонсиы на (3» ) 0 и сложим с (13) при и= ие. Это значит, что множество (3) также регулярно н к задаче (4) также применима теорема 4.9.2, нз которой следует, что функция Лаягража втой 3 ес задачи ьд(и, ь) = 2 ~ и — ис,]~+()д(У'(ид), и — ид'а+ „«~ $»(вс(ид)+ с д +(В;(ид), и — ид)), иск У, $=~($д, ..., $ю) елЛ„= Е+, имеет седловую точку (о», з»), оа — решение задачи (4), $ =($дд, ..., ь д)шЕ+. В силу леммы 4.9.2 д о, — и»+ (]ду' (ид) + ~~', заде» (ид), и — и, > 0 дсси ш ~~, (13) с=д зп (ВС (ид) + <ВС (ид) од ™д)) 0 С 1 ВС(ид)+(ВС(ид), од — ид) < О, С = 1, ..., т.
312 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ «ГЛ, В Получим 0 ( (гд — и,, и, — г 7 + Од (У' (и») — У' (ид), гд — и») + ю г» + Од ~~З~ Х«(д«(и»), од — и») + ~~', е«д(у«(ид), и» вЂ” гд). (16) Преобравуем и оценим каждое слагаемое в правой части (16). Для первого слагаемого имеем 1 1 1 (ид и«, и» вЂ” од) = 2 (ид — и»(' — 2 (гд — ид)~ — 2 ) и,— ид(а. (17) Далее, ив леммы 2.3Л при 7(и) = д«(и), и = ид, о ид с учетом неравенств (15) имеем Л«(гд)(Л«(ид)+ (Л«(ид), »д — ид) + Е) ид — од(а/2~ (Ь(ид — ид(«/2 (« — 1, ..., т). Отсюда для третьего слагаемого ив (16) о помощью равенств (Щ, неравенств (8) при и = гд и ХдЪО получаем Од ~ч~~~ Х«(д«(и ), ед — и ) = (1, ~чР~ й (»«(и»)+(Л«(и»), од — и»))а, «« «=« ~Ч~~ й»Е (г )( Од) )«» ! Ь'(ид — од'(е/2, ) Х*( = ~~~~~ '()«« ~. (19) '«-« «-« Наконец, для четвертого слагаемого ив (16) с учетом равенств (14), вв равенств (8) при и = и», включений и» «в У, й «и Е»+' имеем д ез ю ~ $«д(д«(и»), и — од) = ~Ч~~ а«д (д«(и,) + (д«(ид), и» вЂ” ид))— «-« «-« — $«д(д«(ид) + (д«(ид), ед — ид)) ~,5~~ ь«де«(и») к~ О.
(20) «=1 Сложим оценки (17) — (20); с помощью (16) получим О( 2 1ид — и ) — 2 )ед — и,) — 2 ) д — ид( Х Х(1 — 2 «Рд — «)Х~(дйд) ° (21) 1 Выберем Од из условий 2 (1 — 7) О < 7~~ Од< 7, (1 ( 2 ()„» ) ) = О (22) где 7и т — настолько малые положительные числа, что 7» ~ (2(1 — 7)«(Ь(1+ 2(д*(~)). Ив (21), (22) тогда имеем ) 㫠— и» (в+ 7(ид — ид)дм ! ид — и» (в, 4 =0, 1... (23) Ив неравенств (7), (9), (23) и леммы 2.3.10 следует существование ковач Польауясь неравенством (4.2.20) при и = ид, и = ид, и и», получаем оценку для второго слагаемого ()д «'Х' (и») — У' (ид), г, — и ) ~ Одй ( и« вЂ” од)в14.
(18) МЕТОД ЛИНЕАРИЗАЦИИ 313 ных пределов Пш)и,— ве(=Пш)ед — и ), 11ш(ид — од)=0. д ю »-~м »-~аа Это аначит, что последовательности (ид), (ед) ограничены. Покажем огра- ниченность последовательности ($д) иа (13) — (15). С помощью (12), (14) из (13) при и = й имеем (и» вЂ” ид+ аиду'(ид) о — ид) ~ — ~ч~~~ $1»(д',. (ид) и — о») ° = ~[еж»( — у1(ид) — (д (и ), и — и ))+$.д(д (ид)+(ус(ид) од — ид))]~ 1 1 ) ~~ $1»( — йе(и))> $1» Ш1П )Хг(и)), 1=1, ..., ю. г»ы Гагам Отсюда и иа неравенств (22), ограниченности (кд) и (ид) получаем 1 0<Ц»( ((гд — ад+()»Х'(и»), й — о»)) ~ сопа1< со, ш1п ! яг(и)) гласы )=1, ..., и.
Таким образоьь последовательность (5») ограничена. Отсюда и из (22) следует ограниченность ($»$»). Перепишем (13), (14) в виде + Х'(ид) + ~~ Лг(ид), и — о» ~а О е,— и, чьч Ьгд рд,, д е — (й; (и,) + (хг (ид), од — ид) ) = О, те ев Пе' (25) Из замкнутости бге следует, что г ен Ус, а иэ (15) при»-~-со получим «»(и„) ~0 (1=1, ...,вг). Следовательно, о ел У. Далее, иа (25) при»-ь -г.со с учетом (22) имеем < у'(гь)+ ~~~" ргл1(ае), и — га ~0 УиенСМ 1 1 р,'л,(о.) =О, 1=1, ..., ю. (26) Как следует из леммы 4.9.2 и теоремы 4.9.2, соотношения (26) означают, что гаем Уе. Вспомним, что неравенство (23) было получено для любых ое ~и У„.
В частности (23) верно и при ие = ге. Но ее — предельная точка последовательности (ид). Согласно лемме 2.3.10 тогда (ид)ч-ге. Теорема докааана. Замечание 1. Если в (5) ед = О, то согласно (9) и»+1 —— ид (» = = О, 1, ...), и неравенство (23) можно записать в виде ( ид+г — и» (з + У ) ад+ д — ид )з ~ ) и» вЂ” ие )з, » = О, 1, ..., 'тиз ш Уе Выбирал при необходимости подпоследовательности из ограниченных последовательностей (ид), (сд), ддщ,можем считать, что зти последовательности сходятся. С учетом (24) тогда 11ш вд —— 11ш од= г*, 1!ш 5 ф» Рг ~0, 1=1, ..., ег. д д ае д ао »-нь 314 мктоды мнншпизлции Функции многих пкгеыенных (гл. 3 Пользуясь произволом в выборе и» <н (Г», отсюда имеем ) иь — и» )) )и<,+ — и*), р(иь, П») >р (ид+т, ()»), 4=0, 1..
причем равенство здесь возможно лишь прп иь+ = иь — — иь <и (<». Таким оорззом, прп точной реалвзацвк описанного метода липеаризации расстояние от точки и» до множества П» влв до точки и» монотонно убывает. В то же время можно отметить, что хотя и(Х(иь))-»»'(<») =г'», ко (У(и<)) пе обязательно монотонно убывает в ие обязателько и»<и П.
Различные варианты метода лвнеарпзации описаны и исследованы в (8, 19, 21, 29, 115, 132, 150, 250, 314, 338); регуляркзозаиные форыы метода ливеаризацип для задач с веточпо задапиымв исходвыып данныыи исследованы в (86, 329). Упражнения. 1. Доказать, что если в (4) окажется и»= иь прп некотором Ь) О, то точка и» удовлетворяет кеобходвыым условвяы опы<- ыальпостп. У к а з а н в е: применить теорему 4.8Л к задаче (4), затем принять ид = гы 2. Доказать, что если выполнены условия теоремы 1, зь = О, )< = О, 1, ..., и в (4) и»=и» при некотором «~)0, то иьшП».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
