Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач, страница 8

Среди ' выпуклых многогранников простейшую (в некотором смысле) структуру имеют симплексы (выпуклые оболочки конечногочисла аффинно независимых точек в К"), т. е. треугольники в Кт, треугольные пирамиды в Кз. 34 Особую роль в структуре выпуклых множеств играют крайние точки. Точка х выпуклого множества А называется крайней, если не существует точек х~Фхь хь х2енА, н числа Л, 0(Л~1, таких, что х=Лх1+ (1 — Л)хь У многогранников крайние точки — вершины. Имеет место т е о р е м а М и н к о в с к о г о: компактное мноасество в К" является выпуклой оболочкой своих крайних точек. 1.5.2. Операции над выпуклыми объектамн.

Приведем некоторые алгебраические н теоретико-множественные операции над выпуклыми объектами. Элементарно доказывается, что онн выпуклые объекты переводят в выпуклые. Операции над функциям н. 1) Сумма; (11+12) (х):= =1, (х) + )2(х); 2) конволюцня; У,Ю1») (х): = 1п((11 (х,) + +Ь(хг) ~х,+х,=х); 3) максимума Ц1У)») (х):=шах(1,(х), 1,(х)); 4) выпуклая оболочка минимума: (11со/~~») (х) =ппп (а)1(х1)+ +(1 — а)1(хз) ~аен(0, 1), ах,— (1 — а)хз=х). Третья операция может быть естественным образом распространена на произвольное семейство выпуклых функций. Операции над множества мн: 1) сумма: А~+А:= =(х~х=х1+хъ х~яАь хзенА»); 2) конволюцня: А,)+)А~.—— =О(аАП(1 — а)А»), ая$0; 1]; 3) пересечение: А1ПА»=(х)хек ~Аь х»еиА»); 4) выпуклая оболочка объединения: А1со))А»= =со(А,()А,), Третья операция может быть применена к любому семейству выпуклых множеств. Операции 1), 3) н'4) н над функциями, н над множествами вполне привычные, чего нельзя сказать про операции 2) — конволюцнн.

Их смысл н значение раскроются, когда речь пойдет' о двойственных соотношениях. В соответствии с общим замыслом этой книги в первой части ограничиваемся по преимушеству конечномерным случаем. Во второй части будет рассказано о выпуклом анализе в бесконечномерном пространстве, в первой части К вЂ” это Й". Одно из важнейших свойств выпуклых объектов состоит в том, что они допускают двойное описание: в основном н «двойственном» пространстве.

В конечномерном случае (когда Х= = К") двойственное пространство (пространство лннейных функционалов) может быть идентифицировано с Й", н это облегчает нашу задачу. Перейдем к определению двойственных операторов. Пусть ): й"-~-К вЂ” некоторая функция. Преобразованием Дескандра — Инга — Фенхеля функции ) называется функция 1" (у): =зпр((х, у) — 1(х)). Из определения 1* видно, что ~* — верхняя грань семейства аффннных функций, т. е. 1* выпукла. 35 Функция 1'" (х): = зпр((х, у) — ~' (у)) называется второй со-' пряженной к ).

Из определения сопряженной функции следует неравенство Юнга: (х, у) «((х) +(*(у). Легко подсчитать, что сопряженной к аффинпой функции',: » э" х-»а(х; $, а): = у $;х; — а будет «элементарная» функции 1=1 е(у; $, а), равная а в точке $ и +ос — в остальных точках, и,'я наоборот, е*(о; $, а) =а(; $, сс). Пусть А — непустое подмножество в й". Полярой множества Л называется множество Аы (уяР»~(х, у)«1 1~хе=А). Множество Аш=(хан(("1(х, у) «1 Ъ уенА') называется биполярой. Из определения Ае видно, что это пересечение семейства полупространств, содержащих нуль, т. е. выпуклое замкнутое множество, содержащее нуль. Нетрудно понять, что поляра отрезка (О; х) — полуплоскость П„:=(у((х, у)«1) и наоборот, П,»=(0, х). Отметим еще, что поляра шара В(0, г):='(хзх~ «г) — шар В(0, г-').

Пусть К вЂ” конус в й", Сопряженным конусом к К называется множество К»:=(уен(("~(х, у)>0 тхенК). Конус К»*:=(хя(т" 1(х, у)ъ0 "т'уенК~) называется вторым со- ~ пряженным конусом к К. Из определении К» видно, что это ( множество — пересечение полупространств, границами кото- г рых являются гиперплоскости, проходящие через нуль. Значит, ' К» — выпуклый замкнутый конус. Сразу видно, что К*= — Ко Субдифференциалом сублинейной функции р называется множество др:=(у1(х, у)«р(х) Чх).

Легко понять, что субдифференциалом евклидовой нормы х-~- ' (х~ в Й" является шар В(0, 1) =(х1~х) «1). Субдифференциалом (выпуклой собственной) функции 1 в точке х называется следующее множество: д((х):=(уенК" ~(х — х, у)«1(х) — 1(х) тх). Из определений сразу вытекает, что др и д~(х) — выпуклые подмножества в Й". Легко доказать, что они замкнуты. Пусть А — непустое подмножество Й". Функция зЛ(у):=зпр((х, у) )хенА) называется опорной функцией А. Субдифференциал линейной функции х-~(х, $) совпадает с (Ц. Опорная функция элемента $ есть линейная функция (о $). После каждого определения давались примеры.

Они могут показаться искусственными. На самом деле в них заложен зародыш тех соотношений двойственности; которые будут обсуждаться в следующих пунктах. Приведем еще два определения. Пусть А непустое подмножество в Й". Функция рА(х):=1п((сс)О~а 'хяА) (!пЮ=:+оо) называется функцией Минковского, а функция 6А(х): = ~ 1 оо, хКА — индикаторной функцией. Функция Минковского шара В(г" есть норма в 1,": о р(В1,")(х)=~)Г Цх,/') ', 1< р(оо, р(В1"„(х))= шах !х,! в=1 1~~~л Из определения рА (при выпуклом А) сразу следует эта выпуклая однородная (сублинейная) функция.

1.5.3. Теоремы двойственности и компактности. Придаднм точный смысл'высказыванию о том, что выпуклые объекты имеют двойное описание. Этот смысл раскрывает следующая Теорема двойственности. а) Функция ):11 ~й совпадает со своей второй сопряженной тогда и только тогда, когда она выпукла и замкнута (т. е. когда ее надграфик— выпуклое и замкнутое множество). б) Пусть А — непустое множество в 11". Оно совпадает со своей биполярой тогда и только тогда, когда А — выпукло, замкнуто и содержит нуль: в) Конус К~К" совпадает со своим вторым сопряженным, когда он является выпуклглм и замкнутым. г) Пусть р:й 11 — однородная первой степени функция с непустым субдифференциалом.

Для того чтобы было выполнено равенство здр=р, необходимо и достаточно, чтобы р была сублинейна и замкнута. д) Пусть А — непустое подмножество в 11": Для того чтобы было выполнено соотношение дзА=А, необходимо и достаточно, чтобы А было выпукло и замкнуто. Утверждение а) часто называют теоремой Фенхеля — Моро, утверждение б) — теоремой о биполяре. Выразим некоторые следствия из теоремы в виде алгебраических или теоретико- множественных равенств.

а) Пусть ) — выпуклая замкнутая собственная функция. Тогда из а) следует, что 1, с одной стороны, есть выпуклая обо- 37. лочка объединения «элементарных функций» е(«; х, /(х)), хан епбош/, а с другой — верхняя грань семейства аффинных функций, а именно ыр(а(", у, /«(у)) ~у~баю/«). 6) Пусть А — непустое выпуклое и замкнутое подмножество й" и ОепА. Тогда А= () (О, х1= () П„, где П«=(х!х, у>к: «ел уел' « «,. 1).

у) Пусть р — замкнутая сублинейная функция и дрФЯ. Тогда р=зпр ((«у)/у~др). 6) Пусть А — непустое выпуклое и замкнутое подмножество. Тогда А= П (х)= () П(у, зА(у)), П(у, а): =(х~(х, у) (а). «ел «едз л Эти соотношения и раскрывают дуальность описания выпуклых объектов. Переформулируем их словесно. Замкнутая выпуклая собственная функция — верхняя грань 4 аффинных функций, ее не превосходящих (Минковский).

Замкнутая сублинейная функция с непустым субдифференциалом есть верхняя грань линейных функций, ее не превосходящих (Хермандер). Замкнутое выпуклое подмножество есть пересечение полупространств, его содержащих (Минковский). Во второй части (п. 8.1) теорема двойственности будет доказана полностью в бесконечномерном варианте. Все утверждения а) — г), по сути дела, равносильны. Во второй части утверждения б) — г) будут выведены из а) — теоремы Фенхеля— Моро.

Здесь же докажем лишь утверждение 6) — теорему, о биполяре. О Из определения бнполяры следует, что Аеь = () П„, П„=(х~ (х, у) ~( Ц. Ясно, что П« — выпуклое замкнутое подмножество, содержащее нуль. Таким образом, если А=А«ь, то А выпукло, замкнуто и содержит нуль. Докажем теорему в другую сторону. Если х~А и у~А«, то из определения следует, что (х, у)«:1, т. е. АсАю.

Допустим, что имеется элемент ЫА«ь' А. Тогда (в силу допущения А выпукло и замкнуто) по второй теореме отде лимости найдется элемент алый«, такой, что зпр (х, у) (1, (х, у) )) 1. «ел В силу первого неравенства 4яА'„значит, для УаАьь долж. но выполняться неравенство (х, у)~1, а это противоречит второму из выписанных неравенств. (> Отметим следующий результат.