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

Ïóñòü U ⊂ H âûïóêëîå, çàìêíóòîå ìíîæåñòâî, ïðè÷¼ì int U 6= ∅,J(u) ∈ C2 (U) è ñèëüíî âûïóêëà ñ êîýôôèöèåíòîì κ > 0, J 00 (u) ∈ Lip(U) ñ êîíñòàíòîéLL > 0. Òîãäà åñëè q = 2κku1 − u0 kH < 1, òî ìåòîä (2) ñõîäèòñÿ ê u∗ è âåðíà ñëåäóþùàÿîöåíêà ñêîðîñòè ñõîäèìîñòè:kuk − u∗ kH 62κ 2k k −1·q1 − q2,Lk = 0, 1, 2, .

. .Äîêàçàòåëüñòâî.Ïî Òåîðåìå 6 u∗ ñóùåñòâóåò è åäèíñòâåííà.0Ïðèìåíèì ê Jk (u) Òåîðåìó 8 ï.(d ):Jk0 (u) = J 0 (uk ) + J 00 (uk )(u − uk );Jk00 (u) = J 00 (uk );hJk00 (u)h, hiH = hJ 00 (uk )h, hiH > κkhk2H .uk òàêæå(2) èìååì:Îòñþäà ïî Òåîðåìå 6Ïî Òåîðåìå 9 èçñóùåñòâóåò è åäèíñòâåííà.hJk0 (uk+1 ), u − uk+1 iH > 0 ∀u ∈ U44(3).hJ 0 (uk ) + J 00 (uk )(uk+1 − uk ), u − uk+1 iH > 0 ∀u ∈ UÏîäñòàâèì â ýòî âûðàæåíèå âìåñòî(4)u uk :hJ 0 (uk ), uk − uk+1 iH > hJ 00 (uk )(uk+1 − uk ), uk+1 − uk iH > κkuk+1 − uk k2HuÒåïåðü â êà÷åñòâåâîçüì¼ì â(4) uk+1 (k := k − 1)è ïðèáàâèì ê(5)(5):κkuk+1 − uk k2H 6 hJ 0 (uk ) − J 0 (uk−1 ) − J 00 (uk−1 )(uk − uk−1 ), uk − uk+1 iH = {óïð.

6} ==w1hJ 00 (uk−1 + t(uk − uk−1 ))(uk − uk−1 ), uk − uk−1 iH dt−0− hJ 00 (uk−1 )(uk − uk−1 ), uk − uk+1 iH ==w1h[J 00 (uk−1 + t(uk − uk−1 )) − J 00 (uk−1 )] (uk − uk−1 ), uk − uk+1 iH dt 606Lw1kt(uk − uk−1 )kH ·kuk − uk−1 kH ·kuk+1 − uk kH dt =0Èìååì:Lkuk − uk−1 k2H ·kuk+1 − uk kH .2L2κ 2kkuk − uk−1 k2H 6 . . . 6q2κL∞÷òî ïîñëåäîâàòåëüíîñòü {uk }k=0kuk+1 − uk kH 6Èç(6)è óñëîâèÿq <1ïîëó÷àåì,ñóùåñòâóåò (â ñèëó ïîëíîòû(6).ôóíäàìåíòàëüíàÿ èH)lim uk = u ∈ H,k→∞uk ∈ U, à U çàìêíóòî, òî u ∈ U.â (4) ê ïðåäåëó ïðè k → ∞, òîãäàíî òàê êàê âñåÏåðåéä¼ìâ ñèëó íåïðåðûâíîñòèJ 0 (u)èJ 00 (u)ïîëó÷àåì, ÷òîhJ 0 (u) + J 00 (u)(u − u), u − uiH > 0 ∀u ∈ UÎòñþäà ïî Òåîðåìå 9u ∈ U∗ ,íîU∗ñîñòîèò èç åäèíñòâåííîé òî÷êèu∗ ,çíà÷èòu = u∗ .Òàêèì îáðàçîì, ìû äîêàçàëè, ÷òî ïðîöåññ ñõîäèòñÿ.

Òåïåðü îñòàëîñü âûÿñíèòü ñêîðîñòüñõîäèìîñòè.kuk − u∗ kH 6 {íåð-âîÎòñþäà ïîëó÷àåì(3)∞X∞2κ 2k X 2m −2kqq4} 6kum − um+1 kH 6 {(6)} 6Lm=km=kè òåîðåìà äîêàçàíà.Çàìå÷àíèÿ.1) Ðàññìîòðèì ñëó÷àé, êîãäà(4)ukíà÷èíàþò ïîâòîðÿòüñÿ, òî åñòü êîãäàuk+1 = uk .Èçñëåäóåò, ÷òîhJ 0 (uk ) + J 00 (uk )(uk+1 − uk ), u − uk+1 iH = hJ 0 (uk ), u − uk iH > 0 ∀u ∈ U.Îòñþäà ïî Òåîðåìå 9 ïîëó÷àåì, ÷òîuk45ñîâïàäàåò ñu∗è ïðîöåññ îñòàíàâëèâàåòñÿ.2) Òàê êàêqäîëæíî áûòü ìåíüøå1,òîu0íåîáõîäèìî âûáèðàòü íå ïðîèçâîëüíûìu∗ . Íî â ñëó÷àå,âàðèàíò âûáîðà u0 .îáðàçîì, òî åñòü ïðîöåññ ñõîäèòñÿ â äîñòàòî÷íî ìàëîé îêðåñòíîñòèêîãäàUñîâïàäàåò ñî âñåìÂîçüì¼ì âHìîæíî ïðåäëîæèòü àïðèîðíûé(5) k = 0:κku1 − u0 k2H 6 hJ 0 (u0 ), u0 − u1 iH 6 kJ 0 (u0 )kH ·ku1 − u0 kH .Òåïåðü äîñòàòî÷íî âûáðàòüu0òàêèì, ÷òîkJ 0 (u0 )kH L·< 1,κ2κèqìåíüøå ýòîé âåëè÷èíû. ñëó÷àå, êîãäàíàUU 6= H ýòî, âîîáùå ãîâîðÿ, ñäåëàòü íå âñåãäà óäàñòñÿ, òàê êàê J 0 (u)ìîæåò è íå áûòü ñòîëü ìàëûì.Ìåòîä ñîïðÿæ¼ííûõ íàïðàâëåíèé (ãðàäèåíòîâ) ýòîì ïóíêòå ðàññìîòðèì çàäà÷ó ìèíèìèçàöèè äëÿ ôóíêöèîíàëîâ ñïåöèàëüíîãî âèäàâ êîíå÷íîìåðíîì ãèëüáåðòîâîì ïðîñòðàíñòâå:J(u) =1hAu, ui − hf, ui → inf,2u ∈ Rn = U,A∗ = A > 0.Êðèòåðèåì îïòèìàëüíîñòè äëÿ òàêîé çàäà÷è ÿâëÿåòñÿ óñëîâèåýêâèâàëåíòíî óñëîâèþ(1)J 0 (u∗ ) = 0,êîòîðîåAu∗ = f.Èäåÿ ìåòîäà ñîïðÿæ¼ííûõ ãðàäèåíòîâ çàêëþ÷àåòñÿ â ñëåäóþùåì.

Ïóñòünnáàçèñ â R . Òîãäà äëÿ ëþáîé òî÷êè u0 èç R âûïîëíåíî ðàâåíñòâîn−1{pk }k=0u∗ − u0 = α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Òàêèì îáðàçîì,u∗ïðåäñòàâèìî â âèäåu∗ = u0 + α0 p0 + α1 p1 + . . . + αn−1 pn−1 .Òîãäà èòåðàöèîííóþ ïîñëåäîâàòåëüíîñòü äàííîãî ìåòîäà ìîæíî îïèñàòü êàêu0 = u0u 1 = u 0 + α 0 p0u2 = u0 + α0 p0 + α1 p1...(òî÷íîå îïèñàíèå èòåðàöèè áóäåò äàíî íèæå).Ïîäåéñòâîâàâ íà âûøåïðèâåä¼ííîå ðàâåíñòâî îïåðàòîðîìA,ïîëó÷èìf − Au0 = α0 Ap0 + α1 Ap1 + . .

. + αn−1 Apn−1 .46Âûðàæåíèåf − Au0ñ÷èòàåì èçâåñòíûì, è íàøà çàäà÷à ñîñòîèò â íàõîæäåíèèòàêæå ïðàâèëüíîãî âûáîðà áàçèñàαi ,à{pk }.Îïðåäåëåíèå. Âåêòîðû p è q íàçûâàþòñÿ ñîïðÿæ¼ííûìè îòíîñèòåëüíî ìàòðèöûR = R∗ > 0, åñëè hRp, qi = 0. Ïî-äðóãîìó ýòî íàçûâàþò îðòîãîíàëüíîñòüþ îòíîñèòåëüíîñêàëÿðíîãî ïðîèçâåäåíèÿ hp, qiR = hRp, qi .n−1Åñëè {pk }k=0 áàçèñ èç ñîïðÿæ¼ííûõ îòíîñèòåëüíî A âåêòîðîâ, òîαk =hf − Au0 , pk i,hApk , pk ik = 0, n − 1.(α)Ïóñòü H = Rn , A = A∗ > 0, {pk }n−1k=0 áàçèñ èç ñîïðÿæ¼ííûõ îòíîñèòåëüíîA âåêòîðîâ, uk = uk−1 + αk−1 pk−1 , ãäå αk âû÷èñëÿþòñÿ ïî ôîðìóëàì (α). ÒîãäàËåììà 2.αk = αk∗ = argmin J(uk + αpk ) = −−∞<α<+∞èhJ 0 (uk ), pk iHhApk , pk iH(2)hJ 0 (uk+1 ), pk iH = 0 ∀k = 0, n − 1(3)Äîêàçàòåëüñòâî.Çàïèøåì óñëîâèå íà ìèíèìóìJ(uk + αpk ):hJ 0 (uk + αk∗ pk ), pk i = 0.Òîãäà,hJ 0 (uk + αk∗ pk ), pk i = hAuk − f + αk∗ Apk , pk i = {uk = u0 + α0 p0 + · · · + αk−1 pk−1 } == hAu0 − f, pk i + αk∗ hApk , pk i = 0.Îòñþäà ñ ó÷¼òîìÒåïåðü èç(2)(α)ñëåäóåò, ÷òîαk = αk∗ ,òî åñòü(2).èìååì:uk+1 = uk + αk∗ pk ⇒ J 0 (uk+1 ) = 0 ∀k = 0, n − 1,òî åñòü(3).Ëåììà äîêàçàíà.Îïèøåì ïîäðîáíåå èòåðàöèè â ðàññìàòðèâàåìîì ìåòîäå.

 êà÷åñòâå ïåðâîãî ïðènáëèæåíèÿ áåð¼ì ëþáóþ òî÷êó èç R , à ïåðâûé âåêòîð áóäóùåãî áàçèñà âû÷èñëÿåì êàêçíà÷åíèå ïðîèçâîäíîé ôóíêöèèJ(u) âÒåïåðü ïóñòü òðåáóåòñÿ âû÷èñëèòüäàííîé òî÷êå:∀u0 ∈ Rnp0 = −J 0 (u0 )k + 1-þèòåðàöèþ, êîãäà ïðåäûäóùèå÷èñëåíû, òîãäà ïðèìåíÿåì ñëåäóþùèå ôîðìóëû:uk+1 = uk + αk pk ,pk+1 = −J 0 (uk+1 ) + βk pk47(4u)(4p)kóæå âû-αk çäåñü âû÷èñëÿþòñÿ ïî ôîðìóëàì (α) èëè (2) (îáîçíà÷èì äëÿ îäíîîáðàçèÿ ôîðìóëû(2) êàê (4α)). Êîýôôèöèåíòû æå βk áåðóòñÿ òàêèì îáðàçîì, ÷òîáû äëÿ pk+1 ñîõðàíÿëàñüîðòîãîíàëüíîñòü (ñîïðÿæ¼ííîñòü) ñ pk :βk =hJ 0 (uk+1 ), Apk ihApk , pk i(4β)Ïóñòü H = Rn ãèëüáåðòîâî ïðîñòðàíñòâî, J(u) = 21 hAu, ui − hf, ui ,A∗ = A > 0. Òîãäà ìåòîä (4) ñõîäèòñÿ ê u∗ çà êîíå÷íîå ÷èñëî øàãîâ (íå ïðåâîñõîäÿùåå n), ïðè÷¼ìÒåîðåìà 20.(a) hApk , pm i = 0 ∀k 6= m;(b) hJ 0 (uk ), J 0 (um )i = 0 ∀k 6= m;(c) hJ 0 (uk ), pm i = 0 ∀m = 0, 1, .

. . , k − 1.Äîêàçàòåëüñòâî.Ïðîâåä¼ì äîêàçàòåëüñòâî ïî èíäóêöèè ïî êîëè÷åñòâó èòåðàöèé.Äëÿ îäíîé èòåðàöèè èìååì (áàçèñ èíäóêöèè):(a):âåðíî ïî ïîñòðîåíèþ (ñì. (4β ));(b): hJ 0 (u1 ), J 0 (u0 )i = hJ 0 (u1 ), −p0 i = {Ëåììà} = 0;(c):â òî÷íîñòè ñîâïàäàåò ñÏóñòü òåïåðüìóëû âåðíû äëÿ(b):(3).(a), (b), (c) âåðíû äëÿ k èòåðàöèé âêëþ÷èòåëüíî. Äîêàæåì, ÷òî ýòè ôîð(k + 1)-é èòåðàöèè.äîêàæåì ñíà÷àëà, ÷òîhJ 0 (uk+1 ), J 0 (uk )i = 0.Èìååì:J 0 (uk+1 ) = Auk − f + αk Apk = J 0 (uk ) + αk ApkÏîäñòàâëÿÿ ýòî â ñêàëÿðíîå ïðîèçâåäåíèå ïîëó÷àåì, ÷òîhJ 0 (uk+1 ), J 0 (uk )i = hJ 0 (uk ), J 0 (uk )i + αk hApk , J 0 (uk )i = {4α} == hJ 0 (uk ), J 0 (uk )i −Ïî ôîðìóëàì(3)hJ 0 (uk ), pk ihApk , J 0 (uk )ihApk , pk i(∗)èìååìhJ 0 (uk ), pk i = {(4p)} = hJ 0 (uk ), −J 0 (uk ) + βk−1 pk−1 i = − hJ 0 (uk ), J 0 (uk )i .À ïî ïðåäïîëîæåíèþ èíäóêöèè(a)hApk , J 0 (uk )i = {(4p)} = hApk , −pk + βk−1 pk−1 i = − hApk , pk i .Ïîäñòàâëÿÿ ïîñëåäíèå äâà âûðàæåíèÿ âÏîêàæåì òåïåðü, ÷òî äëÿ(∗),ïîëó÷àåì, ÷òîhJ 0 (uk+1 ), J 0 (uk )i = 0.m 6 k−1 ñêàëÿðíîå ïðîèçâåäåíèå hJ 0 (uk+1 ), J 0 (um )i òàêæåðàâíî 0.hJ 0 (uk+1 ), J 0 (um )i = hJ 0 (uk ), J 0 (um )i + αk hApk , J 0 (um )i = {ïðåäï.= αk hApk , −pm + βm−1 pm−1 i = {ïðåäï.48èíä.(a)} = 0.èíä.(b)} =(c):åñëèm = k,Åñëè æåòîhJ 0 (uk+1 ), pk i = {Ëåììà} = 0.m 6 k − 1,òîhJ 0 (uk+1 ), pm i = hJ 0 (uk ), pm i + αk hApk , pm i = {ïðåäï.(a):ðàññìîòðèìm6k−1(äëÿm=kèíä.(a)è(c)} = 0.óòâåðæäåíèå âåðíî ïî ïîñòðîåíèþ).hApm , pk+1 i = − hApm , J 0 (uk+1 ) + βk pk i = − hApm , J 0 (uk+1 )i ==−11hαm Apm , J 0 (uk+1 )i =hJ 0 (um ) − J 0 (um+1 ), J 0 (uk+1 )i = {(b)} = 0.αmαmÇäåñü ìû ïðåäïîëàãàëè, ÷òîαm 6= 0.Ïîêàæåì, ÷òî ýòî äåéñòâèòåëüíî òàê.Âîçìîæíû ñèòóàöèè:1)αk = 0.(4u) ïîëó÷àåì, ÷òî uk+1 = uk , òî(4α) αk = 0 òîãäà è òîëüêî òîãäà, êîãäàÒîãäà ïî ôîðìóëàìçàöèêëèâàåòñÿ.

Íî ïîåñòü ïðîöåññhJ 0 (uk ), pk i = 0 = {(4p)} = hJ 0 (uk ), −J 0 (uk ) + βk−1 pk−1 i . ñèëó ëåììû ïîëó÷àåì, ÷òîè2)uk = u∗ .0 = −kJ 0 (uk )k2 .Îòñþäà ñëåäóåò, ÷òîJ 0 (uk ) = 0Òàêèì îáðàçîì, íàéäåí ìèíèìóì è ïðîöåññ ìîæíî îñòàíîâèòü.hApk , pk i = 0. Òîãäà, òàê êàê A > 0, pk = 0 è ïî ôîðìóëàì (4u) îïÿòü ïîëó÷àåì,÷òî uk+1 = uk . Ïî ôîðìóëàì (4p) pk = 0 òîãäà è òîëüêî òîãäà, êîãäà−J 0 (uk ) + βk−1 pk−1 = 0Òî åñòüuk = u∗⇒−kJ 0 (uk )k2 = 0.è ïðîöåññ îïÿòü òàêè ìîæíî îñòàíîâèòü.Òåîðåìà ïîëíîñòüþ äîêàçàíà.Ïðè ðåàëèçàöèè ìåòîäà ñîïðÿæ¼ííûõ íàïðàâëåíèé äëÿ ôóíêöèîíàëîâ îáùåãî âèäàâîçíèêàþò ïðîáëåìû èç-çà íàëè÷èÿ ìàòðèöûAâ ôîðìóëàõ(4α)è(4β).Íî äëÿ òàêîãîñëó÷àÿ ìîæíî èñïîëüçîâàòü äðóãèå ñïîñîáû âû÷èñëåíèÿ ýòèõ ôîðìóë:αk = {Ëåììà (2)} = argmin J(uk + αpk )−∞<α<∞βk =hJ 0 (uk+1 ), J 0 (uk+1 ) − J 0 (uk )ihJ 0 (uk+1 ), Apk i αk·== {(3), (b), (c)} =hApk , pk iαkhJ 0 (uk+1 ) − J 0 (uk ), pk i=hJ 0 (uk+1 ), J 0 (uk+1 ) − J 0 (uk )ikJ 0 (uk+1 )k2=.kJ 0 (uk )k2kJ 0 (uk )k2Çàìåòèì, ÷òî ýòè ôîðìóëû ðàçëè÷íû, åñëè ôóíêöèîíàë íå êâàäðàòè÷íûé.49Ìåòîä ïîêîîðäèíàòíîãî ñïóñêàÇäåñü ìû áóäåì ðàññìàòðèâàòü ýêñòðåìàëüíóþ çàäà÷ó â êîíå÷íîìåðíîì ãèëüáåðòîâîìnïðîñòðàíñòâå H = R :nJ(u) → inf,u∈R .Rn .

Ïîëîæèì pn+1 = p1 , pn+2 = p2 , . . . Ïóñòü òàêæå u0 ∈ Rn íåêîå íà÷àëüíîå ïðèáëèæåíèå. Ïðåäïîëîæèì, ÷òî óæå ïîñòðîåíû k ïðèáëèæåíèé uk èìû íàõîäèìñÿ íà k + 1-îì øàãå èòåðàöèè.Íàçîâ¼ì (k + 1)-é øàã èòåðàöèè óäà÷íûì, åñëèJ(uk − αk pk+1 ) < J(uk ),J(uk + αk pk+1 ) < J(uk ).Ïóñòü{pk }nk=1 áàçèñ â ïðîòèâíîì ñëó÷àå íàçîâ¼ì øàãÅñëè øàã óäà÷íûé, òî îáíîâëÿåììåíÿåìαk : αk+1 = αk .íåóäà÷íûì.uk (áåð¼ì òîçíà÷åíèå, ãäå ìåíüøåÅñëè æå øàã íåóäà÷íûé, òî ïåðåõîäèì ê îáðàáîòêåJ(uk+1 ))pk+2 .è íåÊðîìå òîãî, âåä¼òñÿ ïîäñ÷¼ò íåóäà÷íûõ øàãîâ ïîäðÿä.

Åñëè ýòî ÷èñëî ñòàíîâèòñÿα: uk+1 îñòàâëÿåì ðàâíîéuk , ïåðåõîäèì ê îáðàáîòêå âåêòîðà pk+2 , è ïîëàãàåì αk+1 = λαk , ãäå λ ∈ (0, 1) íàïåð¼äçàäàííûé êîýôôèöèåíò äðîáëåíèÿ (îáû÷íî åãî áåðóò ðàâíûì 1/2).ðàâíûì ðàçìåðíîñòè ïðîñòðàíñòâà, òî ïðîèñõîäèò äðîáëåíèåÏóñòü ôóíêöèÿ J(u) ∈ C1 (Rn ) è âûïóêëà, ìíîæåñòâî ËåáåãàM (u0 ) = {u ∈ Rn |J(u) 6 J(u0 )} îãðàíè÷åíî. Òîãäà îïèñàííûé âûøå ïðîöåññ ñõîäèòñÿ è ïî ôóíêöèè è ïî àðãóìåíòó:Òåîðåìà21.J(uk ) → J∗ ;k→∞ρ(uk , U∗ ) → 0.k→∞Äîêàçàòåëüñòâî.nÒàê êàê M (u0 ) îãðàíè÷åíî è çàìêíóòî (òî åñòü êîìïàêò â R ), à ôóíêöèÿ J(u) íåïðåðûâíà, òî ïî Òåîðåìå 1 J∗ > −∞, U 6= ∅.Äàëåå, ïî ïîñòðîåíèþJ(uk ) > J(uk+1 ) > .

. . > J∗ ,òî åñòü ïîñëåäîâàòåëüíîñòü{J(uk )}ñõîäèòñÿ è ñóùåñòâóåò ïðåäåëlim J(uk ) = J > J∗ .k→∞Çàìåòèì, ÷òîαk → 0ïðèk → ∞.Ýòî ñëåäóåò èç áåñêîíå÷íîñòè ÷èñëà äðîáëåíèé.Ðàññìîòðèì ïîäïîñëåäîâàòåëüíîñòè ñ èíäåêñàìèαkm → 0;m→∞Ìîìåíòókmïðåäøåñòâóåònkm ìîìåíòàìè äðîáëåíèÿ.ukm → u ∈ M (u0 )m→∞íåóäà÷:J(ukm ± αkm pi ) > J(ukm ) ∀i = 1, n.Ïî ôîðìóëå êîíå÷íûõ ïðèðàùåíèé èìååì:iJ 0 (ukm ± θmαkm pi ), ±αkm pi > 0,50iθm∈ [0, 1].Ðàçäåëèì ýòî âûðàæåíèå íàJ 0 (u) ïîëó÷èì:αkmè óñòðåìèìm ê áåñêîíå÷íîñòè, òîãäà âñèëó íåïðåðûâ-íîñòèhJ 0 (u), ±pi i > 0 ∀i = 1, n,{pi }Îòñþäà â ñèëó òîãî, ÷òîu ∈ U∗ ,ò.å.hJ 0 (u), pi i = 0 ∀i = 1, nJ 0 (u) = 0.