Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 28
Текст из файла (страница 28)
Рассмотрим отображение Ч'(1, Л) =(1, х(1, Л)) в некоторой точке (1, О), 1~ [(о, 11]. Имеем У 1 0 бе1 Ч" (г, 0) = бе1 ~ — — [ = бе1 Н(7, 1„) ~ О. .Значит, по теореме об обратной функции найдется такое 6= =6(й) >О, что если только [1 — т[<6, [$ — х(1) ) <6, то сущест.вует единственное Л=Л(т, 6),'такое, что Ч'(, Л(т, $))=(т, $) х(т, Л(т, $))=$. В силу компактности графика Г;=((1, х(1)) [1ен[1„11[) ,можно найти одно 6ь, такое, что для любой точки (т, $), [$— — х(т) [<бь существует (и как нетрудно понять — единствен.ное) Л=Л(т, 6), при котором х(т, Л(т, 6)) =6. При этом гладкость функции Л такая же, как гладкость х, т.
е. Сз. Построение центрального поля, окружающего экстремаль, закончено. 10.3.2. $-функция и ее дифференциал. Пусть х(., Л) — центральное поле с центром 1., окружающее экстремаль Х( ). Функция 8(т, Б) =~ Ь(Г, х(1, Л(т, Е)), х(1, Л(т, $))) й1 ,называется Я-функцией центрального поля х(, Л). Имеем по определению поля и функции наклона поля х(т, Л(т, й))=4, (1) х(т, Л(т, а)) =и(т, $). 144 Предположим, что интегрант Š— непрерывно дифференци- руем в некоторой окрестности графика ЦЕ х(1), х(1)) ~1=.
~[(ь, 1~]), тогда имеет место следующая формула для диффе- ренциала функции о: йЗ(т, $) =(1. (т, $, и(т, $)) — (Е; (т, $, и(т, $)), и(т, $)))йт+ +(Е;(т, $, и(т, $)), с$). Действительно, дифференцируя интеграл с переменным верх- ним пределом, используя непрерывность х„вытекающую из того, что хенСг, получим — =Е(т, $, и(т, ф)) + ~((Е„(1, х(1, Л(т, $)), х(1, Л(т, $))), с, хь(Е Л(т, ь)) Л,(т, ь))+(Е„(Е х,(Е Л(т, ь)), х(1, Л(т, ь))), хь(1, Л(т, $))Л,(т, $)))й(.
Интегрируя второе слагаемое в интеграле по частям с учетом (2) и используя то, что х(, Л) есть зкстремаль, имеем далее — = 1.(т, $, и (т, Ц)+ (Ей (1, х(1, Л (т, $)), х (1, Л (т, $))), х„(Е Л(т, ь)) Л,(т, ь)) ~ (3) Поскольку х,(1., Л(т, 3)) =0 (так как 1. — центр поля), а 'про- дифференцировав по т обе части уравнения (1), имеем Формула для д5/д$ выводится аналогично с помощью интегрирования по частям и использования равенства хь(т, Л(т, К)) Л1(т, $)=1 (получается дифференцированием обеих частей равенства (1) по й). 10.3.3. Формулировка теоремы и вывод достаточных условий в простейшей задаче к.в.и. Основная формула Вейерштрасса. Теорем а.
Пусть х(.) е=Ст([1ы 1~], К") — допустимая экстремаль в простейшей задаче (з) и. 9.2.1. Интегрант енСь(УХй"), где Ус:й"+' — некоторая окрестность расширенного графика ((Е х(1)) ~1~[1ы Я, на х( ) выполнены усиленные ус- '145 х(т, Л(т, 4))+хь(т, Л(т, $))Л,(т, $)=0, то, произведя подстановку в (3), получим нужное соотношение — =Е(т, $, и(т, $)) — (Е„(т., х(т, Л(т, $)), и(т, Л(т, $))), и(т, $)).
,д8 ловил Лежандра и Якоби, интегрант Т. квазирегулярен на,У Тогда х( ) доставляет сильный минимум в задаче (з). с) Условия теоремы позволяют (см. п. 10.3.1) окружить х( ) центральным полем экстремалей х(, А), покрывающим некоторую односвязную окрестность У~(с графика ((1, х(1) ) ~ 1е= е[сь, сс)). Пусть х( )апс(С'((1ь, 1Д, й") — произвольная допустимая функция, график которой расположен в этой окрестности„ ' Тогда 5(1с, х,) — 5(1„хь)= ) Ю(1, х(С)) = ~й8(1, х(1)) = с, с, =~(Т.(1) — (1.„(Н, х(1)))й1+~(Е„(1), сКх(1))=- с, св с, Х(1)й1=ас (х( )). с с, У (х(.)) — У(х( )) =~Е(1, х(1), х(С)) й1 — ~йЗ(1, х(1))= с, с1 = ~ (1. (с, х (1), х (1)) — 1.
(1, х (г)„и (1, х (с)))— се — (Ц (1, х(1), и(1, х(1))), х(1) — и(1, х(1))))йг= с1 = ') з (1, х(1), и(1, х(1)), х(1))йс. и Эту формулу называют основной формулой Вейерштрасса. Из квазирегулярности интегранта следует (см. п. 9.2.1), что если (с, х) я(с, то е (1, х, и, х) >О У(и, х) гни" Х К". Таким образом,. Ю(1, х(1), и(1, х(1)), х(С))й1)0 и, значит, д(х( ))~) с, )5'(х(.)), т.
е. х( ) доставляет сильный минимум. 5 11. ДОПОЛНЕНИЯ 11.1. Задачи линейного и выпуклого программирования Этой теме (выпуклым задачам) было уделено достаточно много места в первой части. Но там мы подходили к проблемам с элементарных позиций. Здесь возвращаемся к тому же кругу вопросов с тем, чтобы посмотреть на него как бы сверху„ вооружившись арсеналом функционального и выпуклого анализа.
146 11.1А. Теория двойственности в линейном программировании. Рассмотрим задачу линейного программирования ц 31.1 (с, х)-нп1; Ах(Ь, (з) где х, с~11", Ь~)т", А — матрица размеров тХп. Включим эту задачу в семейство задач с параметром а~1с" (с, х)-~4п(; Ах(а. (з,) Численное значение задачи (з ) 5(а)=1п(((с, х)~Ах(а) назы- вается 5-функцией задачи (з), 5(Ь) — значение исходной за- дачи (з). Нетрудно доказать, что 5 — выпуклая функция.
~Найдем ;(см. в п. 1.5.2 преобразование Лежандра — Юнга — Фенхеля) соп- ряженную к функции 5 функцию 5 (а,'). Имеем гм 5'(а') =зцр((а', а) — 5(а)) =зцр((а', а) — 1п1((с, х) ~Ах(а)) = а а 1'зцр((а', Ах) — (с, х)), а'(О, ='зцр((а', а) — (с, х) ~Ах(а)=~ аа + оо, в остальных случаях ° ° зцР((А'а' — с, х)), а" (О, 10, А*а'=с, а'(О, м + оо, иначе +оо, иначе Найдем вторую сопряженную к функции 5 функцию 5*'(а): 5-(а)=зцр((а, а') — 5'(а'))=зцр((а, а') ~А'а'=с, а' 0). а При этом 5-(Ь)=зцр((а', Ь) !А'а'=с, а'(0). Задача а' (Ь, у)- зцр; А*у с, у~О, (з*) называется двойственной к (з).
Теорем а (двойственности). Для пары двойственных задач линейного программирования (з) и (з*) имеет место следующая альтернатива: или значение какой-либо из задач конечно (и тогда конечно значение второй и оба значения совпадают), или значение одной из задач бесконечно, а другая несовместна. 0 Пусть 5(а)) — оо таен1("', тогда по теореме Фенхеля— Моро (п. 1.5.3) (здесь мы пользуемся замкнутостью функции 5, поскольку надграфик функции 5 является по лемме о замкнутости конечнопорожденного конуса п. 3.2.1 замкнутым множеством) 5'*=5, и, значит, если Ьенбопт5, то 5(Ь)=5" (Ь)=зцр((Ь, у) )А"у=с, у(0), а это не что иное, как значение задачи (зь).
Если же Ь г. чгбо~п 5, то это значит, что задача (з) несовместна. 147 Пусть существует ае, такое, что 5(ао) = — ьь. В этом случае 5*е= — — ьь, в частности, вм 5" (Ь)=зпр((Ь, у) ~А'у=с,.у~О)= — ао, т. е. задача (з*) несовместна. 11.1.2. Теорема Куна — Таккера. Мы уже затрагивали эту тему в первой части (п. 2.3.2), где дали элементарное доказательство этой теоремы. Здесь выведем ее из основных теорем выпуклого анализа. Т е о р е м а. Пусть Х вЂ” локально-выпуклое пространство.
~г . 'Х- 11 — выпуклые собственные функции,.непрерывные в точке 2, А — выпуклое множество, х доставляет абсолютный минимум в задаче (з) ~ь(х)- 1п1; ~~(х)(0, хенА. Тогда для (з) выполнен принцип Лагранжа. Расшифровку принципа Лагранжа здесь не приводим— она выяснится в итоге доказательства. Обратим внимание на то, что здесь наложены требования (локальная выпуклость Х и непрерывность 1е), которых не было раньше. <) О.
Доказательство базируется на: 1) теореме Ферма дли выпуклых функций (п. 2.3.1); 2) формуле Моро — Рокафеллара и 3) формуле Дубовицкого — Милютина (п. 1.5.4 и 8.2). 1. Как это не раз делалось без ограничения общности считаем, что (е(х)=0, 1=О, 1, ..., т. Положим 1(х)=шах(е(х). Ясно, что если хааЬзш(пз, то хеваЬзш(п()+бА). Тогда, используя теорему Ферма для выпуклых функций и формулы Моро — Рокафеллара и Дубовицкого — Милютина, получаем о.э еа 0 ен д Д+бА)(х)=д1(х)+дбА(х)= =со(д)е(х) ()... Ц д( (х))+дбА(х). Остается расшифровать (1).
Там записано следующее: существуют х,'авдее(х), ае)0, Т ае=1 и $'ендбА(х), такие, что ~ а,х,'+ е=.ь е 0 +$'=О. По определению субдифференциала, учитывая, что ~,(х)=- =О, получаем ~,(х)) (х;, х — х), 0) Я', х — х), х~А. Умножав на ае и суммируя, приходим к принципу минимума: ~', аД(х)) 0 Ух~ А, а неотрицательность а1 н условие дополняющей нежесткос уже выполнены. ь> 148 !1.2.
Ляпуновские задачи К этому классу задач редуцируются многие проблемы оптимизации, в частности линейные задачи оптимального управления. Одна из их примечательных особенностей — наличие скрытой выпуклости, т. е. выпуклой структуры, которая на первый взгляд не видна в них. Однако именно выпуклость предопределяет то обстоятельство, что в ляпуновских задачах необходимые условия смыкаются с достаточными и они реализуются в виде принципа минимума. Т е о р е м а (принцип Лагранжа для ляпуновских задач). Пусть (Т, М, т) метрическое пространство с борелевской мерой т (Я вЂ” совокупность борелевских множеств), У вЂ” топологическое пространство, 1;: ТХ У вЂ” «К — непрерывньсе функции, =О, 1, ..., т, Х вЂ” линейное пространство, й; — выпуклые конечные функции на Х при 1=1,,, тп' и аффинные при (=тп'+ +1, ..., тп, А — выпуклое подмножество Х, пара (й( ), х) доставляет абсолютный минимум в следующей задаче': Га(и(.))+й,(х) — «1п1; Рс(и( ))+ус(х)(0, 1=1, ..., и', Р; (и (.)) + й~ (х) = О, Е = пт'+ 1, ..., т, хая А, Рс(и( ))= 1с(1, и(1))йт.
Тогда для задачи (з) имеет место принцип Лагранжа, т. е. существуют множители Лагранжа Л (Ло, ..., Л )~Й +' и ЛФО, такие, что выполнены: а) принцип минимума по и и по х ппп ~,ЛА(1, и)= ~~ Щ(1, и(г)) п. в., вес,=е ',=.а и~ 7« пт(п ЯЛ;д,(х)= ~~ Л~д,(х); «ел; о а=о б) условие неотрицательности Л;)~0, 1=0, ..., и; в) условие дополняющей нежесткости Л~(Р'(й(.))+й;(х)) =О, 1=1, ..., пс'. Нетрудно понять, что если Ло>0, то условия а), б) достаточны для того, чтобы (й( ), х) было'реитением задачи (з). <~ О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
