Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи (1125256), страница 32
Текст из файла (страница 32)
~(х) также удовлетворяет условию Лнпшица. т1в ГЛ. У. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА В силу замечания, сделанного после определения 2Л, и того факта, что ~'(хо, х) существует и определяется формулой (2Л2), получаем )г (х, хо) = ~' (х„х) = шах ((х, ~„(х„а)): а ~ А (хо) ).
а Последнюю формулу можно записать и иначе: Р (х, х ) = шах ((х, хо ): хо ен 7х' (хо, А (хо))). Сделаем несколько замечаний: У 1) множество ~х (х„А (хо)) компактно как непрерывный образ компактного множества А(хо); 2) в силу теоремы 1Л.7 множество со~ (х„А(хо)) выпукло и компактно; 3) максимум линейной функции на множестве и на его выпуклой оболочке один и тот же. Поэтому г" (х, х ) = шах((х, хо): хоен соД,(хо, А(х,))).
х* Итак, г"(х, хо) есть выпуклая, положительно однородная и замкнутая функция х. На самом деле она даже непрерывна, так как из компактности со)х(хо А(хо)) следует, что г"(х, хо) определена для всех х и, значит, шо теореме 11ЛА непрерывна. Ясно, что функцию Р(х, хо) можно рассматривать как верхнюю вьпгуклую аппроксимацию функции 1 в точме хо. По теореме 11.3Л1 хо ондг'(О, хо) тогда и только тогда, когда х* ~ со(х(хо, А(х )) и (О, хо> Г(0, хо). Но последнее выполняется, очевидно, для всех хо, ибо г'(О, хо) = О.
Поэтому дУ(хо) = дР(0, хо) = со~„(хо, А(хо)), что и требовалось доказать. 3. Функция расстояния до множества. Пусть М— произвольное множество. рассмотрим следующую функцию: Ы(х) М) =(В1((х — у(: у ы М), (2Л5) $2. ФУНКШ1И, ДОПУСКАЮЩИЕ АППРОКСИЫАПИЮ 219 где !!х — у!1=<х — у, х у>ь — обычное эвклидово расстояние между точками.
Тогда Жх)М) есть раостояние от точки х до множества М. Поскольку расстояния до множества и до его замьткачвяя одинаковы, то бев ограничения общности будем в дальнейшем считать, что М замкнуто. Это позволяет переписать формулу (215) в следующем виде: 2((х(М) = ш1п(((х — у((: у~ М». Множество М(х) = (у 2яМ: )!х — у!! = й(х)М)) замкнуто и ограничено, а поэтому компактно. Лемма 2.3. Функция с)(х)М) удовлетворяет условию Липи2ица с константой А=1. Доказательство.
Если у1 2я М(х1), уз шМ(хг), то !!х1 у11 !!х2 у1!! «И(х1!М) 2)(х2!М) « «1Х! у2!! 1х2 у21. Из неравенства треугольника вытекает, что !)х! — у21 — !!х2 — у2!! » «!!х! — х2!), 1х2 — у1!! — 1х1 — у1!! «!!Х1 — х2!1, поэтому Ы(Х1(М) — д(хз!М)! «!!Х1 — Х2!), что п требовалось доказать.
Теорема 2.7. Если д(х)М))0, то ~( -» М» ). 4(х+Й(М) — В(х!М) 21О )' =шш 11тх х в): уенМ" (х)~. у ( Н(х(М) Доказательство. Если хвьу, то )!х — у)! есть дифференцнруемая функция х, градиент которой равен !! -у!!'=!!*'-у!! (2.16) Без ограничения общности можно считать, что М компактно, т. е. ограничено, так как, если отбросить точки 2зо ГЛ. У.
НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА М, лежащие достаточно далеко, то расстояние до вновь полученного множества при малых изменениях х будет совпадать с д(х~М). Записав д(х~М) в виде с)(х) М) = — п1ах( — 1х — у~1: у АМ) и воспользовавшись теоремой 2.6, формулой (212) и выражением (2.16) для грддиента, немедленно получим утверждение теоремы. Теорема 2.8. Если й(х(М))0, то функция Ь(х, х) = *'(* У, уы М(х), (2.17) есть в.в.а. для а в точке х, а (а(х)М)) '(х — у) — соответствующий субдифференциал. Доказательство.
Так как функция а(х(М) удовлетворяет условию Липшица, то г'(х, х) = а' (х, к~М) = ш(В * У . у в= М(х)~. ( в( (м) (2.18) Из этого выражения утверждение теоремы следует непосредственно. Теорема 2ЕЛ Пусть а(х~М) =О, и пусть К„(х) выпуклый конус касательных направлений для М в х. Тогда функция )ь(х, х) = 1В1(~~х — у~1: уви Км(х)] = а(х)КМ(х)) есть верхняя выпуклая аппроксимация для а в точке х, а ВД( — Км(х)) — соответствующий субдифференциал. Доказательство. Пусть ушК„(х). По определению существует такая функция г(Л), Л-'г(Л) — О при Л- О, что х+Лу+г(Л) шМ при малых Л.
Так как с)(х!М) удовлетворяет условию Липшица, то Е(- ) 1. Ы(в+Ле)М) — д(х М) ььь 1(х+ Й) — (х+ Ху+ г (Х))1 ььв ()(х — у1+ 11ш —" =1х — у ~. ььь $2. ФУНКЦИИ, ДОПУСКАЮЩИЕ АППРОКСИМАЦИЮ 22$ Так как у — произвольный элемент Км(х), то Х(х, х)(1о1((х — у~: уев Хм(х)) = д(х[Км(х)). (2Л9) Согласно п. 4 $3 главы 11 функция д(х~К„(х)) выпукла. Теорема 3.5 показывает, что эта функция есть точная верхняя грань линейных функций и, значит, замкнута. Наконец, положительная однородность о(х)К~(х)) следует из того, что К (х) — конус.
В этих условиях формула (2.19) показывает, что функция йх!К~(х)) есть в.в.а. для д в точке х. Вычислим субдифференциал функции д(х)К (х)) при х=О. Заметим, что эта функция совпадает с введенной для выпуклого случая в п. 4 $3 главы 11 функцией д,( ° !Км(х)), когда С В, т. е. С есть единичный шар. Поэтому можно воспользоваться теоремой П.ЗЛ5, которая показывает, что дд(0!К~(х)) = дб(0!Км(х)) О (х*: И'~(х*) (1). Согласно формулам (11.3.25) н (11.3.26) И'в (х*) = шах ((х, х*): '1 х1( Ц = 1 хе ~, дб (О) Км(х)) = — Км(х), поэтому дд(0) Км(х)) = ( — Км(х)) П (х': ~х*~~ (Ц, что и требовалось доказать. 4. Главные верхние аппроксимации и главные субдифференциалы.
Как показывают приведенные выше примеры, для данной функции 1 в точке х может существовать много верхних выпуклых аппроксимаций. Однако, естественно, что если Ь1 и Ьз — в.в.а. функции 1 в точке х и Ь1 ~ Ьп то Ь1 хуже приближает функцию 1 в окрестности точки х. Это мотивирует следующее Определение 2.4.
В.в.а. Ь функции 1 в точке х называется славной, если не существует другой в. в. а. Ь1 такой, что Ь(х, х) > Ь1(х, х) 222 ГЛ. У. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА для всех х. Соответствующий в.в. а. Ь субдифференциал называется главным. Т е о р е м а 2 10. Если Е(х, х) ггосле доопргдвлгния г'(О, х) =О является выпуклой замкнутой функцией, то существует единственный главный субдиффгрвнциал. В частности, если 1 — выпуклая непрерьгвная функция, то ев обычный субдифференциал является единственным главным субдиффервнциалом, Теорема очевидным образом следует пз определения главного субдифференциала.
Условимся, что в дальнейшем всегда, когда выполнены условия теоремы 2.10 под рассматриваемым в контексте субдифференциалом понимается главный субдифференциал. Теорема 2.11. Если Ь(х, х) = <х, х*> есть в.в.а. функции 1 в точке х, то Ь(х, х) — главная в.в.а., а х"— главный субдиффгренциал. Доказательство.
Пусть существует в.в.а. Ьг такая, что <х, х") ~ Ьг(х, х) для всех х. Возьмем х, Бед~(х), где д)(х) соответствует Ьг(х, х). Тогда в силу формулы (2.3) получаем, что (х, х"))~Ь,(х, х)~)(х, х,г. Нетрудно убедиться, что одна линейная функции может быть всюду больше другой лишь в том случае, если онп совпадают. Поэтому (х, х*г = Ьг (х, х) = (х, х г, т. е. Ь = Ьг. В заключение приведем несколько абстрактнуго теорему о существовании главного дифференциала.
Она не используется в дальнейшем изложении. Прн ее доказательстве предполагается, что читатель знаком с частично упорядоченными множествами в объеме $2 главы 1 книги Н. Данфорда и Дж. Т. Шварца (11. Теорема 2.12. Пусть Е(х, х) как функция х г мкнута и нг принимает значений, равных — . Тогда для каждого х такого, что Е(х, х) (+г, существует главная э г. эгнкции, допгсклюшив лппгоксимлцию 22З верхняя выпуклая аппроксимация Ь такая, что й(х, х) = =Р(х, х), и Р (х, х) = (пг Ь (х, х), ь где нижняя грань берется по всем главньив выпуклым аппроксимациям. Доказательство. Последнее утверждение теоремы очевидным образом следует из первого, поэтому кратко проведем доказательство только первого утверждения. Пусть Р(хг, х) — конечное число.
Построим функцию (ЛР(х„х), если х= Лхг, Л)0, ~+ со, если хФЛхг, Л вО. Легко видеть, что Ьв — в.в.а. и Ь-„совпадает с Р, когда х = хг Рассмотрим множество всех в. в. а. й таких, что Ь~~(й-„. Очевидно, что это есть частично упорядоченное множество, где порядок задается неравенством Ь1~ Ьг, если соотношение й,(х, х) ~ Ьг(х, х) выполнено для всех х. Так как Р(й~(й„;, то Ь(хг, х) = =Р(хг, х). Заметим, что функция Ь выпукла, замкнута и положительно однородна тогда и только тогда, когда ер1 й есть выпуклый замкнутый конус.
Пусть теперь й„— линейно упорядоченное подмнол ество рассматриваемого множества, т. е. для любых се~ и сгг либоЬ„, ~(й„„либо йа* чч йке * Рассмотрим множество Н = () ер)й„(, х). а Нетрудно убедиться, что в силу линейной упорядоченности семейства й множество Н есть выпуклый конус. Так как й >Р, то Н вЂ” ер(Р( °, х), а так как Р— замкнутая функция, то ер1 Р(*, х) есть замкнутое множество и Й-ергР( °, х).
Зададим теперь функцию Ь при помощи 224 ГЛ.Ч. НЕОБХОДИМЫЕ УСЛСВИЯ ЭКСТРЕМУМА ее надграфика ер( Ь =Й. Н вЂ” выпуклый замкнутый конус и поэтому Ь выпуклая замкнутая положительно однородная функция. Так как ер( г ( °, х) — ер( Ь ер( Ь„ то г" ~ Ь < Ь„. Таким образом, Ь есть в.в. а. и Ь является минорантой линейно упорядоченного множества. Согласно лемме Цорна в этом случае рассматриваемое множество верхних выпуклых аппроксимаций имеет минимальный элемент Ьг, т. е. з данном случае это означает, что не существует другого Ь такого, что Ьг~ Ь.
Это как раз и показывает, что Ьг — главная в.в.а. Теорема доказана. в 3. Отображения, локально сопряженные к многозначным отображениям В главе П1 было дано определение многозначных отображений и были изучены свойства выпуклых отображений. Одним из основных понятий, введенных там, было понятие локально сопряженного отображения. В этом параграфе будут рассмотрены многозначные отображения, график которых чже не обязательно является выпуклым. Читателю рекомендуется перед дальнейшим чтением еще раз просмотреть основные определения главы 1П. Пусть Х и У вЂ” конечномерные пространства и Я ХХ У вЂ” их прямое произведение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
