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

. . , gm (u0 ) < 0. Äëÿ äîêàçàòåëüñòâà ýòîãî ôàêòà ïðåäïîëîæèì, ÷òî∗∗â íåêîòîðîì (íåíóëåâîì) íàáîðå λ ïåðâàÿ êîîðäèíàòà λ0 ðàâíà íóëþ, òîãäà ôóíêöèÿÐàññìîòðèì ïðèìåð, â êîòîðîì212Ëàãðàíæà íà ýòîì íàáîðå ðàâíà:∗L(u0 , λ ) =mXλ∗i gi (u0 ) < 0 = L(u∗ , λ∗ ),i=1è ìû ïðèõîäèì ê ïðîòèâîðå÷èþ ñ ïðèíöèïîì ìèíèìóìà.61Ïðèâåä¼ì àíàëîã òåîðåìû Êóíà-Òàêêåðà â íåñêîëüêî èíîé ôîðìóëèðîâêå.

Äëÿ ýòîãîñíà÷àëà ââåä¼ì îäíîÎïðåäåëåíèå.Òî÷êàX, Y ìíîæåñòâà ïðîèçâîëüíîé ïðèðîäû. f : X × Y → R1 .(x∗ , y ) íàçûâàåòñÿ ñåäëîâîé òî÷êîé ôóíêöèè f íà ìíîæåñòâå X × Y, åñëèÏóñòü∗f (x∗ , y) 6 f (x∗ , y ∗ ) 6 f (x, y ∗ ) ∀x ∈ X, ∀y ∈ Y.Ïóñòü âûïîëíÿþòñÿ óñëîâèÿÒåîðåìû 22 è óñëîâèÿ ðåãóëÿðíîñòè Ñëåéòåðà. Òîãäà òî÷êà u∗ ïðèíàäëåæèò ìíîæåñòâó U∗ (u∗ îïòèìàëüíàÿ òî÷êà) òîãäà è òîëüêî òîãäà, êîãäà êëàññè÷åñêàÿ ôóíêöèÿËàãðàíæà (ñ λ0 = 1) èìååò ñåäëîâóþ òî÷êó (u∗ , λ∗ ) íà ìíîæåñòâå U0 × Rm+.Òåîðåìà 26 (ñåäëîâàÿ ôîðìà òåîðåìû Êóíà-Òàêêåðà).Äîêàçàòåëüñòâî.Äëÿ íà÷àëà ïåðåïèøåì îïðåäåëåíèå ñåäëîâîé òî÷êèJ(u∗ ) +mXλi gi (u∗ ) 6 J(u∗ ) +i=1J(u∗ ) +mX(u∗ , λ∗ ) äëÿ ôóíêöèè Ëàãðàíæà:λ∗i gi (u∗ ) ∀λ ∈ Rm+(a)λ∗i gi (u) ∀u ∈ U0(b)i=1mXλ∗i gi (u∗ )6 J(u) +i=1mXi=11) Íåîáõîäèìîñòü.u∗ ∈ U∗ .

Òîãäà ïî Òåîðåìå 22 ñ ó÷¼òîì óñëîâèé Ñëåéòåðà ñóùåñòâóåòλ = (1, λ∗1 , λ∗2 , . . . , λ∗m ) > 0, ÷òî óñëîâèå (b) íåïîñðåäñòâåííî âûòåêàåò èçi) ýòîé òåîðåìû, à óñëîâèå (a) ñëåäóåò èç ñëåäóþùåãî íåðàâåíñòâà:Ïóñòü òî÷êà∗òàêîé íàáîðóñëîâèÿmXi=1λi gi (u∗ ) 6 0 = {iii)} = J(u∗ ) +|{z}| {z }>060mXλ∗i gi (u∗ ).i=12) Äîñòàòî÷íîñòü.Ïóñòü â òî÷êåÈç(a)u∗ ∈ U0âûïîëíÿþòñÿ íåðàâåíñòâà(a)è(b).ñëåäóåò, ÷òîmX(λi − λ∗i )gi (u∗ ) 6 0 ∀λi > 0.i=1λ = (λ∗0 , λ∗1 , . .

. , λ∗i−1 , λ∗i + ε, λ∗i+1 , . . . , λ∗m ) (ε > 0), ìûåñòü gi (u∗ ) 6 0. Ïîñêîëüêó ýòî âåðíî äëÿ ëþáîãî i, òîÏîäñòàâèâ â ýòî âûðàæåíèåïîëó÷èì, ÷òîεgi (u∗ ) 6 0, òîu∗ ∈ U.îòñþäà ñëåäóåò, ÷òîλ = (λ∗0 , λ∗1 , . . . , λ∗i−1 , 0, λ∗i+1 , . . . , λ∗m ), òî áóäåì èìåòü0, òî åñòü λ∗i gi (u∗ ) = 0.

Îïÿòü æå èç òîãî, ÷òî ýòîâåðíî äëÿ ëþáîãî i, ïîëó÷àåì óñëîâèå iii) Òåîðåìû 22.Èç (b) íåïîñðåäñòâåííî ñëåäóåò óñëîâèå i).Åñëè ïîäñòàâèòü â ýòî âûðàæåíèå∗−λi gi (u∗ ) 6 0, íî λ∗i > 0, à gi (u∗ ) 6Òåïåðü îñòàëîñü ïðèìåíèòü óòâåðæäåíèå Òåîðåìû 22 îòíîñèòåëüíî äîñòàòî÷íîñòè èòåîðåìà äîêàçàíà.62Ïðàâèëî ìíîæèòåëåé Ëàãðàíæà äëÿ ãëàäêèõ çàäà÷ ýòîì ïóíêòå ðàññìàòðèâàåòñÿ çàäà÷à ìèíèìèçàöèè ñ îãðàíè÷åíèÿìè:J(u) → infãäåHu ∈ U = {u ∈ H | g1 (u) 6 0, . . .

, gm (u) 6 0,gm+1 (u) = 0, . . . , gm+s (u) = 0},(1) ãèëüáåðòîâî ïðîñòðàíñòâî, ñ äîïîëíèòåëüíûìè òðåáîâàíèÿìè íà ãëàäêîñòüôóíêöèé. Çäåñü ìû êðàòêî ðàññìîòðèì ëèøü íåîáõîäèìîå óñëîâèå ëîêàëüíîãî ìèíèìóìà.Äëÿ íà÷àëà ââåä¼ì íåñêîëüêî ïîíÿòèé (íåêîòîðûå èç íèõ ïðèâåäåíû ëèøü â êà÷åñòâåíàïîìèíàíèÿ).òî÷êîé ëîêàëüíîãî ìèíèìóìà ôóíêöèè J(u),åñëè ñóùåñòâóåò òàêîå ïîëîæèòåëüíîå ÷èñëî ε, ÷òî äëÿ ëþáîé òî÷êè u ∈ Uε ∩ U, ãäåUε = {u : ku − u∗ k < ε}, âûïîëíÿåòñÿ óñëîâèå J(u∗ ) 6 J(u).Îïðåäåëåíèå. Ïóñòü X íîðìèðîâàííîå ïðîñòðàíñòâî, M ⊂ X, x0 ∈ M. Âåêòîðh ∈ X íàçûâàþò êàñàòåëüíûì êî ìíîæåñòâó M â òî÷êå x0 , åñëè ñóùåñòâóåò îòîáðàæåíèåϕ(t) : R1 → X, îáëàäàþùåå ñâîéñòâàìè:Îïðåäåëåíèå.Òî÷êà1)x0 + th + ϕ(t) ∈ M ;2)ϕ(t) = o(t),òî åñòüu∗íàçûâàåòñÿkϕ(t)kXt→0ïðèt → 0.Âîîáùå ãîâîðÿ, äëÿ íàøèõ öåëåé äîñòàòî÷íî ñóùåñòâîâàíèÿ îòîáðàæåíèÿ ïåðåâîäÿùåãî1â X íå âñþ äåéñòâèòåëüíóþ îñü R , à ëèøü êàêîé-ëèáî èíòåðâàë (−ε; ε) äëÿ íåêîòîðîãîε > 0.uv0 qÎáîçíà÷èì ÷åðåçTx0 MMâñå êàñàòåëüíûå âåêòîðû êî ìíîæåñòâóMâ òî÷êåx0 .Tx0 M F (x) =x0 qM0Ïðèâåä¼ì áåç äîêàçàòåëüñòâà îäíó òåîðåìó, êîòîðîé ìû â ïîñëåäñòâèè âîñïîëüçóåìñÿ.63Òåîðåìà (Ëþñòåðíèê).[ÀÒÔ, ñòð.

171-174] ÏóñòüX, Y áàíàõîâû ïðîñòðàíñòâà,îòîáðàæåíèå F : X → Y äèôôåðåíöèðóåìî ïî Ôðåøå, M = {x ∈ Xim F 0 (x0 ) = Y. Òîãäà Tx0 M = ker F 0 (x0 ).Óïðàæíåíèå 20 (4). Ïóñòü X = R2 , Y = R1 , F (x1 , x2 ) = x21èìååò âèä| F (x) = 0}, x0 ∈ M,− x42 ,ìíîæåñòâîMM = {(x1 , x2 ) | F (x1 , x2 ) = 0}, x0 = (0, 0).Tx0 M ;1) Íàéòè2) íàéòèker F 0 (0, 0);3) âûÿñíèòü, ñîâïàäàþò îíè èëè íåò è ïî÷åìó.Òåïåðü ñôîðìóëèðóåì è äîêàæåì îñíîâíóþ òåîðåìó ýòîãî ïóíêòà.Ïóñòü u∗ òî÷êà ëîêàëüíîãî ìèíèìóìà â çàäà÷å (1); J(u), gi (u) ∈ C1 (Uε )äëÿ íåêîòîðîãî ïîëîæèòåëüíîãî ε.

Òîãäà ñóùåñòâóåò íåíóëåâîé íàáîð ìíîæèòåëåéËàãðàíæà λ∗ = (λ∗0 , . . . , λ∗m+s ), îáëàäàþùèé ñëåäóþùèìè ñâîéñòâàìè:Òåîðåìà 27.i)L0u (u∗ , λ∗ ) = λ∗0 J 0 (u∗ ) +m+sXλ∗i gi0 (u∗ ) = 0i=1 óñëîâèå ñòàöèîíàðíîñòè ôóíêöèè Ëàãðàíæà ;ii)λ∗i > 0 ∀i = 0, m óñëîâèÿ íåîòðèöàòåëüíîñòè ìíîæèòåëåé Ëàãðàíæà ;iii)λ∗i gi (u∗ ) = 0 ∀i = 1, m óñëîâèÿ, äîïîëíÿþùèå íåæ¼ñòêîñòè .Äîêàçàòåëüñòâî.Äëÿ íà÷àëà äîãîâîðèìñÿ î íåêîòîðûõ ñîãëàøåíèÿõ.Âî-ïåðâûõ, êàê è â äîêàçàòåëüñòâå Òåîðåìû 22, íå îãðàíè÷èâàÿ îáùíîñòè, áóäåìñ÷èòàòü, ÷òîJ(u∗ ) = 0(d1).gi (u∗ ) = 0 ∀i = 1, m(d2).Âî-âòîðûõ, áóäåì ñ÷èòàòü, ÷òîÍà ñàìîì äåëå, ýòî íå ñòîëü ñèëüíîå îãðàíè÷åíèå, êàê ìîæåò ïîêàçàòüñÿ, òàê êàêïðè íåâûïîëíåíèè ýòîãî óñëîâèÿ, ìîæíî ðàññìîòðåòü äðóãóþ îêðåñòíîñòüUε ,÷òî èë-ëþñòðèðóåò ðèñóíîê. Ïîýòîìó ìû ðàññìàòðèâàåì ëèøü çàäà÷ó íà ãðàíèöå. Çàìåòèì, ÷òî,ïðèíèìàÿ ýòî ñîãëàøåíèå, ìû àâòîìàòè÷åñêè èçáàâëÿåì ñåáÿ îò äîêàçàòåëüñòâà ïóíêòàiii),òàê êàê îí, î÷åâèäíî, âûïîëíÿåòñÿ.64gi (u) = 0u∗gi (u) 6 0UεÂ-òðåòüèõ, äëÿ óäîáñòâà îáîçíà÷èì ÷åðåçg0 (u)ñàìó ôóíêöèþJ(u):g0 (u) = J(u)Äàëåå, ïóñòü(d3).G(u) = (gm+1 (u), .

. . , gm+s (u)) : H → Rs . Ïî óñëîâèþ òåîðåìû â òî÷êå u∗ýòà ôóíêöèÿ äèôôåðåíöèðóåìà ïî Ôðåøå, òî åñòü ñóùåñòâóåò ëèíåéíûé îãðàíè÷åííûé000sîïåðàòîð G (u∗ ) = (gm+1 (u∗ ), . . . , gm+s (u∗ )) ∈ L(H → R ).Âîçìîæíû òðè ñëó÷àÿ:1)im G0 (u∗ ) 6= Rs ;2)im G0 (u∗ ) = Rs , ker G0 (u∗ ) = {0}3)im G0 (u∗ ) = Rs , ker G0 (u∗ ) 6= {0}.(ñîñòîèò èç îäíîãî íóëÿ);Ðàññìîòðèì âñå òðè ýòèõ ñëó÷àÿ.1) Âûðîæäåííûé ñëó÷àé: ýòîì ñëó÷àå ïðîñòðàíñòâîim G0 (u∗ ) 6= RsRs ðàñêëàäûâàåòñÿíà ïðÿìóþ ñóììó ïîäïðîñòðàíñòâ(ñì. Óïðàæíåíèå 18):Rs = im G0 (u∗ ) ⊕ ker(G0 (u∗ ))∗ = {Rsêîíå÷íîìåðíî}Òàêèì îáðàçîì, íàéä¼òñÿ íåíóëåâîé âåêòîð= im G0 (u∗ ) ⊕ ker(G0 (u∗ ))∗ .λ0 ∈ ker(G0 (u∗ ))∗ ,äëÿ êîòîðîãî ñïðàâåä-ëèâî âûðàæåíèå:0 = (G0 (u∗ ))∗ [λ0 ] =m+sXλ0i gi0 (u∗ ).i=mÒåïåðü â êà÷åñòâå èñêîìîãî íàáîðà ìíîæèòåëåé Ëàãðàíæà äîñòàòî÷íî âçÿòü:λ∗ = (λ∗0 = 0, .

. . , λ∗m = 0, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ) 6= 0.Êàê íåòðóäíî âèäåòü, äëÿ ýòîãî íàáîðà âñå óòâåðæäåíèÿ òåîðåìû âûïîëíÿþòñÿ.2) Ïîëóâûðîæäåííûé ñëó÷àé:im G0 (u∗ ) = Rs , ker G0 (u∗ ) = {0}Àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ, èìååì ðàçëîæåíèå ïðîñòðàíñòâà0S(dim H 6 s). Òî åñòü íàéä¼òñÿ òàêîé âåêòîð λ ∈ R , ÷òî00∗0J (u∗ ) = (G (u∗ )) [λ ] =m+sXi=m+165λ0i gi0 (u∗ ).H = im(G0 (u∗ ))∗ êà÷åñòâå èñêîìîãî íàáîðàλ∗áåð¼ì ñëåäóþùèé:λ∗ = (λ∗0 = 1, λ∗1 = 0, .

. . , λ∗m = 0, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ) 6= 0.3) Íåâûðîæäåííûé ñëó÷àé:Îáîçíà÷èì ÷åðåçVkim G0 (u∗ ) = Rs , dim(ker G0 (u∗ )) > 1ìíîæåñòâà ñëåäóþùåãî âèäà:Vk = u ∈ H | G0 (u∗ )[u] = 0, hgi0 (u∗ ), ui < 0, i = k, mÇàìåòèì, ÷òî óñëîâèådim(ker G0 (u∗ )) > 1k = 0, m.â ýòîì ñëó÷àå âàæíî, òàê êàê èíà÷å âñåVkáûëè áû ïóñòûìè.Î÷åâèäíî, ÷òî ñïðàâåäëèâà öåïî÷êà âëîæåíèé:V0 ⊆ V1 ⊆ . . . ⊆ Vm .V0 = ∅.Äîêàæåì, ÷òîv ∈ V0 . Ýòîim G (u∗ ) = Rs , òîìåíò0Ïðåäïîëîæèì îáðàòíîå, òî åñòü, ÷òî ñóùåñòâóåò íåêèé ýëåv ∈ ker G0 (u∗ ) è hgi (u∗ ), vi < 0 äëÿ i = 0, m. Òàê êàê0ïî Òåîðåìå Ëþñòåðíèêà ïîëó÷àåì, ÷òî ker G (u∗ ) = Tu∗ {u | G(u) = 0}îçíà÷àåò, ÷òîϕ(t): (−ε, ε) → H òàêîå, ÷òî u∗ + tv + ϕ(t) ∈ {u | G(u) = 0},G(u∗ + tv + ϕ(t)) = 0 äëÿ ëþáîãî t èç èíòåðâàëà (−ε, ε).Òàêèì îáðàçîì, âñå òî÷êè âèäà u∗ + tv + ϕ(t) ≡ u(t) óäîâëåòâîðÿþò îãðàíè÷åíèÿìè ñóùåñòâóåò îòîáðàæåíèåòî åñòüòèïà ðàâåíñòâî.i = 0, mÒåïåðü äëÿ âñåõðàçëîæèì ôóíêöèègiâ îêðåñòíîñòè òî÷êèu∗ :gi (u(t)) = gi (u∗ ) + hgi0 (u∗ ), tv + ϕ(t)i + o(tv + ϕ(t)) == {(d1), (d2)} = t hgi0 (u∗ ), vi + o(t) < 0 ∀t ∈ (0, ε)Ìû ïîëó÷èëè, ÷òî äëÿìíîæåñòâóU,tèç èíòåðâàëàè â òîæå âðåìÿïîëîæåíèå íåâåðíî èJ(u(t)) < 0,(0, ε)òî÷êèu(t)ïðèíàäëåæàò äîïóñòèìîìó÷òî ïðîòèâîðå÷èò ñ(d1).Çíà÷èò íàøå ïðåä-V0 = ∅.Ðàññìîòðèì ñëó÷àé, êîãäà âñåViíå ñîäåðæàò ýëåìåíòîâ, òî åñòü êîãäà0Vm = {u ∈ H | G0 (u∗ )[u] = 0, hgm(u∗ ), ui < 0} = ∅.Ïîñòàâèì çàäà÷ó ìèíèìèçàöèè ôóíêöèîíàëà íà ÿäðå:0Jm (u) = hgm(u∗ ), ui → inf,ÅñëèVm = ∅,òîu=0 ðåøåíèå(2).u ∈ ker G0 (u∗ )(2)Ðàçëîæèì ãðàäèåíò â îðòîãîíàëüíóþ ñóììó:⊥21210∈ ker G0 (u∗ ), gm∈ (ker(G0 (u∗ ))gm(u∗ ) = gm+ gm, ãäå gm 1 1Jm (u) = gm, u ⇒ {min = 0} ⇒ gm=0Òàêèì îáðàçîì, ïîëó÷àåì, ÷òî0λ ∈ Rs , ÷òî0gm(u∗ ) ∈ im(G0 (u∗ ))0 ,01·gm(u∗ )=m+sXi=m66λ0i gi0 (u∗ ).è ñóùåñòâóåò òàêîé âåêòîðÒîãäà â êà÷åñòâå èñêîìîãî íàáîðà ìíîæèòåëåé Ëàãðàíæà ìîæíî âçÿòüλ∗ = (λ∗0 = 0, λ∗1 = 0, .

. . , λ∗m−1 = 0, λ∗m = 1, λ∗m+1 = −λ0m+1 , . . . , λ∗m+s = −λ0m+s ).Îñòà¼òñÿ ðàññìîòðåòü ñëó÷àé, êîãäà∅ = V0 = V1 = . . . = Vk ⊂ Vk+1 ⊆ Vk+1 ⊆ . . . ⊆ Vm .Àíàëîãè÷íî ïðåäûäóùèì ðàññóæäåíèÿì ïîñòàâèì çàäà÷ó ìèíèìèçàöèè:Jk (u) = hgk0 (u∗ ), ui → inf,è ïîêàæåì, ÷òîu=0 ðåøåíèå çàäà÷èinf< 0,Íåîáõîäèìî äîêàçàòü, ÷òîíîãî. Ïðåäïîëîæèì, ÷òîw ∈ Vk+1u ∈ {u ∈ ker G0 (u∗ ) | hgi0 (u∗ ), ui 6 0, i = k + 1, m}Jk∗(3)â(3)(3).íåîòðèöàòåëåí.

Ñäåëàåì ýòî ìåòîäîì îò ïðîòèâ-òîãäà íàéäóòñÿ äîïóñòèìûé äëÿ(3)âåêòîðvè âåêòîðòàêèå, ÷òîhgk0 (u∗ ), vi < 0, hgi0 (u∗ ), vi 6 0 äëÿ i = k + 1, m, G0 (u∗ )[v] = 0,hgk0 (u∗ ), wi < 0, gj0 (u∗ ), w < 0 äëÿ j = k + 1, m, G0 (u∗ )[w] = 0.Ñäâèíóâøèñü íà äîñòàòî÷íî ìàëîåεvèçâ íàïðàâëåíèèw,ïîëó÷èìhgk0 (u∗ ), v + εwi < 0,hgi0 (u∗ ), v + εwi 6 0è, òàê êàêGäëÿi = k + 1, mëèíååí,G0 (u∗ )[v + εw] = 0.Ìû ïîëó÷èëè, ÷òî òî÷êàv + εwñîäåðæèòñÿ âî ìíîæåñòâåæåíèþ ïóñòî. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò, ÷òîÒàê êàêv=0Vk ,êîòîðîå ïî ïðåäïîëî- ðåøåíèå.Vk+1 6= ∅ òî çàäà÷à (3) ÿâëÿåòñÿ âûïóêëîé çàäà÷åé, äëÿ êîòîðîé âûïîëíÿþòñÿ(3) Òåîðåìó 22.óñëîâèÿ Ñëåéòåðà.

Ïðèìåíèì êÏóñòü êëàññè÷åñêàÿ ôóíêöèÿ ËàãðàíæàLk (u, λ) =1· hgk0 (u∗ ), ui+mXλi hgi0 (u∗ ), uii=k+1000óäîâëåòâîðÿåò ïðèíöèïó ìèíèìóìà èç Òåîðåìû 22 ïðè λ = λ = (1, λk+1 , . . . , λm )0Òîãäà äëÿ ëþáîãî u ∈ ker G (u∗ ) (= U0 ) áóäåò âûïîëíÿòüñÿ íåðàâåíñòâî0=1· hgk0 (u∗ ), ui+mX6= 0.λ0i hgi0 (u∗ ), ui 6 Lk (u, λ0 ).i=k+1Òàê êàê ìíîæåñòâî òåðïèìûõ îãðàíè÷åíèé è ôóíêöèÿ Ëàãðàíæà ëèíåéíû, îòñþäà00ïîëó÷àåì, ÷òî Lk (u, λ ) = 0 äëÿ ëþáîãî u ∈ ker G (u∗ ) (âìåñòî u ìîæíî âçÿòü −u èïîëó÷èòü àíàëîãè÷íîå âåðíîå íåðàâåíñòâî).67Ìû ïîëó÷èëè, ÷òî1·gk0 (u∗ ) +mX⊥∗λ0i gi0 (u∗ ) ∈ (ker G0 (u∗ )) = im (G0 (u∗ )) ,i=k+1è ñóùåñòâóåò òàêîé íàáîð(λ0m+1 , . .