Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 70
Текст из файла (страница 70)
Задача: Х(х) = (х!з — ! !п1, х Е Х = (х е Е": д(х) = )х!з— — 1<0). Здесь Х,=Е", Х,=О, х,=О, А =~Л ЕЕ: Л >0). Функция Ла- гранжа Х (х Л ) = !х/~+ Л (/х!~ — 1) = (1 + Л )!х/ — Л, т Е Хл, Л Е А . Ясно, что !Ь(Л) = !п1 Х (х, Л) = — Л при всех Л Е Лх Таким образом, двойственная ллв" задача имеет вид ~(Л) = — Л вЂ” ! зпр, Л е Л = Л .
Эта задача линейного про- граммирования. Двойственная к ней задача также будет задачей линейного программирования и не может совпасть с исходной, Остается заметить, рас- сматриваемая задача выпукла, и функция Лагранжа в ней имеет седловую точку (х„=О, Л*=О). Заметим, что теорема 3.5.2 об одновременной разрешимости исходной и двойственной задач также специфична для задач линейного программиро- вания и не может быть обобщена иа нелинейные задачи даже при условии их выпуклости — см. примеры 6 — 8.
7. Кратко остановимся еще на одном интересном классе задач, называемых задачами геометрического программирования, в которых переход к двойственной задаче весьма плодотворен. Речь идет о задачах минимизации следующего вида: и,=!и х!, 4=1,..., т; и ч,= — Ь!+~ аии,, Ь!= — !и с!, 4=1,..., т!, !' = ! (41) и переписать ее в эквивалентном виде: Х(и) = 2, е "' — ! !П1; (42) иЕГХ=(иЕЕ"!": Х анит — и+! — Ь!=О, 4=1,...,и). !'= ! Отметим, что функция Х(и) выпукла на Е"! ", 1Х вЂ” многогранное множество, и поэтому к задаче (42) применима теорема 3. Составим функцию Лагранжа (3) для этой задачи: л л Х(и,Л)=Х, е'" + Х Л,.(Х,'а,из — и„~! — Ь!) = !=! !=! !'=! = 2,' (е""' — Л и„! — Л,Ь )+~ (Х,' аВЛ)и,, и Е Е'+ =Хм Л Е Е"=А .
С помощью классического метода ($1.2) нетрудно показать, что нижняя грань функции р(г) = е' — Л!г — Л!Ь! переменной г на числовой оси равна ~р„ = Л! — Л!!п Л,. — Л,.Ь!, причем прй Л! > 0 она достигается в точке г, = = — !и Л,.; функция Л,.1й Л,. при Л,. = 0 здесь считается доопределенной по непрерывности нулем. Отсюда, ойираясь на линейность функции Х (и, Л) по переменным и„ ...,и„, получаем !Ь(Л)= !п1 Х(и, Л)= Х,'(Л! — Л! 1п Л! — Л,.Ь,.), Л ЕЕ", Х авЛ! =0,,7'=1,..., т, ! =! =! — со при других Л. Поэтому двойственная задача (30) здесь будет иметь вид п !Ь(Л) = ~ ,'(Л! — Л!!и Л! — Л!Ь!) — ! зпр; Л Е Л, А = (Л = (Л „..., Л„) Е Е„": Х,' анЛ! = О, у' = 1,..., т'). '= ! Если здесь верхняя грань достигается в точке Л" фО, то задачу (43) можно записать в более простой форме. А именно, учитывая, что любую точку Л = Г«9.
ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 233 232 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Упражнении , х, «) с!'... с„"" 4з(и)= '„,'" "„- зпр; иЕЛз« 1«н" ич". (44) = (Л„..., Л„) фО можно представить в виде Л = сги, где сг = 2,' Лг, и = =(и„..., и„), и! =Лг/гх, и, +... + и„=1, задачу (43) перепишем сначала в терминах переменных (гг,и): т]«,(сй, и) = т]«(сйи) = 2 гх(и! — и! [п сги! — и,й!) = г=! п = а [1 — 1п се+ ~ ,'(иг!и с! — и! 1п и!)~ — зцр,' г=! и (сг, и) Е А«=((ст, и): сг >О, и ЕЕ,, 2 , 'и«=1, 2 аи!««=0, 7' =1,, т~ «=! «' ! Далее, пользуясь классическим методом ($1.2), убеждаемся, что точка се*= П ['«и ~ > 0 (здесь принято Ос=1) доставляет функции ф«(сг, и) н' «.= ! максимальное значение по сг > 0 прн фиксированном и е Я~, причем м-,.)= й( —;,) Тогда двойственная задача (43) перепишется в следующем виде: ч Аз = ] и = (и„..., и ) Е Я+ .
'2,' и! = 1, 2" а, и! = О, 7' = 1,..., т ~. Если ь" = г=! г=! = (и,*,...,и„") е 1п! Š— решение задачи (44), то, полагая Л* = а'и*, где сг* = П ~ †'„' ) , ы, „„.„ = Л;, з = 1,...,п, из системы линейных алгебраиче«=! ских уравнений (41) можно получить ы«„,...,ы„, откуда имеем решение х. = (х„ = е",...,ш, = е" ) исходной задачи (40), Задача (44) часто бывает проще задачи (40).[з[ереход к двойственной задаче особенно эффективным оказывается тогда, когда множество Л, в задаче (44) состоит из единственной точки и*, которая и будет решением этой задачи.
Аналогично может быть' исследована и более общая задача геометрического программирования до(х) — «!п[; хе Х =(х е]п! Ь": д«(х) (1,..., д (ш) (1)« где д,(х),..., д (т) — позиномы. Подробнее о геометрическом программировайии, его приложениях см., например, в [204; 260; 54Ц. Читателей, желающих подробнее ознакомиться с красивой и богатой результатами теорией двойственности, с различными ее приложениями, отсылаем к [6; 7; 14; 40; 44; 49; 52; 83; 84; 209; 225; 233; 234; 278; 297; 314; 358; 366; 373; 434; 465; 584; 604; 605; 613; 617; 670; 683; 687). Заметим также, что в последнее время растет интерес к задачам, в которых нарушены соотношения двойственности (34), такие задачи возникают при исследовании объектов, описываемых противоречивыми системами ограничений, и имеют интересные приложения [297; 298; 644). 1.
Сформулировать аналоги теорем Куна — Таккера для задачи максимизации: д(х) — «зор, хе Х, где множество Х определено посредством (2). Указание: рассмотреть задачу: 7(х) = — д(х) — «!п(, х е Х, и воспользоваться теоремами 2 — 4. 2. С помощью теорем Куна — Таккера исследовать задачу: 7(х) = ~; [х! — о![-««п1, х е Х, «=! где Х=(хеЕ": [х[<1) или Х=(хсЕ": х«+...+х =0), или Х=Е"; о«,...,о„— заданные числа. 3. Применить теорему Куна — Таккера к задаче квадратичного программирования: 7"(х) = = (х«)з +... + п(х") «ш1, х е Х, где Х = (х е Е": х +...
+ л" = 1), или Х = (х е Е~.' х'+... + х" < 1), или х =(хе е": — 1 < х«+... ч- х" < 1), или х является пересечением предыдущих мнохгеств с Е". 4. Решить задачи геометрического программирования: а) д(х) = с«х" + сзх 'ч — «!п1 при х >О, где с! >О, а,. >0 — заданные числа; б) д(х у)=х у+2хзу+Зх «у з — «!п1 при х>0, у>0; в) д(гс у з) =4х 'у «х ! + му+ 4хз+ 2уз — «!п( при х > О, у >О, з) 0; г) д(ху)=р-«!п1 при х>0, у>0, х у ~+х «у«!в<1; д)д(хрз)=х+у х ~«~-«!п1прих>0 р>О,з>О,х «у+х «з<!. 5.
Найти решение задачи: 7(н)=-х-у — «!п1, м=(х, у)еХ =(мерз! д(м)=ха+уз — 2(0) и двойственной к ней задачи. Убедиться, что здесь множество А из (30) выпукло и открыто. 6. Показать, что двойственная задача к задаче из примера 5 является задачей линейного программирования, и решить ее. 7.
Доказать, что выпуклая квадратичная функции 7"(х) = †(Сх,х) + (с,х) либо достигает 1 своей нижней грани на Е", либо не ограничена снизу [34( 3. Пусть !го — выпуклое мне«кество из Е", функции д«(м),..., д (и) выпуклы на !го, дг(м) = (ой, и) — Ьг, « = «и+ 1,..., з, Докааать, что если система неравенств д,.(п) < О, ! = = 1,..., и«, д,.(м) = О, ! = го 4.1,..., з, не имеет РешениЯ на !го, то сУществУют числа л! >О, ..., Л > О, Лх «,..., Л, такие, что Л«д«(м) +... + Л,д(о) ) 0 при всех м Е !то. Указание: построить множества, аналогичные множествам А и В из доказательства теоремы 2, и применить к ним теорему отделимости 5.2. 9. Пользуясь теоремой Фаркаша, доказать, что для несовместности системы линейных неравенств (ег, х) < Рч « = О,..., и«, необходимо и достаточно, чтобы существовали такие числа Ло>0, Л!)О,..., Л )О, что ЛоеочЛ«е«+...+Л,„е =О, Лоио+Л«!««+,..+Л уж<0 [752].
10. Доказать, что два непустых многогранных множества А = (х Е Е: (ег, х) ( иг, ! = =О,..., ь) и В = (х ее"; (ег, х) < иг, ! = й+ 1,..., гп), не имеющие общих точек, сильно отделимы. й й У к а з а н и е: рассмотреть гиперплоскость (с, х) = 1, где с = Л,' Л! ег, 1 = 2; Л! и!, числа Ло,..., Лх взяты из упра«кнения 9.
«=о « О 11. Доказать, что если система линейных неравенств (ео, х) < О, (е«, х) < О,., ч (е, х) < 0 несовместна, то сУществУют такие числа Л) ) О,..., Лх )О, что ео — — -Л«е! —... — Л е У к а з а н и е: воспользоваться теоремои Фаркаша. 12. Пусть система (ео, х) < ро, (ег, х) ( иг, ! = 1,..., и«, несовместна, а подсистема (ей, х) < (и! « =1,..., и«, совместна.
Доказать, что тогда существуют числа Л, >О,..., Л )~0 такие, что ео —— -л ! е! —... — л е, до+ л! и! 4... ч- л !«,„< О [54; 670]. Указа н и е; в пРостРанстве пеРеменных (х, 1)ее" +' РассмотРеть системУ (ео, х)-зло< < О, (ей, х)-ги! < О, «=1,..., и«, (О х)-1 (0 и воспользоваться утверждением из упражне. ния 11. 13. Рассмотрите задачу(1), (2) при Хо — — (хеЕ': х>0), 7(х)=х, Х=(х>0: д(х)=х~~<0) н убедитесь, что функция Лагранжа Ь (х, Л) = в+Лхз, х > О, Л > О, этой задачи имеет бесконечно много седловых точек (ср. с примером 1). Сформулируйте двойственную задачу. $1.
ГРАДИЕНТНЫЙ МЕТОД 235 .«( а' «! *" ' 9 1. Градиентный метод 1. Будем рассматривать задачу ГЛАВА б Методы минимизации функций многих переменных Выше в гл. 3 был рассмотрен симплекс-метод для решения задач линейного программирования. Перейдем к изложению других методов минимизации функций конечного числа переменных, не предполагая линейности рассматриваемых задач. К настоящему времени разработана и исследовано большое число методов минимизации функций многих переменных. Мы ниже остановимся на некоторых наиболее известных и ча. сто используемых на практике методах минимизации, будет дано краткое описание каждого из рассматриваемых методов, исследованы вопросы сходимости, обсуждены некоторые вычислительные аспекты атих методов.
При этом мы ограничимся рассмотрением лишь одного-двух основных вариантов излагаемых методов, чтобы ознакомить читателя с основами этих методов, полагая, что знание основ методов облегчит читателю изучение литературы, позволит ему без особого трудо понять суть того или иного метода и выбрать подходящий вариант метода или самому разработать более удобные его модификации, лучше приспособленные для решения интересующего читателя класса задач. В конце главы будут высказаны некоторые общие замечания по методам минимизации.
Из обширной литературьь посвященной методам минимизации функций конечного числа переменных и их приложениям, мы можем здесь упомянуть лишь весьма незначительную ее часть 11; !3; !6; 18-20; 24-30; 32; ЗЗ; 52; 53; 56; 61; 62; 66; 70; 71; 73; 74; 76-78; 83-85; 89-92; 94; 102; !09; 116; 117; !28; 131; !34; 135; 140; 143; 148; 154; !61; 179; 183; 184; 194; 203-205; 214; 2!6; 218; 222; 226; 227; 231; 232; 234; 243; 250-252; 255-257; 259-266; 272; 273; 281; 286; 292; 294-299; 301; 302; 304-309; 314; 316-320; 326; 330; 341-345; 347; 356; 358; 361; 368-370; 372-375; 377; 386-3881 390; 396; 398; 40!', 4!О; 422; 423; 426; 437; 442; 447; 448; 465; 466; 470; 471; 481; 491; 493-495; 499; 506; 511; 5!6-518; 520; 521; 523; 525; 527; 539; 541; 542; 548-550; 561-5661 572; 580-582; 586; 590; 591; 601; 603; 606; 6081 6!О; 612-614; 620; 623; 624; 635; 639; 652; 657; 661; 662; 670; 671; 675; 676; 678; 681; 684; 686-688, 695; 697; 704; 709-711; 713; 718-721; 725; 732; 737; 738; 742; 743-747; 750-752; 7591 760; 765; 769; 774-777; 786; 792; 793; 795; 799; 803; 807; 8!1; 813; 818!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
