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