Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 41
Текст из файла (страница 41)
В соответствии с замыслом Лагранжа, составив функцию Лагранжа, рассмотрим две подзадачи: — гладкую задачу без ограничений Е((х, й), Л, Ло) — ппп; — выпуклую задачу Е((й,и),Л,Ао) - пцп; и б И о» (Л,у) — пнп; у б Р(й,И). Условие минимума во второй задаче запишем в виде тавтологическога принципа минимума ппп ь((х,и), Л, Ло) = Е((х, й), Л, Ло) о» (Л, Р(х, «)) > 0 У« б И.
(2) «ой Так что выражение «доя задачи (Р) выполнен принцип Лагранжа», означает, что имеют место условие стационарности (1) и принцип минимума (2). Соотношениями (1) — (2) можно пользоваться эвристически. 1.2. Доказательство принципа Лаграпжа дда Гладко-выпукльгк задач Доялаатвльство. В основе доказательства лежат два основополагающих факта классического и выпуклого анализа: теорема об обратном отображении и теорема отделимости.
П Регулярный случай. Хотя доказательство принципа Лагранжа и в обшем случае достаточно несложно, считаем целесообразным провести сначала доказательство в регулярном случае, где оно особенно просто, но содержит в себе все важнейшие компоненты рассуждений, приводящих к цели в обшей ситуации. Здесь все основывается на теореме Люстерника. Обозначим Р,'(х,й) = Л. Выбрав и Е И строим отображение ф(,;и):Ц хк У: ф(х,а;и): = (1 — а)Р(а+ х,й) + аР(й+ х,и). Эта функция, очевидно, непрерывно дифференцируема в окрестности точки (О, 0) б Х х В и ф ((0,0);и)[х,а[ = Лх+ аР(й,и). (о) Па теореме Люстерника, если Лх = О, то х — касательный вектор к многообразию (х [ Р(х,й) = О), и значит, сушествует отображение г: [ — 1,1[ - Х такое, что Р(й+ гх + г(1),й) = О,г(1) = а(1).
В силу того, что (й,й) — сильный локальный минимум в задаче (Р), а (й+ 3х+ г(г),й) — допустимая пара, получаем: уо(й) < 1о(й + гх + г(Г)) = уо(х) + «(Го(Х),х) + а(1), откупа вытекает, что ()о(й),х) = О, т.е. /о(х) б (КегЛ) . Из леммы об аннулятаре ядра регулярного оператора последует тогда, что найдется элемент Л Е У' 256 Глава 6. Общая теория экстремальных задач такой, что 1О(6) + Л'Л = О. А зто равенство есть не что иное, как условие стационарнасти. Осталось доказать принцип минимума. Пусть е — некоторый элемент из И. В силу условия регулярности сушествует элемент х(е) такой, что Р,(й,й)х(е) !.
Р(х,е) =- О. Эта означает (см. (!)), что пара (х(е),!) Е (КегФ'(0,0;е)) . Тогда снова по теореме Люстерннка найдем отображения (г,( ), р„()): [О, 1[ Х х )к такие, чта для х„(1) = х -1-гх(е) -1- г,(1) н а,(1) = 1 -1- рг(1) выполнено тождества (1 — а,(1))Р(х,(1),0) + а (1)Р(х,(1),е) = О, г,(1) = о(1), р,(1) = о(1). Из определения гладкой выпуклости найдем элемент и„(1) б И такой, что Р(х„(1),и„.(1)) = О, и следовательно, (х„(1),и„(1)) — допустимая пара, т.
е, 1О(х,(1)) > Уо(У), откуда 0 < Г ( „(1))[, = (1О(6),х(е)) = 1 (Л'Л,х(е)) = -(Л,йх(е)) = (Л,Р(х,е)) П инцип минимума, а с ним и принцип Лагранжа для регулярного Р гладка-выпуклого случая доказан. 2. Общий случай. Пусть теперь Р— слабо регулярно. Обозначим Ьо = 1шЛ, А = Р(У,И), С = Ьо+ А. Пусть я: г'/Ьо = Я вЂ” каноническая проекция. Из условия теоремы вытекает, что Я вЂ” конечномерное пространство.
Нада разобрать два случая; 0 Ф !пгггС, 0 б 1пгяС вырожаенный н невырожденный. В вырожденном случае по теореме отделимости существует х' Е Я' такой, что (з',з) > 0 уз Е !гС. Положим Л = я*х' (я' — оператор, сопряженный к я). В силу того, что ог — сюрьективный оператор, Л ~ О. Имеем: (Л,йх+Р(й,и)) = (я*а',Лх+ Р(й,и)) = = (з',ог(Лх 6 Р(х,и))) > 0 !!Г х Е Х, и 6 И с: (!), (2).
Осталось рассмотреть невырожденный случай. Коль скоро 0 6 !и!яС, существует натуральное число т, (г;),, а, > 0 такие, что 2 а!з, = О, !=! з! = ггР(У е ) и сапе(з );, = Я. Тогда по определению 2 а Р(6 е!) Е Ьо, т.е. существует элемент г Е Х такой, что Л~+ 2 а,Р(х, е!) = О. Далее В= ! поступаем подобно тому, как в ре!улярнам случае. Выбрав ео Е И, определяем отображение 6 1.
Принцип Лаораюво для необходимых условий экстремума 257 хб Х, а=(а„...,а,„). Оно отобразкает Х х К о' в Х, строго дифференцируемо и Ф'(О, О,..., 0;ео)[х,ао,а[ = Лх + 2 а<Р(х,е!). Пусть Лй + Р(6,6) = О. Тогла з=о Ф (О О,...,0 6)[х + ес, 1, еа[ = Лх + Р(х, е) -ь е(йг + 2 а Р(х е!)) = 0 !=! и по теореме Люстерника найдугся г(): [ — 1,1[ Х, р,: [-1,1[ — !к, 0 < о < ег такие, что г(1) = о(1), р,(1) = о(1) и Ф(6+!С+ с(1),1+ ро(1),еоа! + р!(1),...,еоа +р (1)) = 0 916 [ — 1,!!.
Из условия выпуклости получаем, что найдется элемент и(Ц Е И такой, что Р(х+ ох хь е1с + г(1), и(1)) = О, откуда (уо(х), й) > О. Положив 6 = У, получим, чта 1О(х) Е (Кегй)~. Из леммы о нетривиальности аннулятора следует, что существует элемент Л! Е 1ч такой, что 1О(х) + Л*Л! — — О. Пусть теперь Р(х,и) Е Ео. Тогда найдем элемент х(и) Е Х такой, что йх(и) + Р(х, и) = 0 (еа) Следовательно, 0 < (Уо(6) е(и)) =" — (Л'Л!,х(и)) 0 (Л!,Лх(и)) 1="'! (ЛпР(6 и)) Наконец из теоремы отделимости (взяв С = со(С г! 3) где В шар с 'ге "тром г! Е 1о, (Л!, О) > О, который не пересекается с (у [ (Л!, 6) = 0) ~ 1п1 С ~ й1, убеждаемся, что можно применить теорему отделимости) получим, что существует элемент Л Е У" такой, что Л[И = Л! и (Л,Р(х,и)) > 0 ои, откуда слелует принцип минимума. Из первого уравнения получаем (Л,Лх) = (Л!,Лх)' = (Л'Л!,х) = -(1О(2),х) ох.
го, (ь! Это — условие стационарности. Таким образом, принцип Лагранжа доказан. Элементарные задачи Принцип Лагранжа сводит вопрос о необходимых условиях задач с ограничениями к необходимым условиям для более просто устроенных (злемелтарлых) задач. Сформулируем необходимые условия экстремума дяя четырех важнейших элементарных задач. Элементарлал гладкая задача — это задача без ограничений: У(х) пип, где функция 1 предполагается днфференцируемой. Согласно теореме Ферма необходимым условием минимума в (1) является равенспю озко! б 1. Принцип Лагравлга для пеобходпмык условий экстремума 259 258 Глава б.
Обвгая теория экстремальных залая Аналогом теоремы Ферма для выпуклых функций является соотно- шение 0 Е д1(й). ( 1') Это необходимое и достаточное условие минимума 1 в точке й (ср. с п. б.1 и (1)). Элементарной задачей линейного программирования назовем следуюш1по: ~~«, Люв« - ппп; и; > О, (Л = (Л«,...,Л ) Е К"). (11) «>и Необходимым и достаточным условием того, что вектор й Э 0 является решением этой задачи, является выполнение условий неотрицательности и дотыкяющеи нежеспгкосте (2) Л; > 0 Л;й; = 0 уо.
Этот факт совершенно очевиден. Элементарной задачей классического вариационного исчисления или задачей йыьца называется такая задача: В(х()) = / Ь(1,х(1),х(1)) И+1(х(1о),х(1«)) - ппп; (111) б1 — — Х,(1)+Х.(1) =о (3) и усммия трансверсольности (они выполнены при условии непрерывной дифференцнруемости интегпанта и тепминанта): Хь(И) = ( — 1А(ь1 ' (3') где Хо(1) = Щ,й(1),У(.)), Х»(1) = Ь»(1>У(1),Й(1)), а 1»<и1 = 1»(Ь1(й(1о)> й(1«)) (доказательство см. в б 2 гл. 3). Элементарной задачей оптимального управления нли простейшей ляпуновской задачей мы называем следующую задачу: о(в(.)) = / ««(г,в(1))«й ппп; х(г) Е И, где х() = (х«(),...
>Х»()) — векгор-функция, иэ пространства С' ®,гз],К ) непрерывно-дифференпируемыхвектопчйункций, Ь и1— функции (соотвагстаенно) 2х+ 1..и 2п переменных. Необходимые условия экстоемчма в задаче Больна состоят из уравнения Эйлера гле х( ): ]1о,1«] - К' — кусочно-непрерывная функция, Ь(э ): К х К" К вЂ” непрерывная функция, И вЂ” произвольное множество в К', хй) Е И во всех точках непрерывности.
Легко поияц, что кусочно-непрерывная векторФункция й() аосеохеет абсолютный минимум в задаче (1»') тогда и,только тогда, когда е лн«бой точке неногоывности функции й(.) выполнено соотношение: ш1пп(г,о) = Л(1,й(1))> (4) Соотношения типа (4) называют принципам минимума. Применение принципа Лагранжа для гладка-выпуклых задач к конкретным классам экстремальных проблем основывается на трех леммах— о.нетривиальности.лннтлятопа. о эамкнътасти образа н ядре регулярного оператора Доказательства;этих лемм см. в 6 5 гл.
1. 1.3. следс$анн нрнннн~а лапганага Задачи ютемптеческого программирования Применение принципа Лагранжа лля гладко-выпуклых задач начнем с гладких задач математического программирования: ,Го(х) — «ппп; Уг(х) < 6, 1 ~о < пз, Р(х) ~: О. (Р) Свелятвие 1, (Провеяв Лераижа в мвтемяпеехкти программирования). Пкть в задаче (Тйл) пространства Х и г — бакановы, Уо — окрестность точки й Е Х, р«'.Уо,-+ К, О < 4,~ зп«> Р111о — > Зг, Тогда, если уг и Р спцнмо диффермщирухпы, Р'(й)Х вЂ” ца>щкиутое надпространство 3г, а' й доставляет локальнцй гтницум зад1гчег гро, для, лее выпоонен принцип .баграижа.
Если неравенств пет и отобралсение Р регулярно в точке й„то мнжитель Ло можно считать ровным единцце (см. п«8.2 гг. 1). Фраза»выполнен принцип Лагранжа» в данном случае означает, гго сушествуют не равные одновременно нулю числа Ло,..., Л и элемент Л Е Зг*, которые удовлетворяют условиям неотпицательности, дополняющей нежесткости 'и стационарности: Е,(й, Л,ЛН..., Л.,ло) = ~" Л;1!(й)+ (Р'(й))'Л = О. «=о Действительно, если Р>(й)Х вЂ” собственное надпространство, то по лемме о нетривиальности аннулятора найдется элемент Л Ф 0 такой, что Сь(й«Л, О,..., О, 0) = О, а если Р»(й)Х = 3', надо положить И = К,, х = (п«,.«.,и ),У(хв) = (Л(х)+ вн>,Ух(х)+ вы,Р(х)), г' Х х И - К х 3', применить сформулированную теорему (воспользовавшись б 1.
Принцип Лагранжа для яеобходимых условий экезремума 2б1 260 Глава 6. Общая теория экстремальяых задач леммой о замкнутости) и условия экстремума в двух названных выше элементарных задачах — гладкой без ограничений и элементарной задаче выпуклого программирования. Доказанная теорема содержит в себе правило множителей Лагранжа лля конечномерной гладкой задачи с равенствами (это правило, подразумевая регулярность ограничения, Лагранж сформулировал, в частности, в своей книге Лагранж [1801], из которой мы заимствовали свой эпиграф); правило множителей Лагранжа для бесконечномерной задачи с регулярными равенствами (теорему Люстерника [1934]); правило множителей Лагранжа для конечномерной гладкой задачи с равенствами и неравенствами (теорему Джона) и т.
п. Из гладко-выпуклого принципа выводится принцип Лагранжа лля задач выпуклого программирования (теорема Куна — Таккера). Мы не будем проводить этого вывода, ограничившись краткой формулировкой. В выпуклых задачах принцип Лагранжа приобретает завершенную форму: при некоторых мноэсителях Лагранзка, удовлетворяющих условиям неотрицательности и дополняющей неэсесткости, функцио Лагранхса достигает в точке, являющейся решением задачи своего минимума по тем ограничениям, которые не были включены в функцию Лагранзка (см.
[МИ-Т[). Ниже мы вернемся к этому результату при обсуждений условий экстремума ляпуновских задач. Принцип Лагранжа в задачах классического аариациониого исчисления Следствие 2 (Принцип Лагранжа в задаче Лагранжа). Пусть в задаче (Рз) У = В, й = Ц, з = О,! — фиксированы, и все функции еп !! и отобрагкение оз непрерывно дифференцируемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
