Ильин_ Позняк - Основы математичемкого анализа. Часть 1 (1111798), страница 117
Текст из файла (страница 117)
) Зиы у |итываем, что сильно выпуклая на множестве СС функция 7"(т) два раза дифференцируема на этом множестве. )) Какова бы нн была точка .г множества Сз), отрезок, сослана ююнй точки т) и х), принадлежит множеству Сз) в силу выпуклости этого множества. В сноске к теореме тейлора 14.15 отмечалос|ь что в качестве окрестности центра разложения можно брать любун) звездную окрестность этого центра„ т. е. можно брать все множество С).
556 Г:!. 1! еь нкции нискольких пигиминных Это О)начает. что прн (»1(х( ) 1( справедливо н(',равенство г(х) > 1(х(), т. е. всюду вне замкнутого шара Сп радиуса Л ( центром в точке х| значення Г(х) превосходят значешн; ~(х~) (в пентре указанного шара). Обозначпм СЭ!» Пересечение множества бь> с указанным шаром Сн. Так как оба множества 6> и Сп явля|отея вьшуклымп и замкн)'тымн, тО н их пересе 1епи(' (~>!» такж(1 яВля('.т('я Вып|'к.|ым и замкну Гым.
Так как., кроме того, мне>Нес|ВО Щ» являеп)я Ограниченным, то по док|юанному вьппе функция ) (х) имеет на множестве с)п сдпнствснную точку:|о локального мияимума. Поскольку мы Показа;ш, что во всех точках ф лежащих за пределами»~»!», значения 1((г) превосходят 1(х!), то чтп значе- ниЯ тем б(шее пРсвосхоД)п 1'(:го), т. е. точка т:о ЯвлаетсЯ точкой локального минимума » (х) н на всем множестве Я~.
Теорема полностью доказана. 3. Поиск минимума сильно выпуклой функции. 14ы доказали, по сильно выпуклая функция )((г), заданная на замкпхтом Выпрклом м1И)>кестве ьг', име()т на атом мнО>к('.стВО еДинственнУК> то |кУ хо локального минимУма. Обратимся к построенню и обоснованию алгоритма. с помо- ЩЬ|О КОТОРОГО ОТЬН:КНВВ((ТСЯ Э1а ТОЧКВ,:Го. Фиксируем пронзвольнук) точку х! Множества») и произво.тьнос чисто о.
улов.тетворяющее неравенствам 0 < (х ( 2,»ь)г) (14.115) где У». постоянная из неравенства (14.104), опр(деляющего сильную выпуклость функпии 1(х). Отправляясь от х| как от первого приближения, составим ит(.Р|щионную !нх чецоват(тлы!Ость (хь) с п(п!О|ць1О Р()кУРРен1- ного с(ютношения хье| = Рс)(хь — (16гас) ~(хв)), к = 1,2,... (14.116) В настоящем пункте мы дока>кем с;и'.ду(ощее утверждение. Основ)(ая теорема. »|(»Оп)( (()унк()ия > (:г) яоллстея, виляя(о выпуклой на замкнутом выпуклом мно(ясетпве Я~> и пуст»ь хч произвольная |почка мноок>есп)ва 6>. Тогда ап(врационная последова|пельтн:ть (х|), определяемая рекуррентнь(м соотношением (14.116) при любом о, удовлетворя|о»нем нераоенхтвал( (14.115), сходи|воя к точке .Го локольног»> минимума фу)скопи.
У(х) Подчеркнем, что нта теорема дает алгоритм отыскания любо- 10 (Вп>тр()нп('.ГО илп кргн|ВОГО) лОк(М1ьнОГО м1шимума функции 1" (;г). являющейся сильно выпуклой на произвольном (не обяза; Т()ЛЬПО ОГРЗНП'П»ПНОМ) ЗНМКНГТОМ ВЫПУКЛ(пь! МНО>К(К:ТВЕ 17 гглдикнтный мктод поиска экотнкмммл 557 Доказателы:тву основной теорсмы сс1юдпошлем сетыре леммы.
Лемма 4. Если С1 — выпуклое. заллкнутое множество точек Е"', х - произвольнсся фиксированная точка, Ет, а у прослзвольная тстчка счс, то (14.117) ( ' — Рсг(х); у — Рс1(х)) < О. Д о к а з а т е л ь с т в о. Предположим, что неравенство (14.117) несправедливо. Тогда существует точка у множества Я такая.что (х — Рд(.'с), у — РО(х)) ) О. (14.118) Из (14.118) сразу же вытекает, что точка у не совпадает с Рсс(х).
В силу выпуклости множества С1 лн>бая точка з = Рд(х) + +1(у — Ро(х)) отрезка, соединяющего точки Р~(сг) н у, принадлежит множеству сч. Вычщлим расстояние между любой такосй точкой в и точкой х ра(, х) = (х — Рс1( ') — РЬу — РЫх)),: — Ра(сс) — 1(у — Ра(х))) = = ра(хц Рс1( с)) — 21(х — Ро(х), у — Р1(сг)) +1 р (у., Рс7(х)). (14.119) Так как х и у фиксированы, а 1 -- любое чисто из сегмента О < 1 < 1, то в силу неравенства (14.118) можно взять 1 удовлетворя ющим неравенству О с З(' — РО(х) ! — 1'О(х)) Р2 (у, Ро (х) ) При такоъс выборе 1 — 91(.' — Ро (и) . у — Ро (сс ) ) + 1а ра (у, Ро (х ) ) < О, и мы пол1чим из (14.119), что р~(з,х) < р (х,РО(х)).
Последнее неравенство противоречит тоъсу, что точка Рс~(х) является ссроекпиесс то ски х на ксножск:тво с„с 1 ьсс«сжс1ства С~ ссалслассь гочка з, удаленная от х меньпн., чем Рс~(х) от х. Полученное противоречие заверспает доказательство леммы. Лемма $. Пуспсь 1(х) с1ссЯерессцссруема и вынул ла аа зомкнутсглл въяуклом мссогиссстссс Се. Если при некотором положптельнолл о проекция, Рс1(хв — а 8гас) 7'(хв)) точки хв— — сс . Егас) ((ссо) на мпаясестоо Я совпадает с пючкой хо этого мьсожества. то функция 1(х) иллеепс в точке. хе локальнигй мщс илсум. Д о к а з а т е л ь с т в о.
Используя лемму 4, запишем неравенство (14.117) для точек х = хв — сс йгас(1(хо) и у = хо+ 558 г:!. !! ФУНКНИИ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ + Ьх, где 71я лн>бой вектор, для которого точка ст =:го+ !ах принадлежит С). П результате полу тим (хо — 0 . и!Вс(У(сс:о) — Рсз(хо — ст Кгас) У(>го)), хо+ !1х — Рс)(>го — о 8гас)1(хо))) < )1 Учитывая. что Рс>(>го — о нгас) т" (>го)) = хо., по.сучим ит последн!)го нс;раис-истаа с!)!с;дутошс)ст с;оотноптеписк (Кгас) 1(хо) сл:г) > !1. Это соотнснпение, справедливое для любого вектора !1х, для которого точка тс;о + слх принадлежит ф в силу леммы 3 устанавливает, ч10 ФУнкциЯ т" (7:) имстн1' в то ткс', хс) 1!Окольный а!Ннттхсух!.
Лемма 5 доказана. Предположим. что функция ! (Сс>) является сильно выпуклой на огрантсченнол! замкнутом выпуклом множестве ст. Обозначим гп мннимальное значен!Се т (х) на а!ноже!>тве ф В !с -- пи"10. строго болыпее тсс, так что р > ьн = шш 1(тс!). те О) Фиксируем чткло м. строго большее йк и обозначим Я подмножество тех точек тг множества С), для которых р < т(х) < м (14.120) Множество б> как подмножество ограниченного множс ства ~х) СВМО ЯВЛЯЕТС:Я ОГРВНИЧСЕННЫМ.
Убедимся в том, что множес:тво с) является з В м к н уПус:ть 1хь) —. Проис)воль!тая сходя!нинся постптдовательность точек множества © Требуется доказать, что предел тсо этой последовательности также принадлежит хппикеству © Так как каждая точка 7), принадлежит множеству © то для каждого !!ох!ера Й р <.!(Сгт;) < (14.121) Строго выпуклая функ!Сия у(сс>) во всяком случае непрерывна на Д. а поз10>ту ИЗ СХОЛИМС)СТИ ПОС''1РДОВВТР'1ЬНОс!И (Хт,) К ХС) В силу определения ттеттрерьтвнс>с>тн функцшл вытекает сходимость нос)тсдовагсльностн (! (Сгь)) к *псе )У т'(>го).
ТВК как асс. элехпнты сходя!цейс я ми!о!свой пес"и довательности ( ) (хь) ) бдс>в:и твс>- ряют неравенствам (14.121), то и предел ~'(>го) этой пос>ледовательностп удовлетворяет неравенствам сл < 1(хо) < м (см. гл, 3, ) Так как исходное множество О является замкнутым, то нрелел хе но всяком случае нринадлежят О.
г 7 гглдинитный мнтод поиски вкотгнмт мл 559 следствие 2 из теоремы 3.13)„ а зто и означает. что точка хц принял>ижит мио)кс)стВ1 (,1. Дс)казан)лы:1ВО замк1Г) тое1н мно- ЖСЮТВВ Сг' ЗВВЕРПШНО. Итак, хсножеетво б) Всех точек х из множества б), для кОторых справедливы нераве)п:тва (14.120), является замкнутым и ограниченным. Докажем теперь следующую лемму. Лемма 6. Прс>ссг)> Яуунл:ция 1(сх) с>слъно с>)яп)укла на ввтрклом замкнртом мнг>жегтве Щ х — лво>бая то >ка бУ. м — л)обс>е положительное члсело, еиллнол Ьх обозначаесп разьин>ть Ьх = Рд(х — сг р ас1 у(э>)) — х. (14.122) Тогда сприведлисн) нерас>енс>тс>сх (Огас( 1(х), Ьэ:) < — (,Ьх!. (14.
123) >оеэ)11 же. кРоме то>с>, мноэн;ествв Сч) вгРа)ихчеэи> и точка х пр>инадланент подмноэюевтвр б~з тех точек Я, для которых еправедлавьс неуювенвтвв (14.120) пра р > )п)пу(х), то наб- хнО де>пся. строго т>лоэкилтелии)ог сл>ело у такое, чп)в справедливо неравенвтвс> (14. 124) ~Ьх, '> у. Д о к а з а т е л ь е т в о. Докажем сначала неравенство (14.123). Фиксируем произвольну)о точку х множества бУ и. привлекая лемму 4, запишем неравенс:тво (14.117). взяв в нем вместо х точку х — О бгаду(х), а вместо 17 точку х. При атом полу шм неравенство (х — сг.рас(У(х) — Ро(х — о.бгас(У(х)),х — Рд(х — сюбгайу(х))) < О, которое е учетом обозначения Ьх = Рс)(х — О .
гас11'(х)) — х перепив)сггея в виде ( — О дгас()(х) — Ьэд — Ьх) < О. Из псктеднего неравенства и из свойств скалярного произведения вытекает, что о(нгас(>'(х). Ьх) + )Ьх)а < О, а зто и приводит к неравенству (14.123). Остается дока:)ать, что при дополнитс льном предположшпш о том, что С) ограничено и что:1: принадлежит подмножеству ф существует у > 0 такое, что с:праведливо неравенгтво (14.124).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
