В.А. Ильин, Э.Г. Позняк - Основы математического анализа (DJVU) (1108889), страница 115
Текст из файла (страница 115)
Полученное противоречие доказывает, что наше предположение о том, что функция «(х) имеет локальный минимум в двух различных точках множества ф является оп<ибочным. Теорема доказана. Существование локального минимума докажем при более сильных ограничениях, чем единственность. Теорема (о существовании локальногв минимума у сильно выпуклой функции). Если функция «(х) сильно вкм ВУкло, иа замкаолтпм ныпйклом мноэкхестне <,л, то У этой <«)лу>лкц<л<л су<цестаует на множестве бь> точка хо м>кол)о!ого м<лкилмумо ). ,4 О к а 3 ат <эл ь с т в О.
Сна>ала, отм<этим, чло тео1н>м>! заве- ЛОмо с!0)ав<>дг1иВВ для <211 1ая, ко!.да ВЬП11 к>10е за)1кнуто<1 х1НО- жество <> является, кроме тон>, о г р а н и ч е н н ы м. Тогда по второй теореме ВР!<Врштрасса (см. теорему 14.7) функция «(х), будучи во Всяком с. <учае непрерывной на множестве Я, достнга- РТ В НРКОТОРОЙ ТО'1КР 2'о ЗТОГО МНОЖР<'Тва СВОЕГО МИНИМЙЛЬНОГО на б~ значения. ) казанная то'1ка хо и яВляется точкой локального минин> ма. ) !ак как сильно выпУклаЯ на выпУклом множестве бт> фУнкциЯ «(2) является строго выпуклой на этом множестве, то ло предыдугией теореме точка хе бУцет е Л и н с т в е н н о и точкой локального мннимУма. 17 ГГйДИКИтИЫй МКтОД ПОИОКЛ ИКОТГКМьгый 555 Остается доказать теорему в случае, когда выпуклое замкнутоехсножествоб) не является ограниченным.
Фиксируем некоторую внутреннюю точку х| множества с,) и разложим функцшо т(х) по формуле Тейлора с центром в точке х|, взяв ос:|"|точный |лс'.н Лв(:х) в фораге „'1азр)знжа ) (см. п. 3 ч 5 гл. 14). Указанное разложение будет иметь вид 1 (сг) = )'(х) ) + с)('()х) ) + — Й 1" (дз) + О(х — х| )) „(14.111) гле Π— число из |гптервала О ( О ( 1, так что точка х| + 0(х — х| ) принадлежит отрезку, соединяю|нему точки х| и х ). Ест))| обозна тить с.')х вектор х — х|, то для с)Г" (сх|) будет справедливо равенство; с(((х|) = (угас( 1(х|), Ьх).
Из этОГО раве|и:|Ва вытекает,что ~с1) (х) ) ! ( ( дас( ~(х) ) ( )Ьх!. (14. 112) Далее, используя левое неравенство в определении с)гьчьной выпуклости (14.104). мы придем к неравенству сР 7'[х) + 0(х — х| )1 > А | . ()')х)з. (14.113) Из соотпюшенпй (14.111) — (14.113) заключаем. что )(х) — 1(хз) > — ф(хз))+ -с1 1(х) + 0(х — х|)1 > > — ( нгас( 1(х|) ! (,л)з / + —,' (Ьх(~, так что ,) (сх) — З(сх)) > (|зх( [ — '(Ьз( — ~ огас( )(хз)~1 . (14.114) Учитывая, что то |ка х| фиксирована и величина (рас( ((х))) представляет собой некоторое фикс.гсрованное число, мы заведомо можем выбрать положительное число Л настолько большим, чтобы при /Ьх! > Л выражение в квадратных скобках в (14.114) было положительныа|. ) Зиы у |итываем, что сильно выпуклая на множестве СС функция 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ЬНОс!И (Хт,) К ХС) В силу определения ттеттрерьтвнс>с>тн функцшл вытекает сходимость нос)тсдовагсльностн (! (Сгь)) к *псе )У т'(>го). ТВК как асс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
