В.А. Ильин, Э.Г. Позняк - Основы математического анализа (PDF) (1108896), страница 96
Текст из файла (страница 96)
6 § 4 гл.равна fраизведеН:Шf! fраизваднайнаправлению f;e {тара Пх на дл(gIadJ(xo),~,T)де е=~x:I~!I-( 4.105)О.а д и м ат ь.,'илv4, левая часТf (14. 05')функции j х) в тачке хо юI пхl этага f;e {тара:п!'де xo)l~xl~единичныи вектар в направлении(14.106)лu-X.Так как х(! являе! ся тачкай лакал !fюга l'fИНИI!fУI!fаj(x , та праИiваднаif ~:неаТРiщательна(Ta!iHee,i{Цif~x:ю любаму на fравлениюра ;на нулю в СЛУ!iае! еслвнутреннего. лО!{альнага эксfpel!fY:!fa,х(!-тачкаи неатрицател !на в случае,еi'ЛИ хо - тачка KpaeBafa лакальнаfа экстремума).Итаi{ праi;ая !iaCTb (14.
(6) (а патам\левая !iaCТf4,1051)неатрицательна. Неабхадимаi'ТЬ даказана.2) Д а с т а т а ч н а с т ь.любаfа вектара ~;T,катарага тачка хо~T принадлежит,справедлива неравенст!ю ( 4.1(5). lакажеl!f, !iTa тачка х(! я ;ляется та!!лакаеТ!нага минимума функции j х),Так как функция j(x) па уславию я ;ляется i;ыпуклаf на мна,жеi'тве Q, та ДЛif Лfобь!\тачек хl и Х2 этага мно.жеi'тва и+ifсла t ifЗ сеП!fеt 1 справедл iiЮ неравенства. llалагая в эта м неравеш'тве хl = Хо, Х2ХО + ~x, мажfepe fисать эта неравенства в виделюбага(11.9~!на!!!ОtП!)- f!!o'( 4.107)Считая хо и ~x фиксираванными, перейдем в неравеш'тве(14.к предеш Прif t --+ ОО.
Па апределению праи iiЮДнай па направлеНИff! (см.,6л. 11) предел fрИ tОО1) 13 неравенстве ( 1.105) берется С!iалярное произведение векторовgradf(:r:! и ~!, Опре!еление gradf(:r:! см, в п. 6 § 4 гл. 4.'faCTff (14 (7)оиз ,(Д( НffЮ, стоящеIiI\iв праfЮЙ 'f;lC fЯ410вс<ют fOШ<Р4105) и(1] 106) этот fредел неотр:vщателен Учитыв;ш, чтi i лева~l Ч;li ть(14, (7);;ШffСИТ от t,ШШУЧИIiпреlеле при --+шравеш'тва (14,107), ЧТi1+~,г)f- j(:r:o)Оllоследнее неравеш тво, справедливое дшl Ш1iбого вектора ~X,дЛЯ которого точка Хо~X ПРfflfадлеЖfП Q, дока; 1!Бает, 'fTOфункцияХ) имеет в точке ХО локальный минимум.
10статочfность дока;ана.Лемма33ЮЛНОСТЫ{i доказана.а м е ч а н и ео (е 'ffДНО, что длян е й1. Из fриведеННОf о нами доказателы'тваCf1 'faK когда то'н,а ХО Яf,ляется в уе нточкой множе,'тва,т. е. КОfда речь идет о внутреннемлокальном МИНИМ1 ' ме, в ФОРМ1 1 лировке леммы 3;нак ;? в неравенстве (lJ.10~!) можно заменить на знакалеммы=.е ч ае 2.При ДOf,а;ательстве неоБХОДffМОСТffмы ш ' и1 fюльзовали требоваНИ~l вьmуклости функции3f(x . ПоэтOfry ДOf,а;ательство неоБХОДffМОСТff проходит без (ребоваНИIl вьmуклости функции f(x). Иными 1 ' ловами, справедливо следующее уеж Д ее: 1СЛ!! фУНК:'Ц!! 11(х дU1ф-fфi П!1!'Цируе,м.п 'Н.п выnук:ло,м.и и,м.еет л,"!IУЛ'Ь !Ыйминиму,м. 60 6 !утрен!!ей (6 ?lJa1!И'Ч'Н,оu) то'Чк:е хо этоi'О .;\л'Н,о)i1любоi'О 11/к:тора ~x, длл к:, 'тор, '?О то'Чк:а хоQ.
справедлив{! н' равен! '!n!m= О(gIad,~x) ;? О].[(gIadllерейдем к ВОПр01 ' У о едиш ' твенности и о суще1 ' твовании точлокаЛf,1ЮГОMffI'Ia.Teopf1Ma (о ед 1iИiсmве1iносmu .лоnа.лъного м 'пн 'пмума усnрогофУ1iУ'fu,uu).фУНК:'Ц!!1 1х) 1luфферен'ЦируемаuCmpOi'O 6ыnук:ла но 6'Ы iУК:ЛО,м..;\л'Н,о)i1 !{'т6еQ.то оно,ножет 'и,!1{ет'Ь лок:аJ,'ЬНЫU ,н'ин'и Н.!!,Н. то.н·ьк:о в 1'cfHOU то'Чк:е это,м.'Н,он{'ества.ь с т в о.докаffMeeTЛОf,аЛЬffI'IИНИIiIУI1и ;Т,ч н ы х14.95)f(;r('о н,ах хlдля точекможно;а(Х2) ;десьа з лда условие ВЫПУКЛ01 ' ТИи Х2 множествах!Предположим.
что функцияД "1 Хt-14. (8)(хлюбое число и; се; мента ОJ\kH l~l В 1 ' ООТНОШ! нии (lJ.108) точкиffM нераf,еllСТfЮt1и 12 рол lМИ, мыЮ14. (9)[нихпрнно[рав;у,чаСТf,н;]правлению вектор;] х"х « ,111твеТСТВI нно вектора хlвз(с,ютвет< твен!в T11'fKeIfHI111"I'HH"(){'11 ,ак какнн\fY\Ia,точки хХ2)наи Х2 являются точками лок;]льто об,' т,,;];анныеfРОffЗЕ,щныенаffр;шлениюнеотрицате,'ТЬны, т. е.
пределы правых частей 14.НJR) 11 (14.НJ9)при t -+ ОО оба неОТРlщательны.Tat"обра;ом. из [ераЕенстр (14. ()8)(14. оч) в tределе+приОt+Омы получимЛХ2Соtюставленнелхl~ О,юследнихfлхl -[ера! енстрtриводtf'l.нию о ТОМ. что f хl) = ЛХ2Использ"раве! [С; во j (" ) =строгой выпуклости 14.96), что+t(:C2 -(12))]х ,) ~ О.нас'!им"tы<f(14.< <tля в с е х t из интервала Оt1.Неравенство 14.110) противоречит тому что функт~ияfхTO'fKe(в точt·:е :Сl + t(:C2 - :Сlмалом t к точке Хl, функт~ия f (х имеети\tеетмини''"вкак уго. [но близкой при;начение. меньшее;начения (;Тl)),Полученное противоречие доказывает, что наше пре шоложе-ние о том. что функцияи\}еет Лоt"аЛf,ныi.jf(1)различных точках множестваQ,ннндв\является ошибочным.доt·:а;ана.Существование локальногоl\ШНИМУl\Ia докажем при i'юлее..Теорема (о сущесmвова1iUU .лO'tш.лЪ1iого мииимума уси.
",ныхо!'Т)а l;fчеЮf'''Х,че,,1еДИНСТЕеННОС IIсu.лъ1iо выnуn.лоU фУ1inЦUU). Еслu фУН'К'ЦUЯ лх) сuльно 6ыnу'Кла на заJvt'Кн jmO.Jvt 6 ыlntj'КЛО.Jvt .Jvшожест6е Q, тоэтойфУН'К'ЦUUна .) f.НО:Ж:I:С!i!61'QmО"i'К1i хо ло'КаЛЬНО20MUHUMY·JvtaД о к а з а т е л ь с т в о. Сначала отметим. что ТI орема заведо\юсttравеДЛИffажестводляQ являетскча)}t<шдаfътttyt·:лое;а,,1[утоекроме того, о г р а н и ч е н н ы м.мноогда повторой теореме Вейерштрасса (см. теоремубудучи во всяt<о,}случае непреРЫВfЮЙ [а14. 7) функт~ия j( х),MHO)ffeCTBe Q. ДОСТИl'ает в некоторой точке хо этого множества своего МИНИl\IaЛЬНОГОна Q;на'fения.
у ·:а;анна)} точt·:а 1'о и )шл)}ется ТО'fКОЙ лоt·:ального l\ШНИМУl\Ia.1) Так как сильно выпуклая на выпуклом множестве Q функция f(x)jШ.,!ЯI· С"точю,рого ВЫfiУ1i.,Ю'"1 "а эбудетд"ред,р,555JCTaeI С>Iд' ,Кёга'IQто''I,теор,'сн еkЛl'да Ю"в л я е ткл' ,ео г р ач;амкну-н н ынекоторую внутреннюю точку Х1 мн, ,жестваt<Цf1Ю (:1:) п,i ,f,'iPMi ле ТеЙ'I' ,ра цеIJв »шглтато'шыijalтанжаУказаНН'i"14)1)иметь вилх) = Л Х 1где е-14.111число из интервала О< е < 1, так что точка Х1принадлежит отрезку, соединяю нему точки Х1 и ХЕсли оГюзначить д.х вектор хвеДЛf1ВОQ и раз-Х1)2).Х1.
то tля dJ(X1{'удет спраравенство:11), д.(= (gradИз cfТOl'O рю,еНСТI а ВIЛ екает, что.1 2выДалее, используя левое неравенство в опресклости (14. 1)4),ы tриде t 'нерю,енстр>[, лениисильной14.113 )И; СООТНО ненийЛХ)Л Х 1) ~.1 1)-(14.IdJ Х1 +заt<лючае\t.d 2 ЛХ 1+ е(х -~Ч'I ОХ1)] ~J( x 1)1 ·Iд.хlk1+ 2 1 д. х lтак что14.114Jу штывая, что точt<аt<сировartавеЛf1чt1ftа I gradпрес tставляет собой некоторое фиксированное числос мы заведоtю tЮ/ltемчтобы при Iд.хюложитеЛI,ное 'шсло> R выражение в кваRнаСТОЛltКО БОЛЫТТf1[ратных скобках в,14.114;было положительным.1) ?\Iы с,читывае"" чJсильно ''"сс""клаtJ н" множесп",сша разаtJIффереНЕируема на этом мно:жествес:"2) Какова бы ни была точка х множества Q, отрезок, сое, tJIняющий точкии Ti:, "рииадле,t,итву Q в,'"ссшукл"стивас Всноске к теореме Теikлоратра ра,с,южеН,t с"т.14.15,с,южно БР"JЬ:с,южно БР:tс JЬ всеотмечалось с что в качестве окрестности "ен,ве,диую "крести ,сп,с этого цеНJр,tс.[них~?TO iiзна'Iaf~'IJ(:C)>),Ч'If\с [рав!т, е, в( ЮД!BHi'T~' нтр()м В Т()ЧI<;Г хl ЗН!iЧi'НИЯтттар!,ryT()riiJ(x)преВОСXiiцентре yt,:азаННii,о IШlра)01 ,! iзначим QR пере(ечение множе( ва Q с указ!шным шарО!' СП' TiK K!iK iiбаiiiже(Iта QСП iШЛifЮТ(Я ВI,ШУКЛI,i!ШИ замкнутымк то и их пересечение Qп также является выпукЛЫ!':а\fКН!ТЫМ.
Так как f<pO\fe Т01'О, !ШОiIiеСТIЮ Qп iШЛifетсяограниченным, то по юказанному выше функт~ияMHo;rieCTBeПоскольк!fC'IBeI шую ТОЧf<УДОf<а:али, 'ITO воед jf!fЫJ(x)имеет на!fY\Ia.лока,ff,НOl'ОвсехTO'IKax Q,Jлежащнх запре, fелами Qзначения J( х) превосходятхl), ТО эти значения тем более превосходят ji'!{i), т. е. ТОЧi<аявляется точкойлокального МИНИМУ"Ia (х) и на всем множестве Q.
Теорема полJность(tДОi<а:ана.3, Поиск минимума сильно выпуклой функции. Мыдоказали. что сильно выпуклая ФУНКi)ИЯх . за, iанная на заМКН!ТО!1выпyt<ЛО!1J!fHO;riecTEe (!,И\fеетна!ТО!1!fножествее iинственную точку ха локального минимума.06ратимся к построению и обоснованию алгоритма, с помокоторо;о отыс<iшаеТCifФикснруе!1 прои:вольн!I <а :СО.TO'IK! i'l MHo;rieCTBaэта ТО'ивольное число СУ, удовлетворяющее неравенствам(14. 15)1'де h:2 - ПОСТOiшнаif(еравенствасильную выпуклость ФУНКТ~ИИ (х ) .J(14.
04),опредеШfi tще,оОтправляясь от хl как от первого приближения, составимитерационную последовательность{:CI,,}с помощьюpei<yppeHT-ного соотношения(14.116)в настоящем пункте мыюкажем СЛi' iующее УТВi'рЖ ii'ние.Основная теорема. ПУС!i!Ь фу'!!'Х:'ЦuяJ( х)является сuлы-tовъmу-клой на за.Nl-кнутом въmу-клом множествеu пустьnроuзвольная тО'i-ка ,(f'!-tожеС!i!ваТогда uтершцuонная послеQ.довательностьЮМ'}, Оnf!еделяемая !!е-кm !!eHmHъt.Nl соотноше{14.116 )nри любо,(!HipiiBeHC пва,(!(14.115),с:содuтсяЛХ).i iодчеркнем,что эта теорема дает алгоритм отыскания ЛЮ('0-f( х)~Н~в~~:~:~~с='~7I~~~~е:~~~~к~~~а.~:н~~~и~:~~~,~jома (2~j'~~iзИа~тельно ограниченном) замкнутом выпуклом множествеQ.557Дiiii1iaTeo fЬCTB\осн,if'Hii'* Ti'iipe\iпреДПi iтттле\i чеf ыре ле\f~ЫоЛемма.че'J(;Еел'/},QпоеМ'J-lо:жеетпо,Т!о!юuаНОЛ'hiHOJ/,'h'J-lая то io'J(,aQотo~ато14.1171д о к а з ае л ь с то.
ПреДfЮiЮifoi,'fTO нерariеНСТfЮогда существует точка у множества Q14.11 7) несправедливо.Taiia [, 'fTO14.118 )Иiсра 'у же.1fiblTeKaeT, ifTO+ t(yлежит множествуточкойQ.(:С)не соп адает слюГ!ая точка Z =Вычислим расстояние меж [у любой такой-= Р (Х, PQ(X)Х-- PCJ(i) PQ(X) у PQ(X)t-Так как Х и у фиксированы, аtQи точкой :С2ОТОЧiiаPQ Х +PQ(X) отрезка i сое iиняющего точки PQ(X) и у, принаВ силу выпуклости множества1,то в силу неравенства- PCJ(:C))) =+ {о (у, PQ Х ).14.119;ЛЮ(iое число из сегмента(14.118)можно в iЯТЬtудовлетворяющим неравенству<t <2(х - PQ(X), у - PQ( \))р2(и,П} и таком выборе-2t(:c -PQ(oi))tРОи мы получим изО,14.119;, чтоZ,нее неравенство противоречитХ<р2(х, PQ(x) . Последчто точкапроеiiцией ТОЧiiИ :С на множествооточка Zi Уоiоаленная от Х меньше i чемPQ(X) являетсямножестваQнашласьPQ(X) от х. Полученноеiротиворе'ше зariертттает доказатеш,сТfЮ ле\'Лемма 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
