Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 24
Текст из файла (страница 24)
9.1. Необходимые условия! и П порядка в гладких задачах математического программирования 9.1.1. Постановка задачи и необходимые условия ! порядка. Пусть Х и У вЂ” нормированные пространства, 1;:Х-«К, =О, 1, ..., т — функционалы, Р:Х вЂ” «У — отображение из Х в У. Гладкой задачей математического программирования с ограничениями типа равенств и неравенств называется задача 1,(х) -« 1п1; Т;(х) ( О, ! = 1, ...,т, Р (х) = О. (з) Функция ~(х, ), у') =~', )~А(х)+(у', Р(х)) называется функцией Лагрангка задачи (з), пара ()„у*) ен енй е'Х У* — набором множителей Лагранжа.
Те о р ем а (необходимое условие ! порядка). Пусть в (з) Х, У вЂ” банаховы пространства (условие банаховости), е=БР(х), 1=О, 1, ..., т, РенЗР(х) (условие гладкости), 1тР'(2) — замкнутое надпространство в У (ослабленное условие регулярности). Тогда если ха!оспин з, то существует ненулевой набор множителей Лагранжа (г„уь) такой, что для функции Лагранжа выполненй условия; а) стационарности.- ,Ы,(х, Л, у )=О У Лчу; ( )+(Р'( ))' у'=О; (ьа б) дополняющей нежесткости: л;);(х)=0, 1=1, ..., т; в) неотрицательности; )ч~О, 1=0, 1, ..., т.
Данная теорема была доказана в п. 2.4. Здесь мы приве" дем еще одно доказательство основного случая теоремы 122 л1шР'(х) =У) с использованием формул Моро — Рокафеллара и Дубовицкого — Милютина (п. 1.5.4). Как и при доказательстве в п. 2.4, считаем, что [о(2) =О, 1 О, 1, ..., т, а условия дополняющей нежесткости уже выполнены. <) Обозначим Л Е'(х), х;* )~'(х), 1=0, 1, ..., т.
Рассмотрим вспомогательную задачу: шах (х,', х)+6КегЛ(х)-~-1п1, ю-ол,...,« (з') Теперь остается воспользоваться формулой Дубовицкого — Милютина, очевидным соотношением дб КегЛ (КегЛ)х и леммой об аннуляторе ядра регулярного оператора (п. 7.2). Полу- чаем где 6 — индикаторная функция множества КегЛ. Л е м м а. ОенаЬзш(п з'. <3 <1 Предположим, что ОФаЬзш1пз', Тогда 5 м<0 и, значит, существует злемент йыКегЛ, для которого (х;*, Й)< <О, 1=0, 1, ..., т.
По теореме о касательном пространстве (п. 1.4.4) найдутся число е)0 и отображение г:[ — е, е)-~-Х, .такие, что Р(х+И+г(1))=0 )г(ы[ — е, е) и [[г(1)[)=о(1) при 1-~ — О. Но тогда, используя определение днфференцируемости по Фреше и то обстоятельство, что ~~(х) =Оп получаем 1(х+Я+гЯ)=~о(х)+(хь Я+г(1))+о(~~1Ь+г(1)![)= =1(х',,а)+о(1)<0 при малых 1)0, 1=0, 1,..., т. Таким образом, при малых 1 точка х+Я+г(1) будет допустима и 1о(х+Й+г(1))(0, т.
е. х~р ~ 1осппп з. Противоречие. г г; Положим <р(х)= шах (х',, х)+6КегЛ(х). Поскольку ~р — выл=-0, ь...,« пуклая функция и по лемме О~аЬзш(п~р, то по аналогу тео- ремы Ферма для выпуклых функций (п. 2.3.1) Орду(0). В си- лу формулы Моро — Рокафеллара О~д~р=д( шах (х,', )+6КегЛ( ))= о=оп,..., =д шах (х,', )+дбКегЛ(.). ~=оп,...,« 0~ со(х', ..., х')+1ш Л' ««Б Л,) О, ~~' Л, = 1, ~-о « ив у' еи У": ~ Л х,'.+Л'у'=0««Я Л;Г; (х)+(г' (х))'у" =О. [> о=о о=о 9.1.2. Необходимые условия П порядка. Обозначим Л совокупность всех наборов (Л, у*), для которых выполнены ус- 123 ловия а)-в) теоремы и. 9.1.1 и Я)о!=1. Теорема о необс о ходимых условиях ! порядка утверждает, что ЛФЯ.
Теорем а (необходимое условие Н порядка). Пусть в задаче (з) и. 9.1.1 Х и У вЂ” банаховы пространства (условие банаховости), функционалы ~ь о=О, 1, ..., т, и отображение Р' дважды дифференцируемы в некоторой окрестности точки й (условие гладкости), 1п!Р'(2)=У (условие регулярности). Тогда если хы!осщ!п з, то Положим 8(а, у)= !п! п!ах (а,+(х,', х)) лх+у о ! !....л (2) Тогда: а) величина Я(а, у) допускает двойственное представление В (а. у) = зцр ( ~ )!!ас+ (у' у)) =:зЛ (а, у), (3) сьл >ел где з о Л =(()!, у')ен',й' х У' ! )!ч)0, ~~' Ц=1, !(!')!!х,'. +Л'у'=0), ! ! . ! ! зЛ(а, у) — опорная функция множества Л в точке (а, у).
б) !п! в (2) и зпр в (3) достигаются. ()0 А) Существование минимума полиэдральной функции, ограниченной снизу на афф иннам многоо бр аз ни. Нетрудно видеть, что следующие три задачи эквивалентны: !р(х): = п!ах (ао+(х,'., х))+6М„(х)-!-!п!. !(!~ы М„: =(х!Лх+у=О); щах (а!+В!)-! !п1; $~ М(у); !<~~(з (3,) 124 и!ах Я (х,)!,у')[Ь,Ь))0 (ь,у )ел для любого )о, принадлежащего конусу допустимых вариаций К вЂ” "(ЬХ! (1; (х), 1!) (О, Р'(х)"!й1=0). <~ Доказательство базируется на лемме о миинмаксе и теореме Люстерника (и. 1.4.4).
Лемма 1 (о минимаксе). Пусть Х, У вЂ” банаховы пространапва, Ля.У(Х, У), ЛХ=У, х,' я Х', о=1,...,з, уев У, а я К', щах (х',, х) ь: О тгх ~ Кег Л. Я М (У): = (в = Яс,..., $,) ен й* ! Бх еп Х: $с = (х,', х), Лх+ У = О), с-~.)п1; ас+$счмс, с=1;...,з, $енМ(у). (за) В задачах (з,) — (з,) М, н М(у) — аффинные !многообразия, соответственно в Х и в 11*. Возьмем элемент х, для которого стх+ +у=О. Тогда М„=х+КегЛ н„следовательно, М(у)=($~$с= = (х, х)+(х;, Ь), Ьеп КегЛ). По условию леммы найдется с', 1(с'„(з, такое, что (х,'., Й))0 н, значит ас,+чс,)а;,+(х'., х), т. е. шах (ас+$с)~ ппп (а,+(х,'., х)) Уйен М(у).
Таким образом !~!~с с(сяяс значение задач (з,) — (з,) 3(а, у) ) — ео. Задача (зз) — задача линейного программирования, поэтому по теореме существования (п. 3.2.1) решение в ней, а следовательно, н во всех остальных существует. Обозначим через х решение в (з,).
Б) Применение аналога теоремы Ферм а. Поскольку х~аЬзш)псу, где ср — выпуклая функция, то по аналогу теоремы Ферма (и. 2.3.1) О~бср(х). Используя формулу Моро — Рокафеллара и Дубовицкого — Милютина (и. 1.5.4), соотношение бМ„(х)=(КегЛ)х и лемму об ангуляторе ядра регулярного оператора (п. 7.2), получим, что существует с!= =()сс, ...., 1с.) и У*яву*, для которых 5 с У Хсх +Л у О Хс ссО т )сс 1 с=! с=! Прн этом, если )сс)0, то ас+(х,', х) =3(а, у), откуда 3(а.
у)= ~~ )с!а!+а )ссх~',х) =Я Цас — (Л'у'х) = с=! с 1 с=! = ~Г )ссас+(у, у). с=! С другой стороны, если ()с, у*) ен Л, то для любого х, такого, чтсь Лх+у=О, 5 в 2 с!с а, + (у', у) = ~ ' с!с (ас + (х,', х) ) ( с=! с=! ( !пах (ас+ (х,, х)) ~Г Лс — — !пах (а,+ (х,'., х)) < 3(а, у), !<!~с !~!~а с=! 5 т. е. 3(а,у)= яср (~)ссас+(у",у)). ~[> сьлс,ел .
с=! 125. Как н прн доказательстве необходимых условий 1 порядка, не ограничивая себя в общности, можно считать, что [~(Я) =О, 4~0. Рассмотрим задачу 1(х):=тахЦ,(х),...,Г (х))-~1п1; Р(х)=0. (з,) Лемма 2. х<щ!осш!пз,.
:) <) Если х 4' 1осппп з4, то Уе 0 Бх,: Цх, — х11 ( е, Р (х,) = О, ~,(х,)(0, !)О, =:,'ьх~1оспипз,. >'!> Введем обозначения х; = (х), Л=Р'(х), а;=(1/2)7" (х) [Ь, Ь[, р=(1!2)Р" (х) [Ь, Ь1, где Ь ~ К вЂ” фиксированный вектор. По лемме п. 9.1.1 условие (!) леммы о минимаксе выполняется. По лемме о мннимаксе существует элемент С=$(Ь), Л$+у=О, для которого шах(а,+(х,', $))= за (~зЬ;а,+(у', у)) = с~О м,ичел ~. ~ ~=о — зцр .У„(х) [Ь, Ь[ =: — Ч'(Ь). (4) х (хавел 2 По формуле Тейлора в силу соотношений ЛЬ=О, ЛЦ+у=О по- .лучаем прн !)О Р (х+й+!'$) =Р(х)+Р'(х) [!Ь+г'ц+ +(1/2) Р" (х) [!Ь+!зЦ, й+!зЦ+о(!з)=гз(ЛЦ+у)+о(!з) =о(гз). По теореме Люстерннка существует отображение Чп0-~Х окрестности точки х, такое, что Р(х+Ч>(х))=0, 1!Ч~(х))!~(КЦР(х)[!.
Полагая г(!) = у (х+ й+ !з$), получим Р(х+й+1-й+г(!)1=0, Цг(!))! (К ЦР(х+й+!зф)Ц = о (!з). Тогда, применив формулу Тейлора к ~, и используя (4), получаем (вспомнив, что (х,", Ь) (О, !)0) 1(х+ !Ь+ гз$+г (!)) = гпах (! (х,', Ь) + !з ((х,'., $) + а;))+ +о((з)(Гешах((х', ф)+ос)+о(!з)= — 'Ч'(Ь)+о(!з). с>о 2 Если допустить, что Ч'(Ь)(0, то получим противоречие с лем'мой 2. !> 126 9.2. Условия первого и второго порядка в классическом вариационном исчислении Цель этого пункта — показать, что классические необходимые условия (уравнение Эйлера, а также условия Лежандра,. Вейерштрасса и Якоби) являются простыми следствиями принципа максимума. 9.2.1.
Простейшая задача к, в. и. Рассмотрим вновь (ранее см. п. 4.2) простейшую задачу классического вариационного исчисления, для определенности задачу на минимум 47 (х ( )) = ~ Ь (1, х, х) й( -~ 1п1; х (г ) =' х, х (1,) = х,. (з). Здесь х(-)=(х,( ), ..., х„(.)) — вектор-функция. Напомним, что функция х( ) ~ Ст([1„11], К"), х(1 ) =х, х(1,) = =х„доставляет слабый локальный минимум в задаче (з), если она: доставляет локальный минимум в пространстве С'([1„1,], К"), т.
е. если существует 6>0, такое, что для любой функции х( ) я ~ С'([1„1,], К"), х(1,) =х„х (1,) = х,, для которой йх (.)— — х(.)11с п~,л,1 на,(6 выполняется неравенство 47(х( ))) 47(х( )). Напомнйм, что ИХ(')1~Сгнигп1,а"> = ШаХО»(')ИСПЬЛ,1,а"1 > ПХ(')ПСПи,а1.а">) Наряду со слабым экстремумом в простейшей задаче к.в.и. рассматривается понятие сильного экстремума. Говорят, что функция Х( )енКС'([(ы 1,], К"), (или принадлежащая более широкому классу, например, йГ '([1ы 1д, Й") ), х(1о) =хо' х(1,)=хь доставляет сильный локальный минимум, если она доставляет локальный минимум в пространстве С([(ь, 11], й"), т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
