Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 51
Текст из файла (страница 51)
Пример 5. Пусть 1(и) = п1ах (и; 0) (и ш И' = Е'). Если (У = Е', то Пт =(0), ду(0) = [О, 1) и (8) имеет место ли1пь для се =.О. Если (У = (и ш Е'. и ) О), то по-прежнеьту(Уе=(0),но неравенство (8) здесь выполняется для всех св ш дУ (0) = [О, 1[. 6. Определение 2. Пусть Е, Ен — евклидовы пространства, И'с с Е", П(Е ) — множество всех непустых множеств из Е".
Говорят, что на И' задано многовиачное отобрахсение Р: И'-» П(Е ), если наждой точке и ш И' поставлено в соответствие некоторое множество Р(и) с П(Е ). Определение 3, Многозначное отображение. которое каждой точке и из открытого выпуклого множества И' с Ев ставит в соответствие субдифференцнал дУ(и) некоторой выпуклой на И' функции 1(и), называется субдифференциалъным отображением и обозначается через дУ. Субдифференциальпое отображение обладает рядом замечательных свойств [18, 21, 132, 255, 264); на некоторых из них мы здесь кратко остановимся.
Определение 4. Пусть й' — множество из Е". Многозначное отображение Р: ту-»П(Е'") называется: 1) номпаптным, если для любого компактного множества (Ус йт множество Р ((У) = () Р (и) компактно; ис П 2) монотонным, если (с(и) — с(г), и — г) ) 0 при всех и, г ш И', с(и) шР(и), с(г) шР(г); 3) выпуллоеначным, если Р(и) — выпуклое мпоткество при каждом и ш ш И', 4) полунепрсрывным сверху в точке г ш И', если из того, что (ге) -» г (оь ем Ит) и (св) -» с (се ш Р(ш), )с = 1, 2, ...), следует с ш Р(г); 5) полунепрерывным снизу в точке г ш И; если для всзъого элемента с ш р (г) я лтобой последовательности (гл) -» г(ге ш И') найдутся се ш Р(гь) такие, что (се) -» с. Т ео р ем а 5, Пусте 1(и) — выпунлая фунпцин на открытом выпуклом множестве И' ие Е", Тогда субдифференциальное отображение дУ: (У-» -»-П(Е") выпунлоеначно, монотонно, полунепрерывно сверху, номпаетно.
Дока за тельство. Выпуклозначность отображения дУ следует из теоремы 2. Возьмем произвольные и, ген И', с(и) ш дУ(и), с(г] ш дУ(г). Тогда согласно (2) 1(и) — 1(г) ) (с(г), и — г), 1(г) — 1(и) ) (с(и), г — и), Сложив эти два неравенства, получим (с(и) — с(г), и — г) ) О. Монотон- 2Т2 ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА )ГЛ. Ь ность дУ установлена. Далее, пусть о <и ИУ, (оь)-+ о, огж ИУ, пусть (сь)-+с, сьж дУ(ог). Это значит, что 1(и) — 1(оь) ) (сы и — огу при всех и <и И'.
Поскольку функция 1(и) непрерывна на И' (см. теорему 2А5), то, переходя к пределу в этом неравенстве при Уг ->- со, приходим неравенству (2). Это аначит, что с <и д1(о). Полунепрерывность сверху отображения д1 доиааана. Наконец, возьмем произвольное ограниченное замкнутое множество ПсИ'. Поскольку И' — открытое множество, то все точки П являются внутренними для И' и поэтому найдется такое число 6 ) О, что ограниченное замкнутое множество (Уь = (и <и е5ч )и — о) < 6, о ж (У), представляющее собой 6-раздутие множества П, принадлежит И'. В самом деле, если И'= Е", то Пь с Е" при любом 6) О. Если же И'чь Е", то граница Гр И' выпуклого множества И' непуста н р(о, Гр И') = >п1 ( о — ю) > 0 при всех о ьи (У. В силу леммы 2.1.2 функция иы ГР >У Р(о, Гр И') непрерывна на компактном мнол<естве (У и согласно теореме 2.1.1 найдется такая точка ог щ П, что !В( Р (о, ГР Иг) - Р (ог, ГР Иг) = емп 26 > О.
Это значит, что (Уь <: И'. Функция 1(и) непрерывна на компактном множестве УУь, поэтому гир 1 (и) = УЬ < со. пь Возьмем любые о ж П, с ж дУ(о). В неравенстве (2) положим и = о+ + бс>)с) с (Уь с И'. Получим ( с) ((1 (о+ бе)) с)) — 1 (о))/6 < 21~/6=М< со для всех сж дУ(о), о<и П. Таким образом, зир впр (с(= сар (с)( оы и спице) еыдз<п) < М < со, т. е. множество дУ(П) ограничено.
Докажем замкнутость д1(П). Пусть (са)-<-с (сещ д1((У)). Это аначит, что существует такая точка вью ы П, что сь щ дУ(ог) Поскольку УУ вЂ” компактное множество, то без ограничения общности можем считать, что (оь) -ь- о с П. В силу полуиепрерывности сверху отображения д1 тогда с<и дУ(о) сд1((У). Следовательно, д1(У)— замкнутое множество, Компактность отображения дУ установлена.
Отметим, что субднфференцнальное отображение дУ, вообще говоря, не является полунепрерывным снизу. Например, функция 1(и) = )и(, аж ж И' = Е', имеет субдифференциал дУ(0) = ( — 1, 1), но точки с щ ( — 1, 1) щ ьп дУ(0) не могут быть получены как предел какой-либо последовательности (сг), сь ж д1(ог), где оь Ф О, У< = 1, 2, ..., (оь) ->-0. Испольауя компактность отображения дУ, нетрудно получить обобщение теоремы 1.8.3 на многомерный случай.
Те о р е ма 6. Пусть 1(и) — выпуклая функция на открытом выпуклом множестве Ит иг Е". Тогда на любом ограниченном множестве 6 с ИУ функция 1(и) удовлетворяет условию Лип<ница т. е. существует такая постоянная Ь = Х (6) ) О, что (1(и) — 1(о) ) ( Ь(и — о), и, о я 6. Доказательство. Возьмем П = со 6 — это выпуклая оболочка аамыкания множества 6. В силу теоремы 1.8 П вЂ” выпуклое компактное множество (У с И'. Тогда 1(и) — 1(о) ) (с(о), и — о) ) — Ци — о( (и, о <и П), где Ь =зир ) с( < оо в силу теоремы 5. Поменяв здесь и, о местами, имев><Э) ем 1(о) — 1(и) ) — Е) и — о) (и, о <и (У), Отсюда следует утверждение теоремы. Для получения интересных экстремальных свойств субдифферевциального отображения нам понадобится Т е о р е м а 7.
Пусть И' — открытое множество ив Е", многозначные отображения А и В< Ит->-П(Е") таковы, что А полунеярерывно сверху и комиактно, В монотонно, причем А (и) () В(и) ~ ЕУ при всех и ~ ИУ. Тогда со (В(и) с со А(и) (и ж Ит). Доказательство.
Зафиксируем любые иж И' и е<иЕ" ((е) = 1). Поскольку И' — открытое множество, то Ю = (о <иЕ: )о — и( < ег) с И' прн некотором зь ) О. Воаьмем последовательность (еь) -+0 (О < еь < е,). уз) СУНРРАДИННТ. СУБДИФФИРКНЦИАЛ 213 Тогда ог = и + сое с Я с И', (оо) -ь и. По условию существуют аь он А (оь) О 0 В(оь). В силу монотонности В для всех Ь он В(и) имеем (аь — Ь, оь — и) =<аь — Ь, еое>) 0 или <аь — Ь, е>) О.
Поскольку отображение А компактно, то множество А(Я) является компактным. Поатому, учитывая вклгоченио ага А(оь) сА(Я), можем считать, что (аь) -+ао. В силу полунепрерывности сверху отображения А тогда ао щ А(и). Поэтому, переходя к пределу в неравенстве (аь — Ь, е))0, получаем (ао — Ь, е))0, или (в, Ь>~ <е, а ) < зпр (е, а) при всех Ь жВ(и). Отсюда зир (е, Ь>(~ аыл(н) Ьын(н) эир <е, а>, и требуемое утверждение следует из теоремы 4.6.
ам А(и) Теорема 8. Пусть 1(и) — вьопуклая функция но открытом выпуклом множестве Ит ие Е", пусть Ро Ит-ьП(Ео) — какое-либо многоеначное отображение. Тогда: а) если Р монотонно, дУ(и) ар(и) ири всех ион Ит, то ду(и) =Р(и) (и ж И'), т. е. субдифференциальное отображение максимально в классе монотонных отображений; б) если Р полунепрерывно сверху, выпукловначно и Р(и) с д1(и) нри всех и он Ит, то д1(и) = Р(и), т. е. субдифференциальное отображение минимально в классе полунепрерывкых сверху выпуклогначных отображений, Доказательство. В случае а), пользуясь теоремой 7 при А(и) = = дУ(и), В(и) = Р(и), получаем Р(и) с сор(и) с со д1(и) дУ(и), так что д1(и) Р(и) (аж И'). В случае б) в теореме 7 возьмем А(и) =Р(и), В(и) = дУ(и).
Нужно проверить компактность отображения Р. Пусть УУ— какой-либо компакт иа И". Из включения Р(и) о:д1(и) (ион уу) следует Р(П) с д1(П). В силу теоремы 5 множество дУ(П) компактно. Это значит, что его подмножество Р(П) ограничено. Далее, пусть (сь)-ьс(сьжР(П)). Тогда найдутся такие точки ивом П, что сь он Р(иь) (Ь = 1, 2, ...).
В силу компактности П можем считать, что (ио)-ьи ж П. Из полунепрерывности сверху отображения Р следует, что с он Р(и) с Р(П), т. е. Р(П) замкнуто. Компактность Р установлена. В частности, взяв здесь одноточечный компакт П= (и), ааключим, что Р(и)— компактное, т.
е. ограниченное и замкнутое множество при каждом и он И'. Отсюда и иэ теорем 1.5, 1.8 с учетом выпуклости Р(и) имеем равенство со Р(и) = Р(и). Иа теоремы 7 теперь получаем со д1(и) = д1(и) с со Р(и) = =Р(и) (иж П). Отсюда и иэ включения Р(и) с дУ(и) (ищИ() следует утверждение б) теоремы. 7. Субдифференциал для выпуклых функций играет роль, аналогичную той, какую играет градиент для дифференцируемых функций.
Как для работы с градиентами полезно иметь некоторый набор правил дифференцирования, так и для работы с субдифференциаламн нужно иметь некоторые правила субдифференцирования. Предлагаем читателю самостоятельно доказать следующие правила субдифференцирования 1 — 4: 1. Если у(и) = 1(и+ ио), то дэ (и) = дУ(и+ ио). 2. Если у(и) = ЛУ(и) (Л ) 0), то ду(и) = ЛдУ(и). 3. Если у(и) = У(Ли), то ду(и) = Лд!(Ли). 4.
Если функция 1(и) выпукла на Е, а А — матрица порядка п >( п, л)е(А Ф О, Ь (н Е", то функция у(и) =1(Аи+ Ь), и онЕ" вып кла на Е" п ичем У р ду(и) = Атд1(о) ]о лчеь. 5. Справедлива следующая теорема [21], обобщающая известную теорему о проиаводной сложной функции. Теорема 9. Пусть Уо(и), ... 1 (и) — выиуклые функцию определенные на открытом выпуклом множестве И' ив Е", функция ор(х) = = ц(х', ..., хн) — выпуклая функция на открытом выпуклом множестве Х мг Ен ирнчем 1(и) = (Уо(и), ..., Ун(и)) он Х при всех и ж Ит, ор(х) моно- ~ГЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
