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

Äëÿ ýòîéâûïóêëî, òî äëÿ ëþáîé òî÷êè÷òî äëÿ ëþáîãîα ∈ [0, α0 ]òî÷êàòî÷êè ïî óñëîâèþ âûïîëíåíî íåðàâåíñòâî:J(u∗ + α(u − u∗ )) − J(u∗ ) > 0.Ïðèìåíÿÿ ôîðìóëó êîíå÷íûõ ïðèðàùåíèé, ïîëó÷àåì:hJ 0 (u∗ + θα(u − u∗ ), α(u − u∗ )i > 0.Ðàçäåëèì ýòî íåðàâåíñòâî íà α è óñòðåìèì α ê íóëþ. Òîãäà â ñèëó íåïðåðûâíî0ñòè J (u) ïîëó÷àåì ïåðâîå óòâåðæäåíèå óòâåðæäåíèå òåîðåìû.2) Äëÿ äîñòàòî÷íî ìàëûõòî÷êóuaâ(1)α>0òî÷êàua = u∗ − αJ 0 (u∗ )ïðèíàäëåæèòè ïîëó÷èì:hJ 0 (u∗ ), −αJ 0 (u∗ )i > 0,òî åñòükJ 0 (u∗ )k2 6 0,à ýòî îçíà÷àåò, ÷òîJ 0 (u∗ ) = 0.3) Ïîñëåäíåå óòâåðæäåíèå òåîðåìû ñëåäóåò èç ïóíêòà (b) Òåîðåìû 7:J(u) − J(u∗ ) > hJ 0 (u∗ ), u − u∗ i > 0.Òåîðåìà äîêàçàíà.Ïðèìåðû ïðèìåíåíèÿ Òåîðåìû 9.29U.Ïîäñòàâèì1) Ðàññìîòðèì ñëåäóþùóþ òðèâèàëüíóþ çàäà÷ó ìèíèìèçàöèè íà îäíîìåðíîì ïðî1ñòðàíñòâå H = R :2J(u) = u → inf,Î÷åâèäíî, ÷òîu∗ = 1.u = x,U = [1, 2].Ïîëó÷èì ýòîò ðåçóëüòàò ñ ïîìîùüþ(1).Äëÿ íàøåãî ñëó÷àÿñêàëÿðíîå ïðîèçâåäåíèå åñòü ïðîñòî åñòåñòâåííîå óìíîæåíèå, ïîýòîìó íåîáõîäè-(1) ÿâëÿåòñÿ íåðàâåíñòâî 2u∗ (u − u∗ ) > 0,êîòîðîå äîëæíî âûïîëíÿòüñÿ äëÿ ëþáîãî u èç îòðåçêà [1, 2].

Òàê êàê u∗ ìîæåòáûòü òîëüêî èç [1, 2], òî íåîáõîäèìî äîëæíî âûïîëíÿòüñÿ u − u∗ > 0 îïÿòü æå äëÿëþáîãî u èç îòðåçêà [1, 2]. Îòñþäà ïîëó÷àåì, ÷òî u∗ = 1.ìûì óñëîâèåì îïòèìàëüíîñòè âñëåäñòâèåH = F = L2 [0, π], J(u) = ||Au||2L2 [0,π] , ãäå äåéñòâèå îïåðàòîðà A ∈ L(L2 → L2 )rtu(s)ds. Äîêàæåì îãðàíè÷åííîñòü J :îïðåäåëÿåòñÿ ñîîòíîøåíèåì (Au)(t) =2) Ïóñòü0||Au||2 =äëÿ ëþáîãîwπwt00u.!2u(s)dsdt 6 π!2wtu(s)ds6 {Êîøè-Áóíÿêîâñêèé}π 2 ||u||20Ïðîâåðèì, èìååò ëè ìåñòî ñèëüíàÿ âûïóêëîñòü:2||Ah|| =Íî ìîæåò ëè äëÿ âñåõhwπwt00!2h(s)dsáûòü åäèíàÿκκw 22h (s)ds.dt > ||h|| =22 0πκ?Ðàññìàòðèâàÿhk = sin(kx), k = 1, 2, .

. .,óáåæäàåìñÿ, ÷òî ïðàâàÿ ÷àñòü ñòðåìèòñÿ ê íóëþ, â òî âðåìÿ êàê ëåâàÿ - êîíñòàíòà.5Òàêèì îáðàçîì, ñèëüíàÿ âûïóêëîñòü íå èìååò ìåñòî .3) Ðåøèì ñëåäóþùóþ çàäà÷ó îïòèìàëüíîãî óïðàâëåíèÿ â ïðîñòðàíñòâåJ(u) =w4x(t) + u2 (t) dt → inf ,U0U = {u ∈ L2 (0, 4) |u(t)| 6 1x0 (t) = u(t),x(0) = 0.L2 (0, 4):ïî÷òè âñþäó},0<t<4UÄëÿ íà÷àëà çàìåòèì, ÷òî ìíîæåñòâîâûïóêëî çàìêíóòî è îãðàíè÷åíî è, ñëåäî2âàòåëüíî, ÿâëÿåòñÿ ñëàáûì êîìïàêòîì â L (0, 4).Ðàçîáü¼ì ôóíêöèîíàëJ(u)J(u) =íà äâà èíòåãðàëà:w40x(t) dt +w4u2 (t) dt ≡ J1 (u) + J2 (u)05 Îòìåòèì, ÷òî õîòÿ îïåðàòîð ëèíååí, îáðàòèì, ýòó íåïðèÿòíîñòü îáóñëàâëèâàåò òîò ôàêò, ÷òî îáðàòíûé îïåðàòîð íå íåïðåðûâåí.30ÔóíêöèÿJ1 (u)âûïóêëà êàê ëèíåéíàÿ ïîâûïóêëà ñ êîýôôèöèåíòîìκ = 2.u.ÔóíêöèÿÎòñþäà ïîëó÷àåì,J2 (u) = kuk2L2 (0,2)÷òî J(u) ÿâëÿåòñÿñèëüíîñèëüíîâûïóêëûì è ïî Òåîðåìå 6 ñóùåñòâóåò åäèíñòâåííî îïòèìàëüíîå óïðàâëåíèå.Âîñïîëüçóåìñÿ íåîáõîäèìûì óñëîâèåì(1) äëÿ íàõîæäåíèÿ îïòèìàëüíîãî óïðàâëå-íèÿ.hJ 0 (u∗ ), u − u∗ iL2 ≥ 0 ∀u ∈ U(∗)J 0 (u∗ ) â íàøèõ îáîçíà÷åíèÿõ ïðåäñòàâèìî êàê J10 (u∗ ) + J20 (u∗ ), ïðè ýòîì J20 (u∗ ) =2u∗ .

Åñëè áû ìû ïðåäñòàâèëè J1 (u) â êàíîíè÷åñêîì âèäå J1 = hc, ui (âèäå Ðèññà),0òî J1 (u) = c.J1 (u) =w4x(t, u) dt =w4c(t)u(t) dt == {èíò.x(t)·1 dt =ïî ÷àñòÿì}=−w40x (t)(t − 4) dt =x(t)(t − 4)0 dt =w4u(t)(t − 4) dt.00Òàêèì îáðàçîì, ïîëó÷àåì, ÷òîw40000w4J10 (t) = c(t) = 4−t. Òîãäà óñëîâèå (∗) ïåðåïèñûâàåòñÿâ âèäåw4((4 − t) + 2u∗ (t)) · (u(t) − u∗ (t)) dt > 0 ∀u ∈ U.0Âîñïîëüçóåìñÿ òåì, ÷òî ýòî íåðàâåíñòâî äîëæíî âûïîëíÿòüñÿ äëÿ ëþáûõðàññìîòðèì ñëåäóþùåå ñåìåéñòâî ôóíêöèé, ïðèíàäëåæàùèõu(t) =ãäåvëþáîå ÷èñëî èç îòðåçêàu èç U èU:u∗ (t), t ∈ [0, 4]\(t0 − ε, t0 + ε)v, t ∈ (t0 − ε, t0 + ε)[−1, 1], ε > 0Òàêèì îáðàçîì, ìû çàìåíèëè îïòèìàëüíîå óïðàâëåíèå ôóíêöèåé, îòëè÷íîé îò îïòèìàëüíîé, ëèøü íà èíòåðâàëå(t0 − ε, t0 + ε),íà êîòîðîì îíà ïðèíèìàåòñÿ ðàâíîéäîïóñòèìîé êîíñòàíòå.

Ýòîò ìåòîä íàçûâàþò ìåòîäîìÒîãäà äëÿ ëþáîãî ïîëîæèòåëüíîãîεè ëþáîãîèãîëü÷àòûõ âàðèàöèé.v ∈ [−1, 1]óñëîâèå(∗)ïåðåïèñûâà-åòñÿ â âèäåtw0 +ε((4 − t) + 2u∗ (t)) · (u(t) − u∗ (t)) dt > 0t0 −εÒåïåðü âîñïîëüçóåìñÿ òåîðåìîé î äèôôåðåíöèðóåìîñòè èíòåãðàëà Ëåáåãà (ñì., íà-2ε è óñòðåìèì ε ê 0.(4 − t0 + 2u∗ (t0 )) · (v − u∗ (t0 )) > 0.ïðèìåð, [ÊÔ, ãë.VI, Ÿ6]). Ðàçäåëèì ïîëó÷åííîå íåðàâåíñòâî íàÄëÿ ïî÷òè âñåõt0èç èíòåðâàëà(0, 4)ïîëó÷èìÂîçìîæíû íåñêîëüêî âàðèàíòîâ.31i)Ïðåäïîëîæèì, ÷òîèíòåðâàëà[0, 2)4 − t0 + 2u∗ (t0 ) > 0.âûïîëíÿòüñÿ óñëîâèåt0 ∈ [0, 2)ii)Òàê êàêu∗ (t0 ) ∈ [−1, 1],òî ïðèt0èçýòî íåðàâåíñòâî áóäåò âûïîëíåíî.

Òîãäà íåîáõîäèìî äîëæíîv − u∗ > 0 ⇔ v > u∗v ∈ [−1, 1].u∗ (t) ≡ −1.äëÿ ëþáîãîîïòèìàëüíûì ÿâëÿåòñÿ óïðàâëåíèåÎòñþäà ïðè4 − t0 + 2u∗ (t0 ) < 0, òî v − u∗ (t) 6 0 ∀v ∈ [−1, 1] è ìû ïîëó÷àåì, ÷òîu∗ (t) ≡ 1, íî ýòî ïðîòèâîðå÷èò òîìó, ÷òî 4 − t0 + 2u∗ (t0 ) < 0. Çíà÷èò ýòîòÅñëèâàðèàíò èñêëþ÷¼í.iii)Îñòàëîñü ðàññìîòðåòü ñëó÷àé, êîãäàt−4.ïðè t0 ∈ [2, 4] u∗ (t) =24 − t0 + 2u∗ (t0 ) ≡ 0.Òîãäà ïîëó÷àåì, ÷òîÇàäà÷à ïîëíîñòüþ ðåøåíà.u62q4q−1 qtu∗ (t)Ðèñ. 7:u∗ (t)Ìåòðè÷åñêàÿ ïðîåêöèÿ ýòîì ïóíêòåM ìåòðè÷åñêîå ïðîñòðàíñòâî,Îïðåäåëåíèå. Ïðîåêöèåé prU (v)òî÷êèvρ(x, y)U ⊂ M.U íàçûâàåòñÿ argmin ρ(u, v) ìåòðèêà,íà ìíîæåñòâîu∈U(â íåêîòîðûõ ñëó÷àÿõ âûãîäíåå ðàññìàòðèâàòü ïðîåêöèþ êàêÇàìåòèì, ÷òî â ñëó÷àå, êîãäàUargmin ρ2 (u, v)).u∈Uíå âûïóêëî, ïðîåêöèÿ òî÷êè, âîîáùå ãîâîðÿ, ìîæåòáûòü íå åäèíñòâåííîé (ñì. ðèñ. 8).p P1VpUp P2Ðèñ.

8: ïðèìåð ïðîåêöèè íà íåâûïóêëîå ìíîæåñòâîÄëÿ íåêîòîðûõ ìíîæåñòâ ïðîåêöèè òî÷êè íà íèõ âîîáùå íå ñóùåñòâóåò. Íàïðèìåð,åñëè ðàññìîòðåòü îòêðûòûé øàðU = {kuk < 1} è òî÷êó âíå ýòîãî øàðà, òî îíà íå áóäåòèìåòü ïðîåêöèþ íà ýòî ìíîæåñòâî (ñì. ðèñ. 9).32Vp∈UÐèñ. 9: ïðèìåð îòñóòñòâèÿ ïðîåêöèèÒåîðåìà 12 (ñóùåñòâîâàíèå è åäèíñòâåííîñòü ïðîåêöèè è å¼ ñâîéñòâà).Ïóñòü H ãèëüáåðòîâî ïðîñòðàíñòâî, U âûïóêëîå çàìêíóòîå ìíîæåñòâî, òîãäà1) äëÿ ëþáîãî ýëåìåíòà h èç H ñóùåñòâóåò åäèíñòâåííàÿ prU (h);p ∈ U,2) p = prU (h) ⇔(ñì. ðèñ.

10);hp − h, u − piH > 0 ∀u ∈ U3) k prU (f ) − prU (g)kH 6 kf − gkH ∀f, g ∈ H. Ýòî ñâîéñòâî íàçûâàþò íåñòðîãîéñæèìàåìîñòüþ îïåðàòîðà ïðîåêòèðîâàíèÿ (ñì. ðèñ. 11).Äîêàçàòåëüñòâî.J(u) = ku − hk2H . Îíà ñèëüíî âûïóêëà (κ = 2). Ìíîæåñòâî Uïî óñëîâèþ. Îòñþäà ïî Òåîðåìå 6 ñëåäóåò, ÷òî J∗ êîíå÷íî è1) Ðàññìîòðèì ôóíêöèþâûïóêëî è çàìêíóòîU∗ = {u∗ } =6 ∅,òî åñòü ïåðâîå óòâåðæäåíèå òåîðåìû.2) Âòîðîå óòâåðæäåíèå ÿâëÿåòñÿ ñëåäñòâèåì ïðèìåíåíèÿ Òåîðåìû 9 ê ýòîé æå ôóíêöèè.3) Ïóñòüpf = prU (f ), pg = prU (g).Òîãäà, ïðèìåíÿÿ âòîðîå óòâåðæäåíèå äâà ðàçà,èìååì:hpf − f, u − pf iH > 0hpg − g, u − pg iH > 0Ïðèìåì çàuâ ïåðâîì íåðàâåíñòâåpg ,à âî âòîðîìpfè ñëîæèì èõhpf − f − pg + g, pg − pf iH > 0èëè ïî-äðóãîìóhpf − pg , pg − pf iH + hg − f, pg − pf iH > 0.Òîãäà â ñèëó íåðàâåíñòâà Êîøè-Áóíÿêîâñêîãî:kg − f kH ·kpg − pf kH > hg − f, pg − pf iH > hpf − pg , pg − pf iH > kpg − pf k2H .Ðàçäåëèì ýòî íåðàâåíñòâî íàkpg − pf kH 6= 0(åñëèp g = pfäîêàçûâàåìîå íåðàâåí-ñòâî, î÷åâèäíî, âûïîëíÿåòñÿ) è ïîëó÷èì òðåòüå óòâåðæäåíèå òåîðåìû.33uαhU*pÐèñ.

10: ê ï. 2 Òåîðåìû 10fpppfgpppgUpf = pgfgÐèñ. 11: ê ï. 3 Òåîðåìû 10Òåîðåìà ïîëíîñòüþ äîêàçàíà.Óïðàæíåíèå 13 (5).íîå ïîäïðîñòðàíñòâî èçH ãèëüáåðòîâî ïðîñòðàíñòâî, L çàìêíóòîå ëèíåéH. Äîêàçàòü, ÷òî prL åñòü ëèíåéíûé îãðàíè÷åííûé ñàìîñîïðÿÏóñòüæ¼ííûé îïåðàòîð (îïåðàòîð îðòîãîíàëüíîãî ïðîåêòèðîâàíèÿ).Óïðàæíåíèå 14 (4).íîå ïîäïðîñòðàíñòâî èçH ãèëüáåðòîâî ïðîñòðàíñòâî, L çàìêíóòîå ëèíåéH, x0 ∈ H ôèêñèðîâàííàÿ òî÷êà.

Äîêàçàòü, ÷òî (ñì. óòâ. 2ÏóñòüÒåîðåìû 10)p = prx0 +L h ⇔p ∈ x0 + Lhp − h, li = 0 ∀l ∈ L.Ïðèìåðû íà âû÷èñëåíèå ïðîåêöèé.H: U = {u ∈ H | ku − u0 kH 6 R, u0 ∈ H}. Íå îãðàíè÷èâàÿîáùíîñòè ðàññóæäåíèé, ìîæíî ñ÷èòàòü, ÷òî u0 = 0. Ðàññìîòðèì òî÷êó h 6∈ U. Òîãäà3ïî àíàëîãèè ñ ãåîìåòðè÷åñêèì ïðîñòðàíñòâîì R ïðåäïîëîæèì, ÷òî ïðîåêöèÿ ýòîéòî÷êè íà ìíîæåñòâî U ðàâíà:1) ÏóñòüU øàð âprU (h) = Rh.khkHÄîêàæåì ýòî, èñïîëüçóÿ óòâåðæäåíèå 2) Òåîðåìû 10.

Äëÿ ýòîãî ðàññìîòðèì ñêà-34ëÿðíîå ïðîèçâåäåíèå hRkhk2Hh− h, u − R=− 1 × hh, uiH − RRkhkHkhkH HkhkHkhkHÒàê êàêh 6∈ U, òî khkH > R, à çíà÷èò ïåðâûé ìíîæèòåëü ýòîãî ïðîèçâåäåíèÿ îòðè-öàòåëåí. Âî âòîðîì ìíîæèòåëå ðàñïèøåì ñêàëÿðíîå ïðîèçâåäåíèå ïî íåðàâåíñòâóÊîøè-Áóíÿêîâñêîãî:hh, uiH 6 khkH ·kukH 6 R·khkH .Îòñþäà ñëåäóåò, ÷òî îí íåïîëîæèòåëåí, òî åñòü âñ¼ ñêàëÿðíîå ïðîèçâåäåíèå îêàçûâàåòñÿ íåîòðèöàòåëüíûì è âûïîëíÿåòñÿ âòîðîå óñëîâèå Òåîðåìû 10. Òàêèì îáðàçîì, íàøå ïðåäïîëîæåíèå îêàçàëîñü âåðíûì.U = {u(t) ∈ L2 (a, b) | α(t) 6 u(t) 6 β(t); α(t), β(t) ∈ L2 } ïàðàë2ëåëåïèïåä â L . Äëÿ íàõîæäåíèÿ ïðîåêöèè ôóíêöèè h(t) (íå ïðèíàäëåæàùåé U,òàê êàê â ïðîòèâíîì ñëó÷àå ïðîåêöèÿ ïðîñòî áóäåò ðàâíà h(t)) íà U íåîáõîäèìî2) Ðàññìîòðèììèíèìèçèðîâàòü íîðìó:ku(t) −h(t)k2L2wb=|u(t) − h(t)|2 dt → inf .u∈UaÏðîåêöèÿ â ýòîì ñëó÷àå, êàê íåòðóäíî âèäåòü, áóäåò ðàâíà: h(t),β(t),[prU (h(t))] (t) =α(t),Óïðàæíåíèå 15 (3).Íàéòè ïðîåêöèè1) â ãèëüáåðòîâîì ïðîñòðàíñòâå2) â ïðîñòðàíñòâåRnt : α(t) 6 h(t) 6 β(t),t : h(t) > β(t),t : h(t) < α(t).Híà ãèïåðïëîñêîñòüíà ïàðàëëåëåïèïåäU = {u ∈ H : hc, uiH = β};U = {u ∈ Rn : αi 6 ui 6 βi , i = 1, n}.Ïóñòü H ãèëüáåðòîâîïðîñòðàíñòâî, U âûïóêëîå çàìêíóòîå ìíîæåñòâî, J(u) ∈ C1 (U), J(u) âûïóêëà.Òîãäàu∗ = argmin J(u) ⇔ ∀α > 0 u∗ = prU (u∗ − αJ 0 (u∗ )).Òåîðåìà 13 (ïðîåêöèîííàÿ ôîðìà êðèòåðèÿ îïòèìàëüíîñòè).u∈UÄîêàçàòåëüñòâî.Ïî Òåîðåìå 9 èìååì, ÷òîu∗ÿâëÿåòñÿ òî÷êîé ìèíèìóìà òîãäà è òîëüêî òîãäà, êîãäàhJ 0 (u∗ ), u − u∗ i > 0 ∀u ∈ U.Óìíîæèì ýòî íåðàâåíñòâî íàïðèáàâèì è âû÷òåìα>0è â ïåðâîì àðãóìåíòå ñêàëÿðíîãî ïðîèçâåäåíèÿu∗ :hu∗ − (u∗ − αJ 0 (u∗ )), u − u∗ i > 0.Ýòî íåðàâåíñòâî ïî ï.2 Òåîðåìû 10 âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäàu∗ = prU (u∗ − αJ 0 (u∗ )).Òåîðåìà äîêàçàíà.355Èòåðàöèîííûå ìåòîäû ìèíèìèçàöèèÌåòîä ñêîðåéøåãî ñïóñêàÐàññìîòðèì äîñòàòî÷íî îáùóþ çàäà÷ó ìèíèìèçàöèè:J(u) → inf,u ∈ H.(1)Äëÿ å¼ ðåøåíèÿ â äàííîì ìåòîäå ñòðîèòñÿ ñëåäóþùàÿ èòåðàöèîííàÿ ïîñëåäîâàòåëüíîñòü:uk+1 = uk − αk J 0 (uk ), k = 0, 1, 2, .

. . ; α > 0Äëÿ íà÷àëà ïðîöåññà èòåðèðîâàíèÿ íåîáõîäèìî çàäàòü(2)u0 ∈ H. Ñïîñîáîâ, äëÿ âûáîðàu0 â îáùåì ñëó÷àå íå ñóùåñòâóåò è â îñíîâíîì çäåñü èñõîäÿò èç êàêèõ-ëèáî ýìïèðè÷åñêèõäàííûõ è ïîëàãàþòñÿ íà îïûò.Êðèòåðèè îñòàíîâêè ïðîöåññà ïðèáëèæåííîãî íàõîæäåíèÿ ìèíèìóìà ìîãóò áûòü îñíîâàíû íà ðàçëè÷íûõ ñîîáðàæåíèÿõ.

Ïðèâåä¼ì íåêîòîðûå èç íèõ:1)kuk+1 − uk k 6 ε1 ;2)kJ(uk+1 ) − J(uk )k 6 ε2 ;3)kJ 0 (uk )k 6 ε3 .(εi âûáèðàþòñÿ, èñõîäÿ èç òðåáîâàíèé ê ðåøåíèþ). Îáû÷íî íà ïðàêòèêå ïðèìåíÿþòêîìáèíàöèè ýòèõ îöåíîê.Âûáîð øàãà ñïóñêàαkâ îáùåì ñëó÷àå òàêæå íå åäèíñòâåíåí (ïðè÷¼ì íà êàæäîì øàãåîí ìîæåò áûòü âçÿò ïî-ðàçíîìó). Èíîãäà ìåòîäå ñêîðåéøåãî ñïóñêàαkαk áåðóò íå çàâèñÿùèì îò k : αk = α ≡ const > 0.îïðåäåëÿåòñÿ êîíêðåòíûì îáðàçîì:αk = argmin J(uk − αJ 0 (uk )).(3)α>0J(uk − αJ 0 (uk )).0Çàìåòèì, ÷òî â ïðè òàêîì âûáîðå αk , åñëè uk+1 = uk , òî ëèáî αk = 0, ëèáî J (uk ) = 0.0Ñëó÷àé J (uk ) = 0 ÿâëÿåòñÿ íåîáõîäèìûì óñëîâèåì ìèíèìóìà è ïðîöåññ èòåðèðîâàíèÿìîæíî îñòàíîâèòü.