Методы оптимизации. Конспект лекций (Буряков) (2010), страница 6

À â ñëó÷àå, êîãäà αk = 0 èç (3) èìååì(fk0 (0) > 0fk0 (0) = hJ 0 (uk ), J 0 (uk )i 6 0.Îáîçíà÷èì ÷åðåçÎòêóäàfk0 (0) = 0fk (α)âûðàæåíèåè ìû îïÿòü ïîëó÷èëè íåîáõîäèìîå óñëîâèå ìèíèìóìà.Ïóñòü H ãèëüáåðòîâî ïðîñòðàíñòâî, J(u) ∈ C1 (H), J(u) ñèëüíî âûïóêëà ñ êîýôôèöèåíòîì κ > 0, J 0 (u) ∈ Lip(H) ñ êîíñòàíòîé L > 0. Òîãäà ïðè ëþáîìâûáîðå íà÷àëüíîé òî÷êè u0 èç H ìåòîä (2)(3) ñõîäèòñÿ ê òî÷êå ìèíèìóìà u∗ çàäà÷è(1), ïðè÷¼ì äëÿ ñêîðîñòè ñõîäèìîñòè ñïðàâåäëèâà îöåíêà:Òåîðåìà 14.κkuk − u∗ k2 6 J(uk ) − J(u∗ ) 6 q k (J(u0 ) − J(u∗ )),236ãäåq =1−κ∈ [0, 1)L(4)Äîêàçàòåëüñòâî.Äëÿ íà÷àëà çàìåòèì, ÷òî ïî Òåîðåìå 6 òî÷êàu∗äëÿ ôóíêöèèJ(u)ñóùåñòâóåò èåäèíñòâåííà.(c0 )Ïî Òåîðåìå 8 ï.(óñëîâèå ñèëüíîé ìîíîòîííîñòè ãðàäèåíòà) èìååì:κku − vk2H 6 hJ 0 (u) − J 0 (v), u − viHÓ÷èòûâàÿ, ÷òîJ 0 (u) ∈ Lip(H)∀u, v ∈ H.è ïðèìåíÿÿ íåðàâåíñòâî Êîøè-Áóíÿêîâñêîãî òàêæåïîëó÷àåì, ÷òîhJ 0 (u) − J 0 (v), u − viH 6 Lku − vk2H .Èç ýòèõ íåðàâåíñòâ ñëåäóåò, ÷òîÒåïåðü îáîçíà÷èì ÷åðåçakκ 6 L,è âûðàæåíèå äëÿðàçíîñòü ìåæäóJ(uk )èqJ(u∗ ).â (4) âåðíî.Î÷åâèäíî, ÷òîak > 0.Âñâîþ î÷åðåäüak+1 = J(uk+1 ) − J(uk ) + ak 6 {(2), (3); ∀α} 6 [J(uk − αJ 0 (uk )) − J(uk )] + akÏðèìåíèì ê ðàçíîñòè â êâàäðàòíûõ ñêîáêàõ ôîðìóëó êîíå÷íûõ ïðèðàùåíèé â èíòåãðàëüíîé ôîðìå:J(uk − αJ 0 (uk )) − J(uk ) =w1hJ 0 (uk − αtJ 0 (uk )), −αJ 0 (uk )iH dt00Äîáàâèì è âû÷òåì ê ëåâîìó àðãóìåíòó ñêàëÿðíîãî ïðîèçâåäåíèÿ J (uk ), òîãäà ïî íåðà0âåíñòâó Êîøè-Áóíÿêîâñêîãî è â ñèëó Ëèïøèö-íåïðåðûâíîñòè J (u) ýòî âûðàæåíèå íåïðåâîñõîäèò−αkJ0(uk )k2H+w101Lk − αtJ 0 (uk )kH ·k − αJ 0 (uk )kH dt = −αkJ 0 (uk )k2H + Lα2 kJ 0 (uk )k2H .2Òàêèì îáðàçîì,1ak+1 6 ak − αkJ 0 (uk )k2H + Lα2 kJ 0 (uk )k2H2∀α > 0. ïðàâîé ÷àñòè ýòîãî íåðàâåíñòâà ñòîèò êâàäðàòíûé òð¼õ÷ëåí îòíîñèòåëüíîäîñòèãàåò ñâîåãî ìèíèìóìà â òî÷êå1/L.α,êîòîðûéÎòñþäà ñëåäóåò, ÷òîak+1 6 ak −1kJ 0 (uk )k2H2L(5)Ïåðâàÿ ÷àñòü íåðàâåíñòâà (4) ñëåäóåò èç Òåîðåìû 6.Äîêàæåì âòîðóþ ÷àñòü íåðàâåíñòâà.

Ïî Òåîðåìå 8 ï.(b0 )èìååìκκak = J(uk ) − J(u∗ ) 6 hJ 0 (uk ), uk − u∗ i − kuk − u∗ k2 6 kJ 0 (uk )k·kuk − u∗ k − kuk − u∗ k2 .22Îáîçíà÷èìkuk − u∗ k = y,òîãäàκak 6 kuk − u∗ k·y − y 2 .237Ýòà êâàäðàòè÷íàÿ ôóíêöèÿ îò ïåðåìåííîéÏîýòîìóak 6Âûðàæàÿ îòñþäà íîðìókJ 0 (uk )kHyäîñòèãàåò ìàêñèìóìà â òî÷êåy0 =kJ 0 (uk )k.κ1kJ 0 (uk )k2H .2κè ïîäñòàâëÿÿ å¼ â (5), ïîëó÷èì:κak+1 6 ak 1 −= ak q.LÏðèìåíÿÿ ýòî íåðàâåíñòâîk,ðàç ïîëó÷àåì âòîðîå íåðàâåíñòâî â (4), è òåîðåìà ïîëíî-ñòüþ äîêàçàíà.(2)(3) äà¼ò â ñëó÷àå, êîãäà κ = LJ(u) = kuk2H − hb, uiH ). Ïðè ýòîìÍàèëó÷øèå ðåçóëüòàòû, êàê íåòðóäíî âèäåòü, ìåòîä(íàïðèìåð, äëÿ êâàäðàòè÷íûõ ôóíêöèîíàëîâ âèäàñîãëàñíî (4) ìû ïîëó÷àåìòî÷íûéðåçóëüòàò óæå ïîñëå ïåðâîãî øàãà ïðîöåññà.J(u) = kAu − f k2F çàäà÷à (3) ðåøàåòñÿ0ÿâíûì îáðàçîì. Åñëè îáîçíà÷èòü ÷åðåç fk (α) âûðàæåíèå J(uk − αJ (uk )), òî äëÿ ñëó÷àÿÇàìåòèì, ÷òî äëÿ êâàäðàòè÷íîãî ôóíêöèîíàëàêâàäðàòè÷íîãî ôóíêöèîíàëà èìååì:fk (α) = kA(uk − αJ 0 (uk )) − f k2F = kAuk − f k2F + α2 kAJ 0 (uk )k2F − 2 hAuk − f, αAJ 0 (uk )iF . ñëó÷àå, êîãäàòåëüíîα,kAJ 0 (uk )kF 6= 0,èìååì â ïðàâîé ÷àñòè êâàäðàòíûé òð¼õ÷ëåí îòíîñè-êîòîðûé äîñòèãàåò ìèíèìóìà â òî÷êåhAuk − f, AJ 0 (uk )iF1 hAuk − f, AA∗ (Auk − f )iF0∗·={J(u)=2A(Au−f)}==kAJ 0 (uk )k2F2kAA∗ (Auk − f )k2F1 kA∗ (Auk − f )k2F1 kJ 0 (uk )k2F1 hA∗ (Auk − f ), A∗ (Auk − f )iF= ·= ·= ·2kAA∗ (Auk − f )k2F2 kAA∗ (Auk − f )k2F2 kAJ 0 (uk )k2Fαk =AJ 0 (uk ) = 0 îçíà÷àåò, ÷òî AA∗ (Auk − f ) = 0.

Åñëè îáîçíà÷èòü∗ðàçíîñòü Auk − f ÷åðåç vk , òî áóäåì èìåòü, ÷òî vk ∈ ker AA . À èç ýòîãî ñëåäóåò, ÷òîvk ∈ ker A∗ , äåéñòâèòåëüíî:Ñëó÷àé æå, êîãäàAA∗ vk = 0 ⇒ hAA∗ vk , vk i = 0 ⇒ hA∗ vk , A∗ vk i = 0 ⇒ A∗ vk = 0.J 0 (uk ) = 0, òî åñòü ïðîöåññ îñòàíàâëèâàåòñÿ.Óïðàæíåíèå 16 (3). Íàéòè ÿâíîå âûðàæåíèå äëÿ αk èç (3) äëÿÎòñþäà ïîëó÷àåì, ÷òîJ(u) =1hAu, ui − hb, ui ,2ôóíêöèîíàëàA∗ = A > 0.Íåïðåðûâíûé àíàëîã ìåòîäà ñêîðåéøåãî ñïóñêàÊàê è â ïðåäûäóùåì ìåòîäå, çäåñü ìû ðàññìàòðèâàåì çàäà÷ó ìèíèìèçàöèè ôóíêöèèJ(u)íà ìíîæåñòâå áåç îãðàíè÷åíèéU = H:J(u) → inf, u ∈ H38(1)Ïðèâåä¼ì íåêîòîðûå ôîðìàëüíûå ðàññóæäåíèÿ, êîòîðûå ïîçâîëÿò íàì ïîëó÷èòüíåïðåðûâíûé àíàëîã ìåòîäà ñêîðåéøåãî ñïóñêà. Ðàññìîòðèì øàã ïðîöåññà äëÿ ýòîãîìåòîäà:uk+1 = uk − αJ 0 (uk ).Åñëè ðàññìàòðèâàòü∆tkêàê íåêèé âðåìåííîé øàã, òî ðàçäåëèâ ýòî ðàâåíñòâî íà∆tkïîëó÷èì:αk 0uk+1 − uk=−J (uk ).∆tk∆tkÅñëè òåïåðü çàäàòü çíà÷åíèåu(t)â íà÷àëüíûé ìîìåíò âðåìåíèt = 0,òî ìû ïðèä¼ì(èñõîäÿ èç çäðàâîãî ñìûñëà) ê ñèñòåìåu0 (t) = −β(t)J 0 [u(t)],u(0) = u0t>0(2)Ïóñòü J(u) ñèëüíî âûïóêëà íà H ñ êîýôôèöèåíòîì κ > 0, J 0 (u) ∈ Lip(H),β(t) > β0 > 0 íåïðåðûâíà ïî t.

Òîãäà äëÿ ëþáîãî íà÷àëüíîãî ïðèáëèæåíèÿ u0 ∈ H ìåòîä(2) ñõîäèòñÿ ê u∗ è äëÿ ñêîðîñòè ñõîäèìîñòè ñïðàâåäëèâà îöåíêà:Òåîðåìà 15.ku(t) − u∗ kH 6 ku0 − u∗ kH ·e−κβ0 t , t > 0(3)Äîêàçàòåëüñòâî.Êàê è â ïðåäûäóùåé òåîðåìå çàìåòèì, ÷òî ïî Òåîðåìå 6 òî÷êàu∗ñóùåñòâóåò è åäèí-ñòâåííà.Ââåä¼ì ôóíêöèþ Ëÿïóíîâà:V (τ ) = ku(τ ) − u∗ k2H .V 0 (τ ) = 2 hu0 (τ ) − u0∗ , u(τ ) − u∗ iH = 2 h−β(τ )J 0 [u(τ )], u(τ ) − u∗ iH 66 {Òåîðåìà 8 ï.(c0 )} 6 −2β0 κku(τ ) − u∗ k2H = −2β0 κV (τ ).Äîìíîæèì îáå ÷àñòè ýòîãî íåðàâåíñòâà íàe2βκτe2βκτ V 0 (τ ) + 2β0 κe2βκτ V (τ ) 6 0,Ïðîèíòåãðèðóåì îáå ÷àñòè ïîτîò0äîè ïåðåíåñ¼ì âñ¼ â ëåâóþ ÷àñòü:òî åñòüV (τ )e2βκτ06 0.t:ku(t) − u∗ k2H ·e2βκt − ku0 − u∗ k2H ·1 6 0.Ïåðåíîñÿ âòîðîå ñëàãàåìîå â ïðàâóþ ÷àñòü, äåëÿ íàÒåîðåìà äîêàçàíà.39e2βκtè âçÿâ êîðåíü, ïîëó÷àåì(3).Ìåòîä ïðîåêöèè ãðàäèåíòà ýòîì ïóíêòå ðàññìîòðèì çàäà÷ó ìèíèìèçàöèè ôóíêöèèñîâïàäàþùåì ñî âñåì ïðîñòðàíñòâîìHJ(u)íà ìíîæåñòâå, óæå íå(çàäà÷ó íà óñëîâíûé ìèíèìóì):J(u) → inf,u∈U⊂H(1). äàííîì ìåòîäå ðàññìàòðèâàåòñÿ èòåðàöèîííàÿ ïîñëåäîâàòåëüíîñòüuk+1 = prU (uk − αk J 0 (uk )),k = 0, 1, 2, .

. .Ïðè ýòîì íåîáõîäèìî ó÷èòûâàòü, ÷òî íà êàæäîì øàãå ïðèáëèæåíèÿ âñå òî÷êèïðèíàäëåæàòüU.(2)uk äîëæíûÄëÿ ïðîñòîòû áóäåì ñ÷èòàòü, ÷òîαk = α ≡ const(3)Ïóñòü U ⊂ H âûïóêëîå, çàìêíóòîå ìíîæåñòâî, J(u) ∈ C1 (U) èñèëüíî âûïóêëà ñ êîýôôèöèåíòîì κ > 0, J 0 (u) ∈ Lip(U) ñ êîíñòàíòîé L > 0. Ïóñòüòàêæå α ∈ 0, L2κ2 . Òîãäà äëÿ ëþáîãî íà÷àëüíîãî ïðèáëèæåíèÿ u0 ∈ U ìåòîä (2), (3)ñõîäèòñÿ:√kuk − u∗ kH 6 ku0 − u∗ kH ·q k (α), ãäå 0 < q(α) = 1 − 2κα + α2 L2 < 1.(4)Òåîðåìà 16.Äîêàçàòåëüñòâî.Ïî Òåîðåìå 11 òî÷êàu∗ÿâëÿåòñÿ ðåøåíèåì çàäà÷èu∗ = prU (u∗ − αJ 0 (u∗ )),Ââåä¼ì îïåðàòîðA:U→U(1)òîãäà è òîëüêî òîãäà, êîãäà∀α > 0.òàêîé, ÷òîAu = prU (u − αJ 0 (u)).Òîãäà òî÷êàu∗áóäåò íåïîäâèæíîé äëÿ ýòîãî îïåðàòîðà.Ïîäáåð¼ì òåïåðü òàêèåkAu − Avk2H 6 {Òåîðåìàα,ïðè êîòîðûõ îïåðàòîðAáóäåò ñæèìàþùèì.6 k[u − αJ 0 (u)] − [v − αJ 0 (v)]k2H == ku − vk2H + α2 kJ 0 (u) − J 0 (v)k2H − 2α hu − v, J 0 (u) − J 0 (v)iH10 ï.3}Âòîðîå ñëàãàåìîå â ýòîì âûðàæåíèè íå ïðåâîñõîäèò â ñèëó Ëèïøèö-íåïðåðûâíîñòè ïåð022âîé ïðîèçâîäíîé J (u) âåëè÷èíû L ku − vkH .

Ïîñëåäíåå æå ñëàãàåìîå íå áîëüøå, ÷åìκku − vk2H , òàê êàê J(u) ñèëüíî âûïóêëà. Èç ýòîãî ïîëó÷àåì:kAu − Avk2H 6 (1 − 2κα + α2 L2 )ku0 − u∗ k2H = q 2 (α)ku0 − u∗ k2H .Òåïåðü, ïðèìåíÿÿ ïðèíöèï ñæèìàþùèõ îòîáðàæåíèé (ñì., íàïðèìåð, [ÊÔ, ãë. II, Ÿ4]),ïîëó÷àåì(4)è òåîðåìà äîêàçàíà.40Ðàññìîòðèì íåïðåðûâíûé àíàëîã ìåòîäà ïðîåêöèè ãðàäèíåòà. Èñïîëüçîâàííîå ïðèäîêàçàòåëüñòâå ñîîòíîøåíèåuk+1 = Auk ,áóäó÷è çàïèñàííûì â âèäåAuk − ukuk+1 − uk=,∆tk∆tkíàïîìèíàåò äèñêðåòèçèðîâàííîå äèôôåðåíöèàëüíîå óðàâíåíèå(u0 (t) = −β(t)(u(t) − Au(t)),u(0) = u0 .(12)Ñïðàâåäëèâà ñëåäóþùàÿÏóñòü H - ãèëüáåðòîâî, ìíîæåñòâî U âûïóêëî è çàìêíóòî, A : U → U- ñæèìàþùèé ñ êîýôôèöèåíòîì ñæàòèÿ q ∈ (0, 1), 0 < β0 6 β(t) 6 β1 - íåïðåðûâíàÿîãðàíè÷åííàÿ ôóíêöèÿ. Òîãäà (12) ñõîäèòñÿ ê íåïîäâèæíîé òî÷êå u∗ , ïðè÷åì ku(t) −u∗ k 6 ku0 − u∗ k exp−β0 (1−q)t äëÿ ëþáîãî u0 ∈ U .Òåîðåìà 17.Äîêàçàòåëüñòâî.Îãðàíè÷èìñÿ èäååé äîêàçàòåëüñòâà.

Îòìåòèì, ÷òî â ñèëó ñæèìàåìîñòèñóùåñòâóåò è åäèíñòâåííà, è, êðîìå òîãî,∀t u(t) ∈ U .A,òî÷êàu∗ ñèëó âûïóêëîñòè èìååì:u(t + ∆t) ≈ u(t) − ∆tβ(t)(u(t) − Au(t)) = (1 − ∆tβ(t))u(t) + ∆(t)β(t)Au(t) ∈ U.Ó÷èòûâàÿ, ÷òî0 = β(t)(u∗ − Au∗ ),îáîçíà÷èìx(t) = u(t) − u∗ .Òîãäà ìû ïðèõîäèì êóðàâíåíèþ(x0 (t) = β(t)(x(t) + Au(t) − Au∗ ),x(0) = u0 − u∗ .Óìíîæèì ñêàëÿðíî ëåâóþ è ïðàâóþ ÷àñòè íà(kx(t)k2 )0 . Ðàñïèøåì ïðàâóþ:2x(t).Òîãäà ëåâàÿ ÷àñòü îáåðíåòñÿ â2β(t) h−x(t) + Au(t) − Au∗ , x(t)i = 2β(t)(kx(t)k2 + hAu(t) − Au∗ , x(t)i) 66 2β(t)kxk2 (q − 1) 6 −2β0 (1 − q)kx(t)k2 .Ñðàâíåíèå ëåâîé è ïðàâîé ÷àñòè çàâåðøàåò äîêàçàòåëüñòâî.Ìåòîä óñëîâíîãî ãðàäèåíòà ýòîì ïóíêòå ðàññìàòðèâàåòñÿ çàäà÷à ìèíèìèçàöèè ñëåäóþùåãî âèäà:J(u) → inf,u ∈ U ⊂ H.Èäåÿ ìåòîäà óñëîâíîãî ãðàäèåíòà îñíîâàíà íà òîì, ÷òî â îêðåñòíîñòè òî÷êèöèîíàëJ(u)ìîæíî ïðèáëèæåííî ïðåäñòàâèòü êàêJ(u) ' J(uk ) + hJ 0 (uk ), u − uk i .41(1)ukôóíê-J(uk ) áëèçêî ê J(u), òî ìû ñòàðàåìñÿ ìèíèìèçèðîâàòüJk (u) = hJ 0 (uk ), u − uk i .

Ââåä¼ì îáîçíà÷åíèåÒàê êàêäåíèåñêàëÿðíîå ïðîèçâå-uk = argmin Jk (u).(2)u∈UÒîãäà èòåðàöèîííàÿ ïîñëåäîâàòåëüíîñòü ðàññìàòðèâàåìîãî ìåòîäà îïèñûâàåòñÿ êàêuk+1 = uk + αk (uk − uk ),(3)αk = argmin J (uk + α (uk − uk ))(4)ãäå06α61Äëÿ îáîñíîâàíèÿ ñõîäèìîñòè ìåòîäà äîêàæåì ñíà÷àëà îäíó íåáîëüøóþ ëåììó.Ëåììà 1 (îöåíêà ñêîðîñòè ñõîäèìîñòè ÷èñëîâîé ïîñëåäîâàòåëüíîñòè).Ïóñòü äëÿ ìîíîòîííîé ÷èñëîâîé ïîñëåäîâàòåëüíîñòè {ak }∞k=0 :a0 > a1 > .

. . > an > . . . > 0âûïîëíÿåòñÿ óñëîâèåak − ak+1 > C·a2kÒîãäà âåðíà îöåíêà:am 6a01 + a0 Cmk = 0, 1, 2, . . .m = 0, 1, 2, . . .(∗).Äîêàçàòåëüñòâî.Ïðåæäå âñåãî çàìåòèì, ÷òî ïîñëåäîâàòåëüíîñòü ñõîäèòñÿ êàê ìîíîòîííî óáûâàþùàÿè îãðàíè÷åííàÿ ñíèçó. Îöåíèì ðàçíîñòü âåëè÷èí, îáðàòíûõ ýëåìåíòàì ïîñëåäîâàòåëüíîñòè:1ak+1−1ak − ak+1C·a2=> 2 k = C.akak ·ak+1akÏðîñóììèðîâàâ ýòè íåðàâåíñòâà ïîkîò0äîm,ïîëó÷èì11−> C·m.am a0Îòñþäà íåïîñðåäñòâåííî ñëåäóåò(∗).Ïóñòü U ⊂ H âûïóêëîå, çàìêíóòîå, îãðàíè÷åííîå ìíîæåñòâî,J(u) ∈ C (U) è âûïóêëà, J 0 (u) ∈ Lip(U) ñ êîíñòàíòîé L > 0, D = diamU.

Òîãäà J(u0 ) − J∗1J(uk ) − J∗ 6(5).=OJ(u0 )−J∗k1 + 2LD kÒåîðåìà 18.1Åñëè J(u) ñèëüíî âûïóêëà, òî, êðîìå ýòîãî, âûïîëíåíî óñëîâèåκkuk − u∗ k2H 6 J(uk ) − J∗ .242Äîêàçàòåëüñòâî.J(u) âûïóêëà èíåïðåðûâíà, ñëåäîâàòåëüíî, è ñëàáî ïîëóíåïðåðûâíà ñíèçó.Uâû-ïóêëî, çàìêíóòî è îãðàíè÷åíî, ñëåäîâàòåëüíî, ÿâëÿåòñÿ ñëàáûì êîìïàêòîì. Îòñþäà ïîÒåîðåìå 2 èìååì, ÷òîJ∗ > −∞, U∗ 6= ∅.Îáîçíà÷èì ÷åðåçakJ(uk )ðàçíîñòü ìåæäóJ∗ ,èòîãäàak+1 = ak + J(uk+1 ) − J(uk ) 6 ak + J(uk + α(uk − uk )) − J(uk ) == {ô-ëàêîíå÷íûõ ïðèðàùåíèé}= ak +w1hJ 0 (uk + tα(uk − uk )), α(uk − uk )iH dt0Ïðèáàâèì è âû÷òåì ê ïåðâîìó àðãóìåíòó ñêàëÿðíîãî ïðîèçâåäåíèÿ ïîä èíòåãðàëîì âåëè0÷èíó J (uk ) è, ïðèìåíèâ íåðàâåíñòâî Êîøè-Áóíÿêîâñêîãî è ó÷òÿ Ëèïøèö-íåïðåðûâíîñòü0ôóíêöèè J (u), ïîëó÷èìak+1 = ak + α hJ 0 (uk ), uk − uk iH +w1L·ktα(uk − uk )kH ·kα(uk − uk )kH dt 606 ak + α hJ 0 (uk ), uk − uk iH +Ïî Òåîðåìå 7 ï.(b)ak+1 6 ak +L 2 2Lα D 6 ak + α hJ 0 (uk ), u∗ − uk iH + α2 D222îòñþäà ïîëó÷àåì:L 2 2Lα D + α(J(u∗ ) − J(uk )) = (1 − α)ak + α2 D222α = 0 è ïîëó÷èì, ÷òî ak+1 6 ak ,ïîñëåäîâàòåëüíîñòü {ak } èìååò ïðåäåë a > 0.Ïåðåéä¼ì â (6) ê ïðåäåëó ïðè k → ∞:Ïîäñòàâèì â ýòó îöåíêóa 6 (1 − α)a +Ðàçäåëèì íàαè óñòðåìèìααÇíà÷èò, íà÷èíàÿ ñ íåêîòîðîãîÁåð¼ì â(6) α = αkâåðø= αk =íî ïðè ýòîì âñåak > 0,(6)òî åñòüL 2 2α D2a 6 0.

Òàêèì(6) ïî αê 0. Èìååì îöåíêóÐàññìîòðèì òåïåðü ìèíèìóì ïðàâîé ÷àñòè∀α ∈ [0, 1]îáðàçîì,a = 0.ak→ 0.LD2k, αk ∈ [0, 1].è ïîëó÷àåì îöåíêóak+1 6 ak −a2k.2LD2Îòñþäà ñ ó÷¼òîì Ëåììû 1 ïîëó÷àåì ïåðâîå óòâåðæäåíèå òåîðåìû.Îñòàëîñü çàìåòèòü, ÷òî åñëèJ(u)ñèëüíî âûïóêëà, òî âòîðîå óòâåðæäåíèå ñëåäóåòíåïîñðåäñòâåííî èç Òåîðåìû 6 ï. 2. Òåîðåìà ïîëíîñòüþ äîêàçàíà.43Ìåòîä ÍüþòîíàÐàññìàòðèâàåì çàäà÷ó ìèíèìèçàöèè ôóíêöèèJ(u) → inf,J(u):u∈U⊆H(1)Èäåÿ ìåòîäà Íüþòîíà ïîõîæà íà ìåòîä óñëîâíîãî ãðàäèåíòà, íî çäåñü ìû áóäåì èñïîëüçîâàòü íå ëèíåéíóþ, à êâàäðàòè÷íóþ àïïðîêñèìàöèþ ôóíêöèèòî÷êèJ(u)â îêðåñòíîñòèuk :1 000J(u) ' J(uk ) + hJ (uk ), u − uk i + hJ (uk )(u − uk ), u − uk i .2Îáîçíà÷èì âûðàæåíèå â êâàäðàòíûõ ñêîáêàõ ÷åðåçJk (u)(êâàäðàòè÷íî ïîu).Íà êàæäîì øàãå ïðîöåññà íàõîäèòñÿ ìèíèìóìuk = argmin Jk (u).(2)u∈UÈ âû÷èñëÿåòñÿ ñëåäóþùåå ïðèáëèæåíèå ïî ôîðìóëàì (â îáùåì ñëó÷àå):uk+1 = uk + αk (uk − uk ),αk = argmin J(uk + α(uk − uk )).06α61Íî ìû áóäåì ðàññìàòðèâàòü ìåòîä â áîëåå ïðîñòîì âàðèàíòå, êîãäàðóþòñÿ è ïðèíèìàþòñÿ ðàâíûìè1. ýòîì ñëó÷àåuk+1 = uk .αkíå ìèíèìèçè-Ýòî êëàññè÷åñêèé ìåòîäÍüþòîíà.Òåîðåìà 19.