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

Ïðèâåäåì îäèí èçâîçìîæíûõ ìåòîäîâ åå íàõîæäåíèÿ, íàçûâàåìûé ìåòîäîì èñêóñòâåííîãî áàçèñà.Au = b âûïîëíåíî òðåáîâàíèå b > 0. Ïîñòàâèìz = (x, u) ∈ Rn+m (ãäå x m-ìåðåí, u n-ìåðíî),Ïóñòü â óñëîâèèçàäà÷ó: ïóñòüâñïîìîãàòåëüíóþg(z) = x1 + x2 + . . . + xm → min, z ∈ Z = {z ∈ Rn+m : x > 0, x + Au = b}.Ìû ïîëó÷èëè êàíîíè÷åñêóþ çàäà÷ó ëèíåéíîãî ïîãðàììèðîâàíèÿ, â êîòîðîé óãëîâîé òî÷-z0 = (b, 0).

Çàïóñòèì îò ýòîé òî÷êè ñèìïëåêñ-ìåòîä ñ àíòèöèêëèíîì. Ò.ê. g∗ = inf g > 0, òî çà êîíå÷íîå ÷èñëî øàãîâ ìû ïîëó÷èì òî÷êó z∗ - ðåçóëüòàòðàáîòû àëãîðèòìà, ò.å. g∗ = g(z∗ ). Çàìåòèì, ÷òî g∗ = 0 ðàâíîñèëüíî íåïóñòîòå ìíîæåñòâàU∗ .  òàêîì ñëó÷àå, z∗ = (0, u), è u - óãëîâàÿ òî÷êà. Ïðîâåðèì ýòî ïî îïðåäåëåíèþ: ïóñòüz∗ = αu1 + (1 − α)u2 , α ∈ (0, 1). Ïîëîæèì z1 = (0, u1 ), z2 = (0, u2 ), z∗ = αz1 + (1 − α)z2 ,∗÷òî âëå÷åò z = z1 = z2 è, ñëåäîâàòåëüíî, u1 = u2 .êîé, î÷åâèäíî, ÿâëÿåòñÿ êîíöå ïóíêòà ñôîðìóëèðóåì îáîáùàþùóþ íàøè ðàññóæäåíèÿ òåîðåìó.Òåîðåìà 23 (ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ).ðîâàíèÿ âûïîëíÿþòñÿ ñëåäóþùèå óòâåðæäåíèÿ: çàäà÷å ëèíåéíîãî ïðîãðàììè-1) åñëè U 6= ∅, òî â U ñóùåñòâóåò ïî êðàéíåé ìåðå îäíà óãëîâàÿ òî÷êà;2) åñëè J∗ > −∞, òî âî ìíîæåñòâå U∗ ñîäåðæèòñÿ ïî êðàéíåé ìåðå îäíà òî÷êà.Äîêàçàòåëüñòâî.Äîêàçàòåëüñòâî ýòîé òåîðåìû, ïî ñóòè, ïðèâîäèòñÿ â îáîñíîâàíèè ñèìïëåêñ-ìåòîäà(ïåðåáîðà ïî óãëîâûì òî÷êàì).Çàìå÷àíèå.Óòâåðæäåíèå 2) ñïðàâåäëèâî èìåííî äëÿ çàäà÷è ëèíåéíîãî ïðîãðàììè−uðîâàíèÿ.

 ïðîòèâíîì ñëó÷àå ýòî, âîîáùå ãîâîðÿ, íå âåðíî. Íàïðèìåð, åñëè1(ýòî íå çàäà÷à ëèíåéíîãî ïðîãðàììèðîâàíèÿ), òî U = R , J∗ = 0, íî U∗ = ∅.6J(u) = eÌåòîäû ñíÿòèÿ îãðàíè÷åíèé ýòîé ãëàâå ðàññìàòðèâàþòñÿ çàäà÷è ìèíèìèçàöèè ôóíêöèîíàëîâJ(u) → inf, u ∈ Uñ ó÷¼òîì îãðàíè÷åíèé íà ìíîæåñòâîU.Ýòè îãðàíè÷åíèÿ ìîãóò áûòü òåðïèìûìè, íàïðèìåð,u ìîæåò ïðèíàäëåæàòü íå âñå-ìó ïðîñòðàíñòâó, à êàêîìó-ëèáî ïîäìíîæåñòâó ýòîãî ïðîñòðàíñòâà. Òàêèå îãðàíè÷åíèÿìû íå ðàññìàòðèâàåì è ñ÷èòàåì, ÷òî èõ ìîæíî îáîéòè ïðîñòûìè ìåòîäàìè.Íàñ æå áóäóò èíòåðåñîâàòü áîëåå ôóíêöèîíàëüíûå îãðàíè÷åíèÿ íàu.Ðàññìîòðèìêîíêðåòíûé ïðèìåð:u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, .

. . , gm (u) 6 0, gm+1 (u) = 0, . . . , gm+s = 0},ãäågiêàêèå-ëèáî ôóíêöèè.56Çäåñü èíòåðåñóþùèå íàñ îãðàíè÷åíèÿ ýòîm îãðàíè÷åíèé òèïà íåðàâåíñòâîès îãðà-íè÷åíèé òèïà ðàâåíñòâî (òåðïèìûì îãðàíè÷åíèåì ÿâëÿåòñÿ ïðèíàäëåæíîñòü òî÷êèuU0 ).ìíîæåñòâóÅñòåñòâåííî, êàêèå-ëèáî èç îãðàíè÷åíèé ìîãóò îòñóòñòâîâàòü.Ìåòîä øòðàôîâ ýòîì ìåòîäå ðàññìàòðèâàåòñÿ çàäà÷à ìèíèìèçàöèè ñ îãðàíè÷åíèÿìè ñëåäóþùåãî âèäà:J(u) → inf, u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, . .

. , gm (u) 6 0,gm+1 (u) = 0, . . . , gm+s = 0}Ðàññìîòðèì ôóíêöèþ (íàçûâàåìóþP (u) =m+sXøòðàôîì(gi+ (u))pi ,èëè(1)øòðàôíîé ôóíêöèåé ):pi > 1 (îáû÷íî pi = 2).i=1Ôóíêöèègi+ (u) íàçûâàþò èíäèâèäóàëüíûìè øòðàôàìè.  êà÷åñòâå êîíêðåòíîãî ïðè-ìåðà ìîæíî âçÿòügi+ (u) = max{gi (u), 0}, i = 1, m,gi+ (u) = |gi (u)| , i = m + 1, m + s.Ëåãêî âèäåòü, ÷òî óñëîâèåP (u) = 0,u ∈ U0âûïîëíÿåòñÿ òîãäà è òîëüêî òîãäà, êîãäà òî÷êàÈç øòðàôíîé ôóíêöèèP (u)Φk (u) = J(u) + Ak P (u),Òåïåðü îò çàäà÷èuk ∈ U0(1)uïðèíàäëåæèò ìíîæåñòâóU.ôîðìèðóþòñÿ ôîðìóëû âèäàAk > 0, Ak → ∞ïðèk → ∞, u ∈ U0 , k = 1, 2, .

. .ìû ïåðåõîäèì ê ïîñëåäîâàòåëüíîñòè çàäà÷(2).(2)Ïóñòü òî÷êèòàêîâû, ÷òîΦk∗ ≡ inf Φk 6 Φk (uk ) 6 Φk∗ + εkU0(3)(èõ ìîæíî ïîëó÷èòü, íàïðèìåð, ìåòîäàìè, èçëîæåííûìè â ïðåäûäóùåé ãëàâå). Èñïîëüçóÿ ýòó ïîñëåäîâàòåëüíîñòü òî÷åê, ñôîðìóëèðóåì îñíîâíóþ òåîðåìó â ýòîì ïóíêòå.Ïóñòü H ãèëüáåðòîâî ïðîñòðàíñòâî, ìíîæåñòâî U0 ñëàáî çàìêíóòî;ñëàáî ïîëóíåïðåðûâíû ñíèçó íà U0 ; òî÷êàÒåîðåìà 24.J(u),gi+ (u)J0 = inf J(u)U0êîíå÷íà; ìíîæåñòâîU(δ) = {u ∈ U0 : gi+ (u) 6 δ, i = 1, m + s}57îãðàíè÷åíî â H äëÿ íåêîòîðîãî δ > 0; Ak → +∞, εk → +0, òîãäà ïîñëåäîâàòåëüíîñòüJ(uk ) ñòðåìèòñÿ ê ìèíèìóìó J(u):J(uk ) → inf(J(uk ) → J∗ ),è âñå ñëàáûå ïðåäåëüíûå òî÷êè ïîñëåäîâàòåëüíîñòè {uk } ñîäåðæàòñÿ âî ìíîæåñòâå U∗ .Äîêàçàòåëüñòâî.Ïðåæäå âñåãî äîêàæåì, ÷òî ïðè âûïîëíåíèè óñëîâèé òåîðåìû ïîñëåäîâàòåëüíîñòüAk > 0, P (u) > 0,ñóùåñòâóåò.

Äåéñòâèòåëüíî, ó÷èòûâàÿ, ÷òîukèìååì:Φk (u) = J(u) + Ak P (u) > {u ∈ U0 } > J0 > −∞,òî åñòü ôîðìóëû(3)èìåþò ñìûñë (ýòî âåðíî, êîãäàΦk∗êîíå÷íû).Äàëåå, ðàññìîòðèì öåïî÷êó íåðàâåíñòâ:J(uk ) 6 Φk (u) 6 {(3)} 6 Φk∗ + εk 6 {∀u ∈ U0 } 6 Φk (u) + εk .Ïîñëåäíåå íåðàâåíñòâî âåðíî äëÿ ëþáîãîuèçU0è, â ÷àñòíîñòè, äëÿ ëþáîãîuèçU. Âîçüì¼ì inf ïî ìíîæåñòâó U îò îáåèõ ÷àñòåé íåðàâåíñòâà, òîãäà ñïðàâàèìåòü J∗ + εk . Îòñþäà, ïåðåõîäÿ ê ïðåäåëó è ó÷èòûâàÿ, ÷òî εk → ∞ ïðè k → ∞,ìíîæåñòâàáóäåìïîëó÷àåì:lim J(uk ) 6 lim Φk (u) 6 lim Φk∗ 6 J∗k→∞k→∞Òåïåðü ðàññìîòðèì çíà÷åíèåΦk (u)(4)k→∞â òî÷êåuk :Φk (uk ) = J(uk ) + Ak P (uk ) 6 {(3)} 6 Φk∗ + εk .Φk∗ + εk − J(uk )Φk∗ + εk − J0c66 {(4)} 6→ 0.AkAkAkÎòñþäà, ó÷èòûâàÿ, ÷òî P (u) ñóììèðóþùèé øòðàô èç íåîòðèöàòåëüíûõ ýëåìåíòîâ+gi , ïîëó÷àåì, ÷òî êàæäûé èíäèâèäóàëüíûé øòðàô gi+ → 0, ïðè k → ∞.

Òàêèì îáðàçîì,äëÿ δ èç óñëîâèÿ òåîðåìû ñóùåñòâóåò òàêîé íîìåð k0 (δ), ÷òî äëÿ ëþáîãî íîìåðà k > k0gi+ 6 δ i = 1, m + s, òî åñòü uk ∈ U(δ). Òàê êàê H ãèëüáåðòîâî ïðîñòðàíñòâî, òîîòñþäà ïîëó÷àåì, ÷òî ó ïîñëåäîâàòåëüíîñòè {uk } ñóùåñòâóþò ñëàáûå ïðåäåëüíûå òî÷êè.Ïóñòü òåïåðü {ukl } òàêàÿ ïîäïîñëåäîâàòåëüíîñòü {uk }, ÷òîP (uk ) 6lim J(uk ) = lim J(ukl ) ∈ U(δ) ∀l > l0k→∞èu0(5)l→∞ îäíà èç ñëàáûõ ïðåäåëüíûõ òî÷åê{ukl }.Ó÷èòûâàÿ ñëàáóþ ïîëóíåïðåðûâíîñòü ñíèçó ôóíêöèéJ(u), gi+ (u), èìååì ñ îäíîé ñòî-ðîíûJ(u0 ) 6 lim J(ukl ) 6 J∗ ,l→∞òî åñòüJ(u0 )íå ïðåâîñõîäèò ìèíèìóìà íà äîïóñòèìîì ìíîæåñòâå0 6 gi+ (u0 ) 6 lim gi+ (ukl ) = 0l→∞58U;ñ äðóãîé ñòîðîíûè (òàê êàêìíîæåñòâóU0 ñëàáî çàìêíóòî) u0 ∈ U, òî åñòü òî÷êà u0 ïðèíàäëåæèò äîïóñòèìîìóU.

Òàêèì îáðàçîì, âîçìîæíà ëèøü ñèòóàöèÿ J(u0 ) = J∗ , òî åñòülim J(ukl ) = J∗ .l→∞ ñèëó ïðàâèëà âûáîðà(5):lim J(uk ) = J∗ ,k→∞è óòâåðæäåíèå òåîðåìû î ñõîäèìîñòè ïîñëåäîâàòåëüíîñòèJ(uk )ê ìèíèìóìó äîêàçàíî.Ñõîäèìîñòü ïî àðãóìåíòó ìîæíî äîêàçàòü àíàëîãè÷íî, ëèáî îïèðàÿñü íà äîêàçàòåëüñòâî Òåîðåìû 2.Óïðàæíåíèå 18 (4). Äîêàçàòü, ÷òî ïðè âûïîëíåíèè óñëîâèé Òåîðåìû 21 çàäà÷à (1)ÿâëÿåòñÿ ñëàáî êîððåêòíî ïîñòàâëåííîé â ïðîñòðàíñòâåH.Ïðàâèëî ìíîæèòåëåé Ëàãðàíæà äëÿ âûïóêëûõ çàäà÷ ýòîì ïóíêòå ðàññìàòðèâàåì ñëåäóþùóþ çàäà÷ó ìèíèìèçàöèè:J(u) → inf,u ∈ U = {u ∈ U0 ⊂ L | g1 (u) 6 0, . .

. , gm (u) 6 0}(1)Ìîæíî ðàññìîòðåòü è ñëó÷àé, êîãäà åñòü îãðàíè÷åíèÿ òèïà ðàâåíñòâî, íî ïðè ýòîìîíè îáÿçàíû áûòü ëèíåéíûìè (â ïðåäûäóùåì ìåòîäå íà òàêèå îãðàíè÷åíèÿ òàêæå íàêëàäûâàþòñÿ æ¼ñòêèå óñëîâèÿ â âèäå ñëàáîé ïîëóíåïðåðûâíîñòè ñíèçó, òàê ÷òî îíè ïî÷òèëèíåéíû).Íàçîâ¼ì çàäà÷ó(1) âûïóêëîé,ëèíåéíîå ïðîñòðàíñòâî, ôóíêöèèåñëè ìíîæåñòâîgiU0âûïóêëî,Lïðåäñòàâëÿåò ñîáîéâûïóêëû.Ïîñòðîèì ôóíêöèþ Ëàãðàíæà:L(u, λ) = λ0 J(u) +mXλi gi (u) (λ ∈ Rm+1 ).i=1×èñëàλiíàçûâàþòìíîæèòåëÿìè Ëàãðàíæà.Òåîðåìà 25 (òåîðåìà Êóíà-Òàêêåðà).ÒîãäàÏóñòü çàäà÷à (1) âûïóêëà â óêàçàííîì ñìûñëå.1) åñëè òî÷êà u∗ ÿâëÿåòñÿ îïòèìàëüíîé (u∗ ∈ U∗ ), òî ñóùåñòâóåò íàáîð ìíîæèòåëåé Ëàãðàíæà λ∗ 6= 0 òàêîé, ÷òîi)min L(u, λ∗ ) = L(u∗ , λ∗ ) ïðèíöèï ìèíèìóìà ;u∈U0ii)λ∗i > 0,i = 0, m óñëîâèÿ íåîòðèöàòåëüíîñòè ìíîæèòåëåé Ëàãðàíæà ;59iii)i = 1, m óñëîâèÿ, äîïîëíÿþùèå íåæ¼ñòêîñòè .λ∗i gi (u∗ ) = 0,2) åñëè äëÿ íåêîòîðîé ïàðû (u∗ , λ∗ ) âûïîëíÿþòñÿ óñëîâèÿ i)-iii) è, êðîìå òîãî,u∗ ∈ U è λ∗0 6= 0, òî u∗ îïòèìàëüíàÿ òî÷êà (u∗ ∈ U∗ ).Äîêàçàòåëüñòâî.1) Íåîáõîäèìîñòü.Óñëîâèìñÿ ñ÷èòàòü, ÷òîôóíêöèþ˜J(u)= J(u) − J∗ ,J(u∗ ) = J∗ = 0(â ïðîòèâíîì ñëó÷àå ìîæíî ðàññìîòðåòüà ôóíêöèÿ Ëàãðàíæà íå ðåàãèðóåò íà ñäâèã íà êîíñòàíòó).Ââåäåì ìíîæåñòâîM = {µ = (µ0 , .

. . , µm ) ∈ Rm+1 | ∃u ∈ U0 : J(u) < µ0 , gi (u) 6 µi , i = 1, m}.ÌíîæåñòâîMíå ïóñòî, òàê êàê â íåì ñîäåðæèòñÿ (ñ ó÷¼òîì äîãîâîð¼ííîñòè J∗ = 0),Rm+1(äëÿ òàêèõ µ ïîäõîäÿùåé òî÷êîé+ïî êðàéíåé ìåðå, âåñü ïîëîæèòåëüíûé îêòàíòáóäåòu∗ ∈ U0 ).ÌíîæåñòâîMâûïóêëî èç-çà âûïóêëîñòè èñõîäíûõ äàííûõ (óñëîâèÿ òåîðåìû).

Ýòîýëåìåíòàðíî äîêàçûâàåòñÿ ïî îïðåäåëåíèþ.Òàêæå ëåãêî äîêàçàòü, ÷òî ñ ó÷¼òîì äîãîâîð¼ííîñòè òî÷êàñòâó0íå ïðèíàäëåæèò ìíîæå-M.Ïî òåîðåìå îòäåëèìîñòè (ñì., íàïðèìåð, [Â2, ãë. 4,Ÿ5, Òåîðåìà 1]) ñóùåñòâóåò íåíóλ∗ òàêîé, ÷òîëåâîé âåêòîðhλ∗ , µiRm+1 > 0 = hλ∗ , 0iRm+1(λ∗∀µ ∈ M(2) íîðìàëüíûé âåêòîð ê ãèïåðïëîñêîñòè).Äîêàæåì äëÿ íà÷àëà óòâåðæäåíèåii).Âîçüì¼ì òî÷êóµiε = (ε, ε, . . . , 1, . . .

, ε), ε > 0,ãäå åäèíèöà ñòîèò âi-éïîçèöèè. Ýòà òî÷êà ïðèíàäëåæèò ìíîæåñòâóM(òàê êàê îíàíàõîäèòñÿ â ïîëîæèòåëüíîì îêòàíòå). Ïîäñòàâèâ å¼ â (2) è óñòðåìèâ ε ê íóëþ, ïîëó÷èì,∗÷òî λi > 0 äëÿ ëþáîãî i. Òàêèì îáðàçîì, óòâåðæäåíèå ii) äîêàçàíî.Òåïåðü äîêàæåì óòâåðæäåíèå iii).  ñëó÷àå, êîãäà gi (u∗ ) = 0, ýòî óòâåðæäåíèå, î÷åâèäíî, âåðíî. Ðàññìîòðèì ñëó÷àé, êîãäàgi (u∗ ) < 0.Áåð¼ì òî÷êóνεi = (ε, 0, . . .

, gi (u∗ ), 0, . . . , 0) ∈ M,ãäågi (u∗ )ñòîèò íài-îììåñòå. Ïîäñòàâèâ ýòó òî÷êó â(2),ïîëó÷èì:εJ(u∗ ) + λ∗i gi (u∗ ) > 0 ∀ε > 0.λ∗i gi (u∗ ) > 0.  òî æå âðåìÿ gi (u∗ ) < 0 è ïî äîêàçàííîìóλ∗i > 0. Îòñþäà ïîëó÷àåì óòâåðæäåíèå iii): λ∗i gi (u∗ ) = 0.Îñòàëîñü äîêàçàòü îñíîâíîå óòâåðæäåíèå i). Äëÿ ýòîãî çàôèêñèðóåì ëþáóþ òî÷êó uèç ìíîæåñòâà U0 è ïî íåé ïîñòðîèì ñåìåéñòâî âåêòîðîâ ηε = (J(u) + ε, g1 (u), .

. . , gm (u))Óñòðåìëÿÿεê íóëþ, èìååì60(ε> 0). Òî÷êà ηεM, òàê êàê ïîäõîäÿùèì u ∈ U0 â ýòîì ñëó÷àå(2) è óñòðåìëÿåì ε ê íóëþ. Èìååì:ñîäåðæèòñÿ âî ìíîæåñòâåu.ÿâëÿåòñÿ ñàìà òî÷êàÏîäñòàâëÿåì∗L(u, λ ) =λ∗0 J(u)+nXηεâλ∗i gi (u) > 0 = {äîïóùåíèå,óòâ.ii)}=i=1=λ∗0 J(u∗ )+nXλ∗i gi (u∗ ) = L(u∗ , λ∗ ).i=1Óòâåðæäåíèåi)äîêàçàíî.2) Äîñòàòî÷íîñòü.∗Ïóñòü òî÷êà u∗ ∈ U, λ0 6= 0.

 ýòîì ñëó÷àå, íå îãðàíè÷èâàÿ îáùíîñòè, ìîæíî ñ÷èòàòü,∗÷òî λ0 = 1, òàê êàê ôóíêöèþ Ëàãðàíæà ìîæíî äåëèòü/óìíîæàòü íà ïîëîæèòåëüíîå÷èñëî. Òîãäà èìååì:J(u∗ ) = 1·J(u∗ ) +nXi=1λ∗i gi (u∗ ) = L(u∗ , λ∗ ) 6 {i)} 6 L(u, λ∗ ).| {z }=0Ïîñëåäíåå íåðàâåíñòâî âåðíî äëÿ ëþáîãîuèçU0è, â ÷àñòíîñòè äëÿ ëþáîãîuèçU.Äàëåå.∗L(u, λ ) = 1·J(u) +nXλ∗i gi (u) 6 {λ∗i > 0 (óòâ. ii)) , gi (u) 6 0 (u ∈ U)} 6 J(u) ∀u ∈ U.i=1Òàê êàêu∗ñîäåðæèòñÿ â äîïóñòèìîì ìíîæåñòâåU,òî îòñþäà ïîëó÷àåì, ÷òîu∗îïòèìàëüíàÿ òî÷êà è äîñòàòî÷íîñòü äîêàçàíà.Óïðàæíåíèå 19 (5).æåñòâà â ïðîñòðàíñòâåÄîêàçàòü òåîðåìó îá îòäåëèìîñòè òî÷êè îò âûïóêëîãî ìíî-nR .Çàìå÷àíèå î ðåãóëÿðíîñòèλ∗0 = 0.

Ïóñòü H = R1 , J(u) = −u → inf, U0 = R1 ,g1 (u) = u , U = {u ∈ R | u 6 0} = {0} = U∗ . Äîêàæåì, ÷òî â ëþáîì íàáîðå λ∗ = (λ∗0 , λ∗1 )∗∗∗îáÿçàòåëüíî λ0 = 0. Ïî Òåîðåìå 22 íàéä¼òñÿ íåîòðèöàòåëüíûé íàáîð (λ0 , λ1 ) òàêîé, ÷òî∗∗ 2áóäåò âûïîëíÿòüñÿ óñëîâèå i): −λ0 u + λ1 u > 0∀u ∈ R1 .∗∗Ðàçäåëèì ýòî íåðàâåíñòâî íà u > 0: −λ0 + λ1 u > 0 ∀u > 0, è óñòðåìèì u ê íóëþ.∗Ïîëó÷èì −λ0 > 0.∗Îòñþäà ñ ó÷¼òîì óñëîâèÿ íåîòðèöàòåëüíîñòè ìíîæèòåëåé Ëàãðàíæà èìååì λ0 = 0.Äîñòàòî÷íûì óñëîâèåì íà ðåãóëÿðíîñòü ÿâëÿåòñÿ ñóùåñòâîâàíèå òî÷êè u0 ∈ U0 òàêîé, ÷òî g1 (u0 ) < 0, .