Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 41
Текст из файла (страница 41)
Для того, чтобы Следствие (о с = А, необходимо и достаточно, чтобы имело место равенство длА =, не мнолсество А было выпукло и замкнуто; для того, чтобы имело место д —, еобхадимо и достаточно, чтобы сублинвйная функция р равенство вдр = р, н была замкнутой. Глава б. Общая теория экстремальных задач 252 конечны и хотя бы одна из нид непрерывна. Тогда для всех х Е дошУ~ гг дою Тг справедливо формула д(Т +Ту)(х) = ду,( )+ду,( ), доказательство. В силу того очевидною факта, что (Т~ + /2) (х; ) = 21(х; ) + Л(х;.), х Е Х (пге Т'(х, ) — производная по направлению функции Т в ~очке х; если Т выпукла, Т" (х, ) — аублинейна), достаточно доказать теорему для сублинейных функций р,( ) = У,'(х; ), 12.
Мы ограничимся случаем, когда одна из них, скажем, замки а, а уг, другая непрерывна (и тем самым также замкнута). В этом м, р, случае дрг есть компакт и поэтому множество др~ + дрг замкнуто (это нетрулное упражнение из топологии). Нам еше понадобится одно соотношение: в(А, + Аг) = вА, + вА2 (з), верное лля любых множеств А~ и Аг из Х, проверка которого элементарна.
Применяя теперь следствие о субдифференциале и опорной функции и используя (з), будем иметь о(Р~ +Р2) = д(вдР~ + вдрг) = дв(др~ + дрг) = др, + др Теорема Дубовицкого — Милютина. Пусть У,; Х вЂ” Й, з = 1,2 выпуклые функции, непрерывные в точке х Е Х и 7,(х) = Тг(х). Тогда дшах(/н уг)(х) = со (дТ1(х) ы дуг(х)). Доказательство. В силу легко проверяемого равенства (шах(Л 22)) (х1') = гоахф(х; ),( (х;.)) теорему достаточно доказать для сублинейных функций р; = Т,'(х; ), з = ! 2.
Так к ак как У„з = 1,2, непрерывны в х, то и функции р,, з = 1,2, непрерывны. Тогда по теореме о компактности субдифференциала, множества др„з = 1, 2, компактны, а значит, и множество со(д у,(х) Гг дух)) компактно (это тоже простое утверждение из топологии). Нам еше понадобится следующее, просто проверяемое равенство в(со(А, гг Аг)) = шах(ваывА2) (з), справедливое для любых А, С Х, з = 1,2, о с бди н Применяя теперь последовательно первое утверждение тео теоремы о су лифференциале и опорной функции, (з) и затем второе утверждение упомянутой теоремы, булем иметь дшах(рнрг) = дтах(вдрпвдр,) = дв(со(др~ Гг дрг)) = со(др, !2 д ).
Т еорема Дубовишсого — Милютина имеет следующее важное обобщение: б !. Принцип Лагранлсй для необходимых условий экстремума 253 Теорема (В. Левина об очистке). Пусть Т вЂ” компакт, Ьл — п -мгриог прог тринство, Р: Т х Ь„К, (1, х) — Тг(1, х) — функция, иолунгирврывная сверку ио ! иуи казсдом фиксированном х и выпуклая по х при коз«дом фиксированном 1. Положим Т(х) = гпах,атР(1,х). Тогда для любого у Е ду'(х) найдутся г Е Я, т < и+ 1, (т;),',, т, Е Т такие, что (А) /(тнх)=Т(х), ! <з<т, (В) у Е со(уп...,у„), гдв у, Е д,Р(т„х), ! < з < г.
Этот результат относится к еше одному важному принципу «очистки» Весьма часто, и в случае конечно-параметрического семейства выпуклых функций это так (в этом и состоит теорема об очистке), все множество может быть заменено на свою часть с сохранением какого-то важного свойства. Так и здесь: можно выкинуть все точки множества Т, кроме и + 1 точки, и уже на семействе из и + 1 функции минимум их максимума совпадает с минимаксом по всему семейству. Более полробно о выпуклом анализе см.
в книге (МИ-Т). % 1. Принцип Лагранжа для необходимнх условий экстремума ° Можно высказать следуюший абший принцип. Если ишезсл максимум илн минимум некоторой функции мне~их переменных при условии, чзо между этими переменными имеется слазь, заааыемал одним или несколькими уравнениями, нужна прибавить х минимизируемой функции функции, заааюшие уравнения свези, умноженнме на неопределенные миожизени, и искать затем максимум нли минимум построенной суммы, ках если бы переменные были независимы. Полученные уравнения, присоединенные к уравнениям салан, паслгакат длл определения всех неизвестных . Логроллс Этот параграф посвящен обоснованию следующего тезиса: необходимыв условия экстремума в задачал, гдв воедино слиты гладкая и выпуклая структуры, соответствуют принципу Пагранжса снятия ограничений.
(Изначальный вариант принципа Лагранжа выражен в приведенном нами эпиграфе.) Мы докажем одну общую теорему, навеянную общим замыслом Лагранжа, которая в качестве следствий солержит необходимые условия экстремума в математическом и выпуклом программировании, вариационном исчислении и оптимальном управлении, ляпуновских задачах и многих других. Но сначала мы (после формулировки теоремы) продемонстрируем, как эвристически пользоваться идеей Лагранжа, т.е. как автоматически писать правильные необходимые условия в разнообразных задачах на максимум и минимум.
254 Глава 6. Обшво теория экстремальных задач 1.1. Формулировка прппцппа Лагранжа ддп гладко-выпуклых задач Пусть Х и 1' нормированные пространства, И вЂ” некоторое множество. Рассмотрим задачу: ф 1. Принцип Лаграшка для веобхедяммх условий экстремума Необходимое условие экстремума в первой задаче пишется в соответствии с теоремой Ферма для глалких функций; оно состоит в условии стацианарнасти г,((й,й),Л,Ло) = О, о» Л ~о(й)+ (Р(й,й))'Л = О.
(1) уо(х) ппп; Р(х,и) =О, ибИ, гле Уо: По т Р: По х И У, По — окрестность в Х. Таким образом, в рассматриваемой задаче имеются ограничения типа равенств, параметризованные множеством И. Мы скажем, что пара (й,й) доставляет сильный локальный минимум в задаче (Р), если найдется б > 0 такое, что для любой пары (х,и), для которой Р(х,и) = О, и б И и [[х — Щл < б выполняется неравенство: Уо(х) > 1«(й). Функция г-((х и),л,ло): = Ло,Го(х)+ (Л,Р(х,и)), Ло > О называется функцией Пагранжа задачи (Р). Число Ло и элемент Л б У' называются мншкитгллии Лагранжа ((Л,у) — это действие линейного функционала Л б У" на элемент у б У).
Отображение Р в (Р) назовем гладка-выпуклым в точке (й, й), если отображение х — Р(х,и) непрерывно дифференцируемо по в окрестности тачки х (или даже строго дифференцируема в й) для всех и Е И, а множество Р(х,И) выпукло для всех х б По. Если Р в (Р) гладко-выпукло, назовем эту задачу гладко-выпуклой. Если Р,'(й,й)Х = К, то назовем Р регулярным отображением, а если подпространство Р«(х,й)Х замкнуто в Х и имеет конечную коразмерность в У (т.е. дополняемо до Х конечномерным подпространством), отображение Р назовем слаба регулярным в точке (х, й) . Теорема (Прияцип Лаграшка длв гладка-выпуклых задач). Пусть Х и У вЂ” банахавы пространства, И вЂ” мивиггства, Уо — диффереицируема в точке й, а Р— гладка-выпукла и слабо регулярно. Тогда если точка (х, й) доставляет сильный локальный минимум задаче (Р), та для задачи (Р) в этой точке выполнен принцип Пагранжа.
Если Р рггуллрна, та Ао Ф О. Расшифруем, что означает выражение «для задачи (Р) в данной точке выполнен принцип Лагранжа», В задаче (Р) два аргумента — х и и. В соответствии с замыслом Лагранжа, составив функцию Лагранжа, рассмотрим две подзадачи: — гладкую задачу без ограничений Е((х, й), Л, Ло) — ппп; — выпуклую задачу Е((й,и),Л,Ао) - пцп; и б И о» (Л,у) — пнп; у б Р(й,И). Условие минимума во второй задаче запишем в виде тавтологическога принципа минимума ппп ь((х,и), Л, Ло) = Е((х, й), Л, Ло) о» (Л, Р(х, «)) > 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 (Л'Л,х(е)) = -(Л,йх(е)) = (Л,Р(х,е)) П инцип минимума, а с ним и принцип Лагранжа лля регулярного Р гладка-выпуклого случая доказан.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
