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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

ðåøåíèå çàäà÷èâ ñëó÷àåψt + ψxx = 0,ψ(t, 0) = ψ(t, l) = 0,ψ(T, l) = y(T, x, u) − f (x),(9),2. ðåøåíèå çàäà÷èâ ñëó÷àåψt + ψxx = −y(t, x, u) + f (x),ψ(t, 0) = ψ(t, l) = 0,ψ(T, l) = 0),(8).Äîêàçàòåëüñòâî.Ñëó÷àé (8) ðàññìàòðèâàåòñÿ ñîâåðøåííî àíàëîãè÷íî (9).Óïðàæíåíèå 12 (5).ÍàéòèJ(u) =xïåðâóþ ïðîèâçîäíóþ ôóíêöèîíàëîâ2|y(t, x, u) − f (t, x)| dx, J(u) =y|y(T, x, u − f (x)|2 dx,0Qãäåwl- ðåøåíèåut = uxx , (t, x) ∈ Q = (0, T ) × (0, l),yx (t, 0) = yx (t, l) = 0,yt (0, x) = u(x).4Ýëåìåíòû âûïóêëîãî àíàëèçàÍàïîìíèì îïðåäåëåíèå âûïóêëîé ôóíêöèè.Îïðåäåëåíèå.ÔóíêöèÿJ(u)íàçûâàåòñÿâûïóêëîéíà âûïóêëîì ìíîæåñòâåJ(αu + (1 − α)v) 6 αJ(u) + (1 − α)J(v) ∀u, v ∈ U, ∀α ∈ [0, 1].È ââåä¼ì íåñêîëüêî íîâûõ ïîíÿòèé:22U,åñëèÎïðåäåëåíèå.ÔóíêöèÿJ(u)íàçûâàåòñÿñòðîãî âûïóêëîé,åñëèJ(αu + (1 − α)v) < αJ(u) + (1 − α)J(v) ∀u, v ∈ U, u 6= v, ∀α ∈ (0, 1).Îïðåäåëåíèå.ÔóíêöèÿJ(u)íàçûâàåòñÿñèëüíî âûïóêëîéñ êîýôôèöèåíòîìκ > 0,åñëèκJ(αu + (1 − α)v) 6 αJ(u) + (1 − α)J(v) − α(1 − α)ku − vk226∀u, v ∈ U, ∀α ∈ [0, 1].6--íåñòðîãî âûïóêëàÿíåâûïóêëàÿ ôóíêöèÿôóíêöèÿ66exx2--ñòðîãî, íî íå ñèëüíîñèëüíî âûïóêëàÿâûïóêëàÿ ôóíêöèÿôóíêöèÿ ñκ=1Ðèñ.

5: ê îïðåäåëåíèþ âûïóêëîñòè ôóíêöèèÒåîðåìà 7 (î ëîêàëüíîì ìèíèìóìå âûïóêëîé ôóíêöèè).ëîå, ôóíêöèÿ J(u) âûïóêëà íà U, J∗ > −∞, òîãäà:Ïóñòü ìíîæåñòâî U âûïóê-1) ëþáàÿ òî÷êà ëîêàëüíîãî ìèíèìóìà J(u) íà U ÿâëÿåòñÿ òî÷êîé ãëîáàëüíîãî ìèíèìóìà;2) åñëè U∗ 6= ∅, òî U∗ âûïóêëî;3) åñëè U∗ 6= ∅, à J(u) ñòðîãî âûïóêëà, òî U∗ = {u∗ } (ñîñòîèò èç îäíîãî ýëåìåíòà).Äîêàçàòåëüñòâî.Ïóñòü òî÷êà u∗ ∈ U òî÷êà ëîêàëüíîãî ìèíèìóìà, ò.å.∃ε > 0 : ∀u ∈ U ∩ {ku − u∗ k 6 ε} ⇒ J(u) > J(u∗ ).23Ôèêñèðóåì ëþáóþ òî÷êóαèç îòðåçêà[0, α0 ]v ∈ U,òîãäà ñóùåñòâóåò òàêîåα0 , 0 < α0 < 1,÷òî äëÿ ëþáîãîâûïîëíåíî óñëîâèåu∗ + α(v − u∗ ) ∈ U ∩ {ku − u∗ k 6 ε}.Èìååì:J(u∗ ) 6 J(u∗ + α(v − u∗ )) 6 {îïð.âûïóêëîé ôóíêöèè}αJ(u∗ ) 6 αJ(v),Îòñþäà ñëåäóåò, ÷òîïðè÷¼ìα > 0,6 (1 − α)J(u∗ ) + αJ(v).òàêèì îáðàçîì, äîêàçàíî ïåðâîåóòâåðæäåíèå òåîðåìû.Äîêàçàòåëüñòâî âòîðîãî óòâåðæäåíèÿ òåîðåìû ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ.Äëÿ äîêàçàòåëüñòâà òðåòüåãî óòâåðæäåíèÿ, ïðåäïîëîæèì, ÷òî âìåíòv∗ 6= u∗ ,òîãäà äëÿ ëþáîãîαèç èíòåðâàëà(0, 1)J∗ = J(αu∗ + (1 − α)v∗ ) < {ò.ê.

J{z}|∈U∗ (ïîU∗ñóùåñòâóåò ýëå-áóäåì èìåòü:ñòðîãî âûïóêëà}<)ï.2< αJ(u∗ ) + (1 − α)J(v∗ ) = {v∗ , u∗ ∈ U} = J(v∗ ) = J∗ .Ïîëó÷èëè ïðîòèâîðå÷èå è òåîðåìà ïîëíîñòüþ äîêàçàíà.Ïóñòü H ãèëüáåðòîâî ïðîñòðàíñòâî, ìíîæåñòâî U ⊂ H âûïóêëî è çàìêíóòî (íå îáÿçàòåëüíî îãðàíè÷åíî!), ôóíêöèÿ J(u) ñèëüíî âûïóêëà ñ êîýôôèöèåíòîì κ è ïîëóíåïðåðûâíà ñíèçó íà U(ò.å.

è ñëàáî ïîëóíåïðåðûâíà ñíèçó) òîãäà:Òåîðåìà 8 (ñèëüíî âûïóêëûé âàðèàíò òåîðåìû Âåéåðøòðàññà).1) J∗ > −∞;2) U∗ = {u∗ } =6 ∅;3) ∀u ∈ U κ2 ku − u∗ k2H 6 J(u) − J(u∗ ).Äîêàçàòåëüñòâî.Çàôèêñèðóåì ëþáóþ òî÷êóu0èçUè ðàññìîòðèì ìíîæåñòâîM(u0 ) = {u ∈ U|J(u) 6 J(u0 )}.Äîêàæåì, ÷òîM(u0 )âûïóêëî, çàìêíóòî è îãðàíè÷åíî.Âûïóêëîñòü ñëåäóåò èç âûïóêëîñòèUèJ(u).Äëÿäîêàçàòåëüñòâàçàìêíóòîñòèðàññìîòðèìëþáóþïîñëåäîâàòåëüíîñòü∞{uk }k=1 ⊂ M(u0 ), ñõîäÿùóþñÿ ê íåêîòîðîé òî÷êå u. Íåîáõîäèìî äîêàçàòü, ÷òî òî÷êàu ïðèíàäëåæèò ìíîæåñòâó M(u0 ).

Òàê êàê U çàìêíóòî, òî òî÷êà u ∈ U, èJ(u) 6 {Jï.í. ñíèçó}6 lim J(uk ) 6 {J(uk ) 6 J(u0 )∀k} 6 J(u0 ).k→∞Òàêèì îáðàçîì, çàìêíóòîñòü äîêàçàíà.24M (u0 ) == M1 ∪ M2M2puM1pu0R=2Ðèñ. 6: ìíîæåñòâîÒåïåðü äîêàæåì, ÷òîM(u0 )Mîãðàíè÷åíî. Äëÿ ýòîãî ðàçîáü¼ì ýòî ìíîæåñòâî íà äâà(ñì. ðèñ. 6):M(u0 ) = (M(u0 ) ∩ {ku − u0 k 6 2}) ∪ (M(u0 ) \ M1 ).|{z}|{z}M1ÌíîæåñòâîM1M2îãðàíè÷åíî (ïî ïîñòðîåíèþ), òî åñòü íàì íåîáõîäèìî äîêàçàòü îãðà-M2 .Äëÿ ëþáîé òî÷êè u èç M2 u ∈ U, J(u) 6 J(u0 ), ku − u0 k > 2. Âîçüì¼ì ÷èñëî1α = ku−u∈ (0, 12 ), 1 − α ∈ ( 12 , 1), òîãäà äëÿ òî÷êè v = u0 + α(u − u0 ) ∈ M1 âûïîë0k| {z }íè÷åííîñòü ìíîæåñòâàk·k=1<2íÿåòñÿ íåðàâåíñòâîJ(v) 6 {J(u) ñèëüíîâûïóêëà}κ6 (1 − α)J(u0 ) + αJ(u) − α(1 − α)ku − u0 k2 .2Îòñþäà, ïåðåãðóïïèðîâàâ ñëàãàåìûå è ó÷òÿ îãðàíè÷åíèÿ íàα,ïîëó÷àåì, ÷òîκku − u0 k 6 J(u0 ) − J(v).4Íîv ∈ M1 ,à äëÿ ýòîãî ìíîæåñòâà (òàê êàê îíî âûïóêëî, çàìêíóòî è îãðàíè÷åíî)4(J(u0 )−J1∗ )âûïîëíåíà Òåîðåìà 2: J1∗ = inf J(u) > −∞ è ìû èìååì ku − u0 k 6.κu∈M1Òàêèì îáðàçîì, ìíîæåñòâîM2(à çíà÷èò è âñ¼ ìíîæåñòâîM)îãðàíè÷åíî è ïåðâîåóòâåðæäåíèå òåîðåìû ïîëíîñòüþ äîêàçàíî.Âòîðîå óòâåðæäåíèå òåîðåìû ñëåäóåò íåïîñðåäñòâåííî èç Òåîðåìû 5.Äîêàæåì òðåòüå óòâåðæäåíèå.

ÈìååìJ(u∗ ) 6 J(u∗ + α(u − u∗ )) 6 {J(u) ñèëüíî{z}|âûïóêëà}6∈Uκ6 αJ(u) + (1 − α)J(u∗ ) − α(1 − α)ku − u∗ k22Îòñþäà ñëåäóåò, ÷òîκα(1 − α)ku − u∗ k2 6 αJ(u) + (1 − α)J(u∗ ) − J(u∗ ) = α[J(u) − J(u∗ )]2òî åñòü,κ(12− α)ku − u∗ k2 6 J(u) − J(u∗ ).Óñòðåìëÿÿæäåíèå.25αê íóëþ, ïîëó÷àåì òðåòüå óòâåð-Òåîðåìà 9 (êðèòåðèé âûïóêëîñòè äëÿ äèôôåðåíöèðóåìûõ ôóíêöèé). Ïóñòü H ãèëüáåðòîâî ïðîñòðàíñòâî, ìíîæåñòâî U ⊂ H âûïóêëî, J(u) ∈ C1 (U). Òîãäà ñëåäóþùèåóòâåðæäåíèÿ ýêâèâàëåíòíû:(a) J(u) âûïóêëà;(b) J(u) > J(v) + hJ 0 (v), u − viH∀u, v ∈ U;(c) hJ 0 (u) − J 0 (v), u − viH > 0 ∀u, v ∈ U.Åñëè, êðîìå òîãî, J(u) ∈ C2 (U) è intU 6= ∅, òî ýêâèâàëåíòíû óòâåðæäåíèÿ (a)−(c)è óòâåðæäåíèå(d) hJ 00 (u)·h, hiH > 0 ∀u ∈ U, ∀h ∈ H.Äîêàçàòåëüñòâî.Äëÿ íà÷àëà ïðîâåä¼ì öåïî÷êó äîêàçàòåëüñòâ ïî ñõåìå1)(a) ⇒ (b) ⇒ (c) ⇒ (a).(a) ⇒ (b)Ïî îïðåäåëåíèþ âûïóêëîé ôóíêöèè:J(αu + (1 − α)v) 6 αJ(u) + (1 − α)J(v).Ïåðåãðóïïèðóåì ñëàãàåìûå è ïîëó÷èì:αJ(u) > αJ(v) + [J(v + α(u − v)) − J(v)].Ïðèìåíèì ê âûðàæåíèþ â êâàäðàòíûõ ñêîáêàõ ôîðìóëó êîíå÷íûõ ïðèðàùåíèé:αJ(u) > αJ(v) + hJ 0 (v + θα(u − v)), α(u − v)iH , θ ∈ [0, 1].Òåïåðü ðàçäåëèì îáå ÷àñòè íåðàâåíñòâà íà α > 0 è óñòðåìèì α ê íóëþ.

Òàê êàêJ 0 (u) íåïðåðûâíà ïî óñëîâèþ, ìû ïîëó÷èì, ÷òî äëÿ ëþáûõ u, v ∈ U:J(u) > J(v) + hJ 0 (v), u − viH ,ò.å. óòâåðæäåíèå2)(b).(b) ⇒ (c)Çàïèøåì óñëîâèå(b)äëÿ ëþáûõ äâóõ òî÷åêu, v ∈ U:J(u) > J(v) + hJ 0 (v), u − viHJ(v) > J(u) + hJ 0 (u), v − uiH ,è ñëîæèì äâà ýòèõ íåðàâåíñòâà:J(u) + J(v) > J(v) + J(u) + hJ 0 (v) − J 0 (u), u − viHÎòñþäà íåïîñðåäñòâåííî ñëåäóåò óòâåðæäåíèå26(c).3)(c) ⇒ (a)Îáîçíà÷èì ÷åðåçwâûðàæåíèåαu + (1 − α)v.Òîãäà:αJ(u) + (1 − α)J(v) − J(αu + (1 − α)v) = αJ(u) + (1 − α)J(v) − [αJ(w) + (1 − α)J(w)] == α(J(u) − J(w)) + (1 − α)(J(v) − J(w)) = {ôîðìóëà=αw1hJ 0 (w + t(u − w)), u − wiH dt + (1 − α)w1êîíå÷íûõ ïðèðàùåíèé}=hJ 0 (w + t(v − w)), v − wiH dt.00Çàìåòèì, ÷òîu−w = (1−α)(u−v), v −w = α(v −u) è, ïðîäîëæàÿ öåïî÷êó ðàâåíñòâ,ïîëó÷èì, ÷òî ïðåäûäóùåå âûðàæåíèå ðàâíîα(1 − α)w1hJ 0 (w + t(u − w)) − J 0 (w + t(v − w)), u − viH dt.0x âûðàæåíèå w + t(u − w), à ÷åðåç y âûðàæåíèå w + t(v − w),òî u−v áóäåò ðàâíÿòüñÿ (x−y)/t, ãäå t > 0.

Òîãäà â ýòèõ îáîçíà÷åíèÿõ ïðåäûäóùèéÅñëè îáîçíà÷èòü ÷åðåçèíòåãðàë ðàâåíw1 1hJ 0 (x) − J 0 (y), x − yiH dt > 0.t0Òàêèì îáðàçîì, èìïëèêàöèÿ(c) ⇒ (a)Äîêàæåì òåïåðü, ÷òî èç óòâåðæäåíèÿóòâåðæäåíèåäîêàçàíà.(c) ñ äîïîëíèòåëüíûìè îãðàíè÷åíèÿìè ñëåäóåò(d).u ∈ intU è ëþáîå h ∈ H.ε ∈ [0, ε0 ] òî÷êà u + εh ∈ U. ÈìååìÔèêñèðóåì ëþáîåëþáîãîÒîãäà ñóùåñòâóåò òàêîåε0 > 0,÷òî äëÿhJ 0 (u + εh) − J 0 (u), εhiH > 0.Ïðèìåíèì ê ïåðâîìó àðãóìåíòó ñêàëÿðíîãî ïðîèçâåäåíèÿ ôîðìóëó êîíå÷íûõ ïðèðàùå2íèé (çäåñü ó÷èòûâàåòñÿ, ÷òî J(u) ∈ C (U)):hJ 00 (u + θεh)εh, εhiH > 0 θ = θ(ε) ∈ [0, 1].ε2 è óñòðåìèì ε ê íóëþ. Òîãäà, ó÷òÿ, ÷òî J 00 (u) íåïðåðûâíà,ïîëó÷èì, ÷òî óòâåðæäåíèå (d) âûïîëíåíî äëÿ âñåõ u ∈ intU.Òåïåðü ïðèìåíèì ñâîéñòâî âûïóêëûõ ìíîæåñòâ: intU = intU (çäåñü îíî ïðèâîäèòñÿáåç äîêàçàòåëüñòâà, ñì., íàïðèìåð, [ÀÒÔ, ñòð.216-217]).

Èìååì, ÷òî (d) âûïîëíÿåòñÿ äëÿâñåõ u ∈ U ∩ intU = U ∩ U = U.Äëÿ çàâåðøåíèå äîêàçàòåëüñòâà òåîðåìû äîêàæåì, ÷òî âûïîëíåíèå óñëîâèÿ (d) âëå÷¼ò çà ñîáîé (c), à ýòî ñëåäóåò èç òîãî, ÷òîÐàçäåëèì ýòî íåðàâåíñòâî íàhJ 0 (u) − J 0 (v), u − viH = {Óïðàæíåíèå 6} = hJ 00 (v + θ(u − v))(u − v), u − viH > 0.Òàêèì îáðàçîì, òåîðåìà ïîëíîñòüþ äîêàçàíà.27Îòìåòèì, ÷òî, ãåîìåìòðè÷åñêè, óñëîâèåäâà òî÷êè ãðàôèêà, ëåæèò âûøå ãðàôèêà.(a) îçíà÷àåò, ÷òî ëþáàÿ õîðäà, ñîåäèíÿþùàÿ(b) íàçûâàåòñÿ ìîíîòîííîñòüþ ãðàäèåíòà, à câ ñêàëÿðíîì ñëó÷àå îçíà÷àåò ïðîñòî çíàê âòîðîé ïðîèçâîäíîé.Àíàëîãè÷íûì îáðàçîì ìîæíî äîêàçàòü ïîäîáíóþ òåîðåìó äëÿ ñëó÷àÿ ñèëüíîé âûïóêëîñòè. Ïðèâåä¼ì å¼ ôîðìóëèðîâêó.ÏóñòüH ãèëüáåðòîâî ïðîñòðàíñòâî, ìíîæåñòâî U ⊂ H âûïóêëî, J(u) ∈ C1 (U).

Òîãäàñëåäóþùèå óòâåðæäåíèÿ ýêâèâàëåíòíû:Òåîðåìà 10 (êðèòåðèé ñèëüíîé âûïóêëîñòè äëÿ äèôôåðåíöèðóåìûõ ôóíêöèé).(a0 ) J(u) ñèëüíî âûïóêëà ñ êîýôôèöèåíòîì κ > 0;(b0 ) J(u) > J(v) + hJ 0 (v), u − viH + κ2 ku − vk2H(c0 ) hJ 0 (u) − J 0 (v), u − viH > κku − vk2H∀u, v ∈ U;∀u, v ∈ U.Åñëè, êðîìå òîãî, J(u) ∈ C2 (U) è intU 6= ∅, òî ýêâèâàëåíòíû óòâåðæäåíèÿ (a0 ) −(c ) è óòâåðæäåíèå0(d0 ) hJ 00 (u)·h, hiH > κkhk2H∀u ∈ U, ∀h ∈ H.Äîêàçàòåëüñòâî.Ïî ñóòè, íåîáõîäèìî ïîâòîðèòü äîêàçàòåëüñòâî Òåîðåìû 7, ó÷èòûâàÿ ñèëüíóþ âûïóêëîñòü.

Ïðåäîñòàâèì ýòî ÷èòàòåëþ.Ïðèâåä¼ì ïðèìåð, ïîêàçûâàþùèé, ÷òî óñëîâèåintU 6= ∅ â ïóíêòàõ (d) è (d0 ) Òåîðåì 7è 8 âàæíî.U = {y = 0} â ïðîñòðàíñòâå R2 (u = (x, y), U âûïóêëî,intU = ∅) è ôóíêöèþ J(u) = x2 − y 2 . J(u) ∈ C2 è ñèëüíî âûïóêëà, îäíàêî î÷åâèäíî, ÷òîÐàññìîòðèì ìíîæåñòâîå¼ âòîðàÿ ïðîèçâîäíàÿ00J (u) =íå óäîâëåòâîðÿåò íè óñëîâèþ(d),200 −2íè óñëîâèþ(d0 ).Ïðèìåðû ïðèìåíåíèÿ Òåîðåì 7 è 8.1)J(u) = hc, ui ëèíåéíàÿ ôóíêöèÿ, âûïóêëàÿ, íî íå ñèëüíî. J 00 (u) = 0,0âåíñòâî (d) âûïîëíÿåòñÿ, íî ïðè ýòîì íåðàâåíñòâî (d ) íå âûïîëíÿåòñÿ.2)J(u) = kAu − f k2F ,A ∈ L(H → F), f ∈ Fò.å. íåðà- êâàäðàòè÷íûé ôóíêöèîíàë, êàêèçâåñòíî âûïóêëûé (äîêàçàíî âûøå). Äîêàæåì ýòî ïî-äðóãîìó ïðèìåíÿÿ Òåîðåìó 7.J 00 (u) = 2A∗ A ∈ L(H → H)hJ 00 (u)h, hiH = h2A∗ Ah, hiH = 2kAhk2F > 0 ∀h ∈ H.Òî åñòü óñëîâèå(d) òî æå âðåìÿJ(u)âûïîëíÿåòñÿ. ñèëüíî âûïóêëûé ñ êîýôôèöèåíòîìòîãäà, êîãäà2 hA∗ Ah, hiH > κkhk2H28∀h ∈ H.κ>0òîãäà è òîëüêîÍà àëãåáðàè÷åñêîì ÿçûêå ýòî îçíà÷àåò ñóùåñòâîâàíèå îáðàòíîãî îïåðàòîðà(A∗ A)−1 ∈ L(H → H).Òî åñòü, åñëèdet(A∗ A) 6= 0,òî ñèëüíàÿ âûïóêëîñòü åñòü, à â ïðîòèâíîì ñëó÷àåñèëüíîé âûïóêëîñòè íåò.Äîêàæåì òåïåðü îäíó èç îñíîâíûõ òåîðåì êóðñà.Òåîðåìà 11 (óñëîâèÿ îïòèìàëüíîñòè â ôîðìå âàðèàöèîííîãî íåðàâåíñòâà).Ïóñòü ìíîæåñòâî U âûïóêëî, J(u) ∈ C1 (U).

Òîãäà1) åñëè u∗ = argmin J(u), òî hJ 0 (u∗ ), u − u∗ i > 0 ∀u ∈ U (1);u∈U2) åñëè u∗ ∈ intU, òî J 0 (u∗ ) = 0;3) åñëè âûïîëíÿåòñÿ (1), à J(u) âûïóêëà, òî u∗ = argmin J(u).u∈UÄîêàçàòåëüñòâî.1) Òàê êàêUu èç U íàéä¼òñÿ òàêîå ÷èñëî α0 ∈ [0, 1],u∗ + α(u − u∗ ) áóäåò ïðèíàäëåæàòü U.

Характеристики

Список файлов лекций