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