Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 49
Текст из файла (страница 49)
Теорема 12. Пусть К», К»,... ..., К вЂ” ненустые выпуклые ко»»усы ив Е" (с вершиной в нуле), нусть К» П К» ()... П Кн = »21. Тоеда необходимо существуют векторы се, с», ..., свь не есе равные нулю,с»»и К» (» = О, 1, ..., ш), и такие, что (19) се+ с» +, ° + сы О. ОтделимОсть Вьгпуклых множестп у 5» Д о к а з а т е л ь с т в о.
Согласно теореме 7 существуют векторы сг, с<, ..., с, не все равные нулю, и числа (р, 7ь ..., 7, удовлетворяющие условиям (7) — (9). Воспользуемся тем, что рассматриваемые множества К„ Кь .,,, К,„лвллютсЯ именно конУсами, и покажем, что тогда Тг = 7< = ... = 7 = О. В самом деле, если (с», и) > 7, при всех и щ К<, то (с», )»и) > > "(, или (с», и» 7«)» для любых )» > 0 и и»и К<.
Отсюда при )» -++ 0 получим (со и) > 0 при всех и»н К», т. е. с» щ К< (» = О, 1, ..., ш). Кроме того, если и»м К», то, взяв в неравенстве (с<, и) >О вместо и точку Еи при малых 7» > О, получим сколь угодно малые значения функции (сь и> на К» и придем к равенству ш( (с», и) =О. Согласно (12) кып» зто означает, что все величины 7» (» = 1, ..., т), участвующие в неравенствах (7), равны нулю.
Из (13) тогда имеем Те — — О. Таким образом, если в теореме 7 множества Аг, А<, ..., А являются выпуклыми конусами, то условие (9) выполняется тривиально, так как все 7» = 0 (» = О, 1, ..., »и), условия (7) означают, что с»»н К» (» = О, 1, ..., т), а из (8) следует (19). При некоторых дополнительных ограничениях на конусы К„Кь ... , К теорема 12 обратима. А именно верна Теорема 13. Пусть Ке, К», ..., К,— непустые выпуклые конусы ив Е (с вершиной в нуле), пусть все гти конусы, кроме, быть может, однова, открыты, Тогда для тово чтобы Ке () К» ()...
() Кн = Е», необходимо и достаточно, чтобы существовали векторы сг, с», ..., свь не есе равные нулю, с<щК» (<=О, 1, ..., т), и такие, что (19) се + с» + ... + с О. Доказательство. Необходимость доказана в теореме 12. Достаточв ность вытекает из теоремы 8, если заметить, что условие с»»н К» равно. сильно неравенству (с», и) > О (и щ К»), и отсюда и из (19) следуют условия (7) — (9) при 7< = 7» = ..
° = Тн = О. Упражнения. 1. Пусть А и  — выпуклые множества, не имеющие общих внутренних точек. Можно ли утверждать, что А и В отделимы7 Рассмотреть пример А = (и = (х, у): у = О, )х) (1), В (и (х, у): х = О, < у) ( 1) в Е'. 2. Пусть Х вЂ” выпуклое множество из Е", 1п» Х = <о. Доказать, что любая гиперплоскостгч опорная к Х и проходящая через точку ужи'Х, содержит Х, т. е. не является собственно опорной.
3. Пусть А — выпуклое множество иа Е", причем АП (п» Еп+ — — 8. Доказать, что существует такой вектор с = (с», ..., с„) чв 0 (с, >О, ... ..., с„> 0), что (с, а) ( 0 при всех а»н А. 4. Пусть А — выпуклое множество из Е", М вЂ” аффинное или многогранное множество иа Е". Для того чтобы А и У< были собственно отделимы, необходимо и достаточно, чтобы д< 0 и'А = »<». Доказать. 5. Пусть р (А, В) = (п( ш1 ) а — Ь ) — расстояние между множест- аЫА 5<ИВ вами А и В. Доказать, что два непустых выпуклых множества А, В из Еь сильно отделимы тогда и только тогда, когда р(А, В) ) О. 6. Доказать, что всякое выпуклое замкнутое ограниченное множество из Е" имеет хотя бы одну угловую точку (см. определение 3.2.1). 7.
Пусть У вЂ” выпуклое замкнутое множество из Е". Доказат»Ь что У имеет хотя бы одну угловую точку тогда и только тогда, когда У не содержит прямых (см. пример 1.4). 8. Доказать, что выпуклое замкнутое ограниченное множество А из Еп является выпуклой оболочкой своих угловых точек. Показатьч что без требования ограниченности множества А зто утверждение неверно. Рассмотреть пример А = (а = (х, у)»н Еч: у ~ )! х)).
(ГЛ 1 элнмкнты Выпуклого АнАлизА 206 9. Если Аь ..., А — выпуклые множества из Е, причем П Н Аз ~(2(, 1=1 то г!( й А!1= й (г!Аг); аИ( й А,.1= й (аМА,) 9 6. Субградиеит. Субдиффереициал 1. Для выпуклых дифференцируемых функций па выпуклом множестве выше было доказано неравенство (см. теорему 2.2) У(и) ) Х(Р) + <У' (о), и — е> 11'и 1и П. (1) К сожаленнго, выпуклая функция может не быть днфференцируемой даже па внутренних точках множества, и в етом случае полезное во многих случаях неравенство (1) не будет иметь смысла. Тем не менее, оказывается, для выпуклых функций зто неравенство можно сохранить, если надлежащим образом обобщить понятие градиента. О предел ение 1. Пусть функция У(и) определена на множестве У из Е".
Вектор с = с(с) 1Н Е" называется субзрадиенгом функции 7(и) в точке и 1н <!, если у(в)» (е)+<с(е), — > 1Г ~(Г. (2) т т П А!=ПА;; 1=1 1=1 Доказать. 10. Пусть К вЂ” произвольный конус из Е". Доказать, что конус К*— замкнутый и выпуклый. 11. Доказать, что если К вЂ” выпуклый конус, то К* = (К)е. 12. Доказать, что если К вЂ” замкнутый выпуклый конус, то (Ке)* = К, 13. Пусть К вЂ” выпуклый конус. Доказать, что для ограниченности снизу линейной функции <с, и> на К необходимо и достаточно, чтобы с 1и К*.
14. Пусть К вЂ” выпуклый конус, штК чь Е!. Тогда <с, и> ) 0 для всех в ж шт К при любом выборе с 1и К* (с Ф 0). Доказать. 15. Доказать, что (К+ ... + К,„) = К П ... ПК,„, где Кь ..., К конусы из Е". 16. Пусть Кь Кз — выпуклые замкнутые конусы. Доказать, что (К,ПК,)'= К,*+К,". 17. Пусть К„КВ ..., ʄ— выпуклые конусы, пусть Кз П (птК, й ... ... П ш1К Фю.
Тогда ( П Кг) =К„+К + ... +Х . Доказать. ~!=С /т 1Ф 18. Пусть К„КВ ..., К вЂ” выпуклые конусы. Тогда либо ~ й Кг) з=е = Ке + К + ... +К„„ либо существуют не все равные нулю векторы сгш К,. (! = О, 1, ..., т) такие, что се+ с~+...+ с,„= О. Доказать. 19. Для того чтобы выпуклые конусы Ке, К, были неотделимы, необходимо и достаточно, чтобы 0 щ !В1(К1 — К~). Доказать. 20. Доказать, что два выпуклых конуса К„К, неотделимы тогда п только тогда, когда одновременно выполнены два условия: ПКе П г1К, чь З', В1а Ко + Тйп Кз = Е".
21. Множество Ае =(се Е": <с, и><1 ти1и А) называется полярен множества А. Найти поляры множеств А, если А = (0); А = [а, Ь] ш Е', А=(ияЕ": и=Се,О(1<ос, еФО); А=(иаЕ": <с, и>(7); А— шар; А — конус с веригиной в нуле. Выяснить связь между полярой конуса и двойственным конусом. суБГРАдикнт. супдиФФБРнициАл 207 о Рис. 4.18 1(и) — 1(0) = /и! > (с, и — 0) = (с, и), исмЕ", для всех с (!с! ~ 1). Это аначит, что д((и!) )„е = дУ(0) = (с ш Е": (с! (1) — единичный шар с центром в нуле. Если очи О, то дУ(о) = = (оУ)о! = У'( )). Заметим, что в примере 2 функция 1(и) = !и! выпукла на Е".
Оказывается, если совсем откачатьск от выпунлости функции, то даже гладкая функция может не иметь субграднента пи в одной точке. Например, для функции 1(и) = и' на Е' субдифференциал пуст во всех точках. В то нте время эта функция У(и) = и' па множестве (У = (ишЕ'. и >0) выпукла и во всех точках о ш П имеет на (У непустой субдифференциал.
Ниже увидим, что это не случайно. 2. Следующая теорема показывает, что понятия субградиента и субдифференциала являются естественными для выпуклых функций. Т е о р ем а 1. Пусть (У вЂ” открытое выпуклое множество но Е" (нопример, возможно, П=Е"). Тоедо для тово чтобы функция 1(и), определенноя но (У, имело непустой субдифференциол во всех тачках (У, необходимо и достаточно, чтобы У(и) была выпукло но П. Доказательство. Необходимость. Пусть для некоторой функции 1(и) субдифференциал дУ(и) чь И при всех и ш П, Покансем, что 1(и) выпукла на П. Возьмем произвольные и, о сп (У, а вм [О, 1! и положим и„= аи+ (1 — а) о.
Пусть с = с(ич) тп дУ(и„). Тогда 1(и) — 1(и„) > (с, и — ич), 1(о) — 1(ич) > (с, о — и„). э(ножество всех субградиептов функции У(и) в точке о называют субдифференциолом этой функции в точке о и обозначают через дУ(о). Неравенство (2) имеет простой геометрический смысл и оаначает, что график функции 7 = 1(и) (и ш П) в пространстве переменных (и, 7) лежит не ниже графика линейной функции 7 = 1(о) + (с(о), и — о) (и ш П), причем в точке и = о оба графика пересекаются (рпс. 4,18).
уч Для гладких выпуклых функций, как показывает неравенство (1), субдпфференциал непуст и градиенты этих функций являются их суб- -;сК градпентамн. Во внутренних точках множества гладкая функция, оказывается, других субградиентов, кроме градиента, иметь не может. В самом Ь (ч чч. тэ Поскольку У(и) ш С'((У), то 1(и) = = 1(о) + (У'(о), и — о)+ о(!и — о!) (иш П). Отсюда и нз (2) следует, что (1'(о) — с(о), и — о) > о(/и — о!) (и сп (У). Поскольку о вн 1пС П, то и = о — з(1'(о) — с(о)) еп (У при всех е (О ( е ( во). Подставив вту точку в предыдущее неравенство, получим — е!1'(о) — с(о) !' > о(е) (О < е ( ее). Деля на е > 0 и устремляя е-ь+ О, отсюда будем иметь — [У (о) — с(о) !' > > О, т. е. с(о) = 1'(о).
Тем самым показапо, что для гладкой выпуклой функции ду(о) = = (У'(о)) при всех о ш (пс (У. Существуют функции, которые недифференцируемы в точке, но тем не менее субдифференциал в этой точке непуст. Прим е р 1. Функция 1(и) = !у(и) ! (и ш П) в точке о, где у(о) = О, всегда имеет субградпент с(о) = О, так каи !у(и)! — !у(о)! = !у(и)! > > 0 = (О, и — о) для всех и ш (У. В то же время в точках о, где у(о) чь О, эта функция может быть недифференцируемой и не имеющей субградиента.
Пример 2. Пусть У(и) = !и! (и шЕ"), В точке о = 0 вта функция недпфференцируема, но для пее верно соотношение (ГЛ, З Злеыпнты ВыпуклОГО АнАлизА Умножим первое из зтих неравенств на и, второе на 1 — а и сложим, Получим п1(и) + (1 — а)1(о) — 1(ие) ~ ><с, ие — иа) = 0 при всех и, о щ У, сс еи [О, 1). Выпуклость 1(и) на У доказана.
Достаточность. Пусть 1(и) выпукла на открытом выпуклом множестве У. Пусть о — произвольная точка на У. Покажем, что д1(о) ~ ЕС, Возьмем некоторый единичный вектор е. Поскольку У вЂ” открытое множество, то о+ Се ж У при всех с (О < с < сг, Се ) 0). По теореме 2.14 существует производная г(1(о)/ое по направлению е. В пространстве Е +' переменных (и, т) введем два множества А = ((и, у) еи Е"+с: и ж У, у > Х (и)1, дХ (о) В = ((и, у) еи Еы+сс и = о+ Се, у = Х (о) + С вЂ”, 0 < С < С ~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
