Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 100
Текст из файла (страница 100)
Последовательно применяя этот прием далее, за конечное число шагов придем к представлению (37), а котором система (а;, ! «1(х)) линейно независима. Из (37) следует тах дй(х) > вах д/(х) > вах д;(х) = вах ((а»,х) — Ь!)= 1<!<ш ге»(п) гЕП ) !Е»(*) = вах (а», х — ю) = р(х, Х) вах (ач, л,' Л»а»). (38) (еП*) ге»(И Покажем,что величину вах (а;, Е; Л.а ), гдесистема(а», 1«1(х)»линейно независима, 'еПЕ)»<ПЕ) можно оценить снизу положительной величиной, не зависящей от х. С этой целью возьмем ЛЮбОЕ МНОжЕСтВО ИНДЕКСОВ Е С(1, .. и и!) таКИХ, Чта ВЕКтОрЫ (а», ( Е 1) Лнивйис НЕЗаВИСИМЫ, и введем множество Л» — — ((Л», ! «1); Л; )О, )" Л!а»]=1). (39) Е1 й й Заметим, что Л вЂ” замкнутое ограниченное множество. В самом деле, если Л = (Л», ! « «1) «Л», Л" и Л, то предельным переходам в (39) легко убедиться, что Л «Л». Следовательно, й Л» замкнуто.
Покажем ограниченность Л». Допустим противное: пусть найдутся Л «Л(, й = =1,2, „]Лй]-поо. Тогда последовательность рй=ЛЕ/]Лй], й =1, 2, .. и ограничена: ]р ]= 1. й Выбирая при необходимости подпоследовательность, можем считать, что (р ) и рп ]р] = 1, Поскольку ~ Л. Л, а»~ =1, то ! Л, рг а[=1/]Л" ]-ЕО= 2, "и а» где р=(рою ! «1)р0 Однако 1Е1 это противоречит линейной независимости (а», ! «1). Следовательно, Л» ограничено. На множестве Л» рассмотрим функцию д(Л,1) = шах(аг, 2 Л.
а, ). Убедимся в том, »Е» что д(Л, 1) > 0 при всех Л «Л». В самом деле, если существует Ло = (Ло, у «1) «Л, что д(Л~, 1) (О, то (а;, 2; Леа ) (0 пРи всех ( «1. Умножим эти неРавенства на Лоы ( «1, и » е1 сло»ким; получим равенство ] Е; Л» а, [ = О, противоречащее определению Л». Таким образом, о »е» д(Л,1) > 0 при всех Л «Л[. Функция д(Л, 1) полунепрерывна снизу на Л». В самом деле, пусть Л «Л», (Лй) и Л, Л ' «Л», й = 1 2,, пусть ы «1 и д(Л 1) = (о., Е' ,Л а ). Тогда » Е1 д(ЛЕ,1) =вах(а„й Л,"а ) > (аг, ', Л ау). Отсюда при й пса получим 11в д(Л",1)) уе»»е1 й ю > (ай, Е Л»а.) = д(Л, 1) ЧЛ «Л».
Согласно теореме 2.1.1 полунепрерывная снизу функция 1' Е» д(Л, 1) на компактном мноягестве Л» достигает своей ни»кней грани в некоторой точке Л„«Л», причем д,Я= )п1 д(Л, 1) =д(Л*,1) >О. Поскольку множество (1) различных подмножеств Лей, 1 множества (1,,, в), для которых векторы (а», ( «1) линейно независимы, конечно, то д, =(п( д,(1) >0 Отсюда и из (37), (38) имеем вах д+(х) > р(х, Х)д(Л, 1(х)) ) р(ж, Х)д„, П) 1<! <и или р(ж, Х) ( (1/д,) вах де(х), х «Е". Таким образом, неравенство (Зб) справедливо с 1<»<п 1= 1, М =!/д,.
Лемма 3 доказана. П Л е и м а 4. Пусть множество Х=(х «Еп! д((х)=(а», х)-Ь < О, э=!, .. Егп; д((х)=(аг, х) — Ь =О, э=в-(-1, .. пг), (40) где а! «Е", Ьг «В непусто. Тогда р(х,Х) < М вах д,".(х) Чх«Е", М=сопз1. (41) 1<1<э До к а з а тел ь с т во. Каждое ограничение д (х) =(а;, х)-Ь! =0 заменим равносильными ограничениями 511(х) = д (х) < О, йз (х) = -д (х) < 0 и воспользуемся леммой 3. Получим р(Х, Х) < М! таХ(дп(Х), .. пд~~(ж)! й,+ „,(ж),,. и 5~1(ж), йя +1(ж), ..
и йз+,(ХО. Отсюда и из й!+ (х) = вах(д»(х)' О) < ]д» (х)] = дпй(х) йэ~ (х) = шах( — дг (х); 0) < ]д (х)] = д/ (х), ! = гп + 1, .. и э, приходим к неравенству (41). Лемма 4 доказана. П Другие классы множеств (8), заданных корректными ограничениями, читатель найдет в [84,' 527; 670]. 6.
В лемме 1 был выделен класс задач (!), (8), имеющих сильно согласованную поста- новку (см, неравенства (20), (21)), Следуя [670], приведем еще один содержательный класс таких задач, Л е м м а 5. Пусть функция /(ж) на множестве Хо удовлетеоряет услоеию Гельдера [/(х) — /(у)]~(5]х — у] Чх,у«Х), 5 >О, 0<а <1; (42) ограничения, задающие множество (8), корректны на Хо и удоэлетаоряют нераеенст- эу (36).
Тогда задача (1), (8) имеет сильно согласоеанную постановку, причем неравен- ство (21) выполняется при с! —— ... — — с„= ЕМ, н = а). Доказательство. Возьмем пройзвольную точку х«Хо. По определению р(х,Х)= = !п1 [х — и] для любого е > 0 найдется такая точка х «Х, что ]х — х ] < р(х, Х) + г. Тогда пеХ г г с учетом условий (36), (42) имеем ОМЕ ~:(дй(х)) т+/(х) — /„>ЕМ ( вах д+(х)) +/(ж) — /(х,)> »=1 * 1<»<п > 5 (р(х, Х)) — 5]ж — ж,]" > 5 (р(х, Х)) — Е (р(ж, Х) + э)", Пользуясь произволом г > О, отсюда при г — и 0 получим 2,(д;+(х)) '+/(ж) — /,~)0 Чх«Хо.
»= 1 Лемма 5 доказана. П 337 5 15. МЕТОД ШТРАФНЫХ ФУНКЦИЙ 336 г . 5, методы минимизАЦии ФУнкЦий многих переменных Заметим, что в общем случае из выполнения условий леммы 5 не следует существование седловой точки функции Лагранжа задачи (1), (8) и, наоборот, существование седловой то пги не гарантирует выполнение условий леммы 5, Это означает, что выделенные в леммах 1, 5 два класса задач (1), (8), имеющих сильно согласованную постановку, взаимно дополняют друг друга. Отметим также, что зтими двумя классами не исчерпываются задачи (1), (8) с сильно согласованной постановкой, Поясним зта на примере. П р и м е р 8. Рассмотрим задачу /(х)=-х"-ч)п1, хеХ=(х>0: д(х)=хд <0), (43) где о>О,Д>0, Хо — — (хсЕ: х>0)=Е+,Ясно, что Х=Х,=(0), /„=О.
Далее, имеем /„= 0 =- -х -1- (хд)~~д =/(х) -1- (д (х))~~д Чх Е ХО, так что неравенство (21) выполняется при в = гп = 1, с; = 1, и = о/)у. Следовательно, задача (43) имеет сильно согласованную постановку и к ней применимы теоремы 5, 6. Отметим, что здесь д(х, Х)=)х-0(=(х1=(дт(х))'/д, хе Х, т. е, условие (Зб) выполняется с М=1, т=1/д, Далее, при 0<о <1 функция /(х)=-х" удовлетворяет условию Гельдера; )х -д )<1х-~!", х, де Хо, так что в этом случае применима лемма 5. При а > 1 условие Гельдера на Хо — — Бч не выполняется и лемма 5 неприменима.
Далее, функция Лагранжа 5 (х Л) = -х + Лх", х > О, Л ) О, задачи (43) при и = д имеет седловую точку (х„=О, Л* = 1). Кстати, седловая точка здесь не единственная: любая точка (О, Л*), Л" > 1, также является седловой, Заметим также, что функция /(х)=-хо, х) О, выпукла лишь при 0< а <1, а д(х) =х, х) О, выпукла лишь д при Д > 1. Если о ф Д, то функция Лагранжа не имеет седловой точки. Таким образом, при а > 1, )У > О, о ~ )У задача (43) не охватывается леммами 1, 5, 7. Рассмотренный выше метод штрафных функций дает простую и универсальную схему решения задач минимизации на множествах, не совпадающих со всем пространством, и часто применяется на практике. Поскольку имеется достаточно богатый выбор штрафных функции, то при составлении функции Фь(х) можно постараться обеспечить нужную гладкость этой функции, выпуклость, подумать об удобствах вычисления значений функции и требуемых ее производных и т.
п. Кроме того, имеется определенная свобода в выборе множества Хо для задачи (2): в задании множества (8) всегда можно отнести ко множеству Х, наиболее простые ограничения (например, Хо может быть шаром или параллелепипедом в Е", совпадать с полупространством или со всем пространством Я" и т. д.), а остальные ограничения оформить в виде дг(х) < 0 нли ду(х) = 0 и учесть их с помощью штрафной функции. Поэтому можно надеяться на то, что вспомогательные задачи (2), (3) удастся сформировать более простыми, более удобными для применения известных и сложных методов минимизации, чем исходная задача (1). Следует заметить, что хотя сама схема метода штрафных функций довольно проста, но при практическом использовании этого метода для решения конкретных задач минимизации могут встретиться серьезные трудности.
Дело в том, что для получения хорошего приближения решения задачи (1) номер й в (2), (3) (или штрафнои коэффициент Аь в (9)) приходится брать достаточно большим. А с увеличением номера й свойства функции рь(х) =/(х)+Р (х), х е Хо, оказывается, во многих случаях начинают ухудшаться; эта фуйкция может стать более овражной, некоторые координаты градиента Ф,'(х) могут быть слишком большими, могут появиться дополнительные локальные минимумы и т. п. Это все может привести к тому, что при больших й методы минимизации, используемые для решения задачи (2), будут плохо сходиться и определение точки хго удовлетворяющей условиям (6), с возрастанием й может потребовать все большего и большего объема вычислительной работы. Поэтому при практическом применении метода штрафных функций вспомогательные задачи (2) обычно решают лишь для таких номеров м (возможно больших), для которых удается обеспечить достаточно быстрое убывание функции /(х) и достаточную близость получаемых точек ко множеству Х при небольшом объеме вычислительной работы, Если полученное на этом пути приближение к решению задачи (1) недостаточно хорошее, то привлекагот более тонкие и, вообще говоря, более трудоемкие методы минимизации, стараясь при этом получше использовать ту информацию, которая получена с помощью метода штрафных функций.
Заметим, что если выполнены условия теоремы 6, то штрафная функция (9) множества (8) при р = м будет точной и нет необходимости неограниченно увеличивать штрафной коэффициент А„и в этом случае упомянутый недостаток метода штрафных функций, вообще говоря, не будет проявляться. Правда, штрафная функция (9) прн р =- и не всегда будет обладать достаточной гладкостью, но появившиеся в последнее время методы минимизации, не требующие гладкости минимизируемой функции (см., например, [264; 265; 361; 386; 396; 426; 572; 586; 718; 769; 777)), позволяют надеяться, что численное решение задачи (2) в рассматриваемом случае не будет слишком трудным.
Отметим, что при описании н исследовании метода штрафных функций выше мы предполагали, что функция /(х) и множество (8) известны точно. Если же указанные исходные данные известны лишь приближенно, то метод штрафных функций полезно регулярнзовать — об этом подробнее см. гл. 9, Различные прикладные и теоретические аспекты метода штрафных функций исследованы в 118-20; 84; 85; 151; 218; 222; 250; 266; 286; 294; 295; 302; 319; 343; 374; 377; 3?9; 471; 562; 603; 613; 670; 720; 721; 738; 759; 774; 785; 786). Упражнения 1. Применить метод штрафных функций к задачам а) /(и) = х ч- дз-г 1п1; и ах =(и=(х, у) ее: д(и) =-х — д+ 1 ~(0) или и ах =(м= =(а,у)еЕ; д(и)= — х — у+1=О); б) /(и)=хд-ч)п(; иеХ=(и=(х,д)сЕ~: хзэдз К<25) или оеХ=(и=(х,д)еЕ~: хе + д = 25); в) Пи) = ха+ да+ зз — ч)п1; и е Х = (и= (х, д, з) е Ез: х+ у+ а+ 1 <О).
2. Применить метод штрафных функций к задачам из примеров $2.3. 3. Пусть /(х) = е зь, а множество Х = (х е и'. 0 < х < 1) задано либо ограничениями д1(х) = -х < О, дз(х) = х — 1 < О, либо д(х) = (х(ч- )х — 1) — 1= 0, либо д(х) = е "(1х)+ (х— — 1( — 1) =О, Выяснить, в каких глучаях задача /(х) ч 1п(, хе Х, имеет согласованную или сильно согласованную постановку на П '. 4. Пусть (Рь(х)) — штрафная функция некоторого множества Х. Пусть функция зз(1) определена при 1 > О, го(0) = О, причем го(а) ч О при з -ч О, тг(1) ч со при 1 -1 со. Показать, что тогда (х(рь(х))) является штрафной функциеи множества Х, 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
