Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 46
Текст из файла (страница 46)
Согласно определению 10 тогда существует такое з >О, что О(о, а)г!аПХ = О(о, з)г!аПХ сХ с Х. Это значит, что ее и Х. Следовательно, г! Х с и' Х. Докажем обратное включение. Возьмем ю е г! Х. Тогда существует такое е > О, что О(ю, з) г|аПХ с Х. Возьмем какую-либо точку о е и' Х и положим ш = ю + Л (ю — о), Л е и. Поскольку о, ю е е аПХ = аПХ, то юл е а~Х при всех Л е Н. Кроме того, существует такое Ло > О, что шл е Е О(ю, з) дла всех Л, ]Л] < Ла.
Следовательно, юх Е О(ю, з)Пап Х С Х, ]Л] < Ло. Из выРажениа для юл следует, что ю = юл+ 1 — Л (а — юл ). При 0 < Л < Ло имеем а = 1 — Л е (О, 1). Согласно Л Л т+Л Л Г+ Л теореме ! 1 тогда ю е и' Х. Это значит, что и' Х с г1 Х. Тем самым установлено, что г«Х = г! Х. Далее, так как и' Х с Х, то и' Х с Х. Возьмем любую тачку а е Х и о е и' Х. По теореме 11 и =и+а(о — а) е г! Х при всех а е(0, 1], причем а — «а при ««-«О.
Следовательно, аег|Х. Это значит, что Х С г! Х. Таким образом, показано, что Х = г! Х. Гз Некоторые другие свойства выпуклых множеств будут рассмотрены ниже. 1. Пусть Х вЂ” некоторое множества из Е", Х вЂ” замыкание множества Х. Если Х выпукло, то можно ли утверждать, что Х также выпукло? 2. Существует ли невыпуклое множество, удалив из которого одну точку (или несколько точек), можно получить выпуклое множество? Рассмотреть пример Х = (и = (х, у) е Е : х ) 2. > О, у > О, х-1-у < 1) О ((О, 1)) О ((1,0)), 3. Покааать, что равенство и' Х = и' Х для невыпуклых множеств, вообще говоря, неверно (рассмотреть круг с выколотым центром).
4. Доказать, чта если А С В, то А с В, !п1 А с!п1 В, но, вообще говоря, не будет включения и'А с и' В даже для выпунлых А и В. Рассмотреть пример  — куб в Е, А — одна из его з граней. б. Если А — выпуклое множество из Еь, то аПА = аП(г! А). Доказать. 6. Доказать, чта размерность выпуклого множества Х совпадает с максимальной размер- ностью симплексов, содерхсащихся в Х. 7. Если А,  — выпуклые множества из Е", то А+ В с А+ В, г! А+ и'В = п(А + В), г!(ЛА) = Л Н А для любых действительных чисел Л.
Доказать. 3. Доказать, что если А,  — выпуклые множества из Е", г! А гт и' В ф мг, то г! А гт и' В = = п(А гт В). Существенно ли здесь требование и! А г| г! В зз и]? Рассмотреть пример А =(а = =(ху)СЕ2: х)0), В =(а=(ау)СЕ2: я<0). 9. Если Х вЂ” открытое множество, то со Х открыто. Доказать. 10. Доказать, что со(А + В) = со А + со В. П. Доказать, чта со Х = соХ, где соХ вЂ” пересечение всех выпуклых замкнутых множеств, содержащих Х. 12, Доказать, что вершины аа, и|,..., и и«-мерного симплекса Я = Вч,(а„«а!,..., а,„) являются его угловыми точками (см.
определения К 3.2.1). 13. Доказать, что аффинная оболочка множества Х состоит из точек вида а,а,+...+а а, при всевозможных и!,...,а ЕХ, а,. — действительные числа, « =1,...,т, а! Ч-, ..ла = 1, т и только из них. 14. Пусть А,  — выпуклые замкнутые множества из Еь, причем хотя бы одна из них ограничено. Доказать, что тогда А +  — выпуклое замкнутое мне«кество. Будет ли А + В замкнутым, если А, В не ограничены? Рассмотреть паимеры; а) А = (а = (х, у) Е Ез: у = О), В = (Ь = (х, у) Е Е: у < е ); б) множества А, В из рис. 4.14; в) А =(а=(х,у,х)еЕЗ: х=я=о,у<0), В=(Ь=(х,у,л)еЕ~: х +уз <2уз,у>0).
1. В главе 1 были рассмотрены некоторые свойства выпуклых функций одной переменной. Здесь мы продолжим изучение свойств выпуклых функций многих переменных, Определение 1. Функция у(х), определенная на выпуклом множестве Х, называется выпуклой на атом множестве, если ,((сгы + (1 — сз)п) < сгХ(и) + (1 — сг) Т(п) при всех ы, э е Х, всех сх, О < сх < 1. Если в (1) при ы фи равенство возможно только при сх =О и сх =1, то функция Т(х) называется строго выпуклой на Х. Функцию У(х) называют вогнутой )строго вогнутой) на выпуклом множестве Х, если ( — у(х)) выпукла )строго выпукла) на Х. Если множество Х пусто илн состоит из одной точки, то функцию на таком множестве нам будет удобно считать выпуклой (или вогнутой) по определени!о.
Подчеркнем также, что всюду, если не оговорено противное, будем рассматривать лишь функции, принимающие конечные значения во всех точках области определения, Примерами выпуклой функции на всем пространстве Е" служат линейная функция У(х) = (с, х) и норма Г(х) = ]х~. Кстати, линейная функция у'(х) = (с,х) одновременно является и вогнутой на Е", В теореме 1.5 было показано, что выпуклое множество Х содержит выпуклые комбинации ~; сг«ыг, сг,. > О, з = 1,...,тп, 2; сг! = 1,любых своих «' = ! «=! точек и„..., ыш при любых т = 2,3,... Пользуясь индукцией по той же схеме, какая была использована ппи доказательстве теоремы 1.5, нетрудно показать, что для любой выпуклои функции У(х) на выпуклом множестве имеет место неравенство ]тгнсгна ,Т(~ ц,.х,.) < 2; сг,,Т(х«) (2) для любых из ее], 2,..., любых х! аХ, и! > О, 2 = 1,..., пь, ~;сг,.
= 1. г=! 2. Как и в случае выпуклых функций одной переменной, выпуклые функции многих переменных на выпуклом множестве не'могут иметь локальных минимумов. Точнее, верна Теорема 1. ?Тусть Х вЂ” выпуклое множество, а функция т'(х) определена и выпукла на Х. Тогда всякая точки локального минимума 160 Гк 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 161 $2. ВЫПУКЛЫЕ ФУНКЦИИ ,Г(х) одновременно является точкой ег глобального минимума на Х, причем множество Х, = (х: х е Х Г(х) =~, = !и! Г(и)) выпукло. Если Г'(х) строго выпукла на Х, то Х„содержит не более одной точки. Доказательство.
Пусть и, — точка локального минимума функции У(х) на множестве Х. Это значит, что существует окрестность О(и„, е) = = (и:[и — и„~ ( е) точки и, такая, что у(и,) ( Г(е) для всех е Е О(и., е) П Г!Х. Возьмем произвольную точку х Е Х и число о > О, столь малое, что о]х — и„[ < г. Тогда и„+ а(х — и,) Е О(и„г) П Х, и с учетом выпуклости функций у(х) имеем Яи.) < у(и„+ а(х — и,)) ~( у(и.)+ а(Г(х) — у(и,)) или 0 < о(у(х) — у(и,)). Сокращая на ср > О, отсюда получаем Г(х) > у(и) при любом х Е Х. Следовательно, и, Е Х,.
Пусть теперь и, е Е Х„т. е, у(и) =Г(е) =Г„и, е ~ Х. Тогда Г"„< Г (ои + (1 — о)е) ( оГ(и) + (1 — о)!'(е) = у„(3) т. е. Г(ои+ (1 — о)е) = Г„при всех о, 0 < о < 1. Следовательно, аи+ (!в — о)е Е Х„О < ср ( 1. Выпуклость Х. доказана. Если и ~ е, то для строго выпуклых функций неравенства (3) не могут обратиться в равенства при 0 ( а < 1.
Следовательно, строго выпуклая функция может достигать своей нижней грани на выпуклом множестве не более чем в одной точке. П Примеры 1.11.1, 1.11.3-1.11.5 показывают, что у выпуклых функций множество Х„может быть пустым, может содержать одну или бесконечно много точек. 3. Далее, остановимся на одном характеристическом свойстве гладких выпуклых функций. Т е о р е м а 2. Пусть Х вЂ” вьтуклое множество.
Если функция Г(х) выпукла на Х и дифференцируема в точке е Е Х, то У(и) > У(е) + (У'(е), и — е) Чи Е Х. (4) Если,Г(х) е С'(Х), то у(х) выпукла на Х тогда и только тогда, когда неравенство (4) вьтолняется при всех и, е Е Х. Доказательство. Необходимость. ПустьЯх) выпукла на Х и дифференцируема в точке е Е Х. Перепишем неравенство (1) в виде ,!'(е + о(и — е)) — Г(е) ( срЦ(и) — Г(е)) Чо Е [О, 1], Чи, е й Х. С учетом дифференцируемости у(х) в точке е отсюда имеем (у'(е), ср(и — е)) + о(о[и — е!) < а(Г(и) — 1(е)) Деля обе части этого неравенства на о > 0 и устремляя а — +О, получим неравенство (4).
Если Г'(х) е С'(Х), то неравенство (4) верно для всех и, е Е Х. Достаточность. Пусть Г(х)е С'(Х), Х вЂ” выпуклое множество и пусть неравенство (4) выполняется при всех и, е Е Х. Покажем, что тогда у(х) выпукла на Х. Возьмем произвольные точки и, е Е Х и число а, 0'< ( о < 1. !1оложим и, = аи + (1 — а)е. Из (4) получим ,! (и) — 1'(и ) > (~'(и,), и — и ), Г(е) — ~(и ) > (Г'(и„), е — и„).
Умножим первое из этих неравенств на а, а второе — на 1 — рх и сложим. Получим ср!'(и)+(! — а)~(е) — ! (и ) > (!"'(и„), и — и ) =О, что равносильно неравенству (1). П Неравенство (4) имеет простой геометрический смысл. Как известно [327; 350; 352; 534], гиперплоскость Г = ((и, Т) е Ь"+ '. и е Я , Т = Г(е) + + (Г'(е),и — е)) является касательной плоскостью к графику функции Т = Г(х) в точке е. Поэтому неравенство (4) означает, что график выпуклой функции лежит не ниже касательной плоскости к этому графику в любой точке е е Х, в которой существует производная Г"'(е) (ср. с теоремой 1.8.4). 4. Следующая теорема, называемая критерием оптимальности для выпуклых функций, дает необходимое и достаточное условие минимума гладких функций на выпуклом множестве.
Т е о р е м а 3. Пусть Х вЂ” выпуклое множество, Մ— множество точек минимума функции У(х) на Х. Если в точке х, е Х„функция У'(х) диффгренцируема, то необходимо выполняется неравенство в ц 2 или й ' Г"''' б Ф и Васррьев (Г'(х,),х — х,) >О !ГхЕХ, (5) 0( (!'(х,), х — х.) + о(а)/о, Чх Е Х, !Уо Е (О, 1].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
