Základy podmíněné matematické optimalizace Zpracoval Doc. RNDr. Zdeněk Hlaváč, CSc
V tématu nepodmíněné optimalizace jsme na pohyb bodu v prostoru nezávisle proměnných nekladli žádná omezení. V případě podmíněné optimalizace se tento prostor omezuje na přípustnou množinu P definovanou pomocí omezujících funkcí. Definice: Přípustnou množinu definujeme jako P = {x; gi (x) ≤ 0; i = 1, . . . , m} .
(1)
Funkce gi se nazývají omezující funkce a říkáme, že přípustná množina je definovaná pomocí nerovnicových omezení. Poznámka: Takto definovaná přípustná množina obsahuje ve většině případů vnitřní body (v topologii prostoru Rn ). Definice: Přípustnou množinu definujeme také jako P = {x; hj (x) = 0; j = 1, . . . , p} .
(2)
Funkce hj se rovněž nazývají omezující funkce a říkáme, že přípustná množina je definovaná pomocí rovnicových omezení. Poznámka: Takto definovaná přípustná množina zřejmě nemá vnitřní body (v topologii prostoru Rn ). Definice: Říkáme, že funkce f (x) definovaná na P má v bodě x0 ∈ P ostré lokální minimum vzhledem k P , jestliže existuje δ > 0 tak, že pro všechna x ∈ Uδr (x0 ) ∩ P je f (x) > f (x0 ). Poznámka: Pro případ definice ostrého lokálního maxima funkce vzhledem k množině platí v závěru definice obrácená nerovnice. V dalším výkladu budeme předpokládat, že přípustná množina je definovaná pomocí nerovnicových omezení (1). Definice: Směr určený jednotkovým vektorem d nazýváme přípustným směrem z bodu x0 (vzhledem k množině P ), jestliže existuje δ > 0 tak, že pro všechna t ∈ (0, δ) je bod x = x0 + td ∈ P . Množinu všech přípustných směrů z bodu x0 ∈ P ve smyslu této definice značíme D(x0 ). Definice: Směr určený jednotkovým vektorem d nazýváme spádovým směrem z bodu x0 (vzhledem k funkci f ) jestliže existuje δ > 0 tak, že pro všechna t ∈ (0, δ) je f (x0 + td) < f (x0 ). Množinu všech spádových směrů z bodu x0 ve smyslu této definice značíme S(x0 ). Intuitivně zřejmé je následující tvrzení: Bod x0 je ostrým lokálním minimem funkce f vzhledem k P definované v (1) právě když D(x0 ) ∩ S(x0 ) = ∅.
Poznámka: Tvrzení říká, že bod x0 je ostrým lokálním minimem právě když z něho neexistuje vycházející směr, jenž by byl současně spádový (vzhledem k f ) a přípustný 1
(vzhledem k P ). Pro diferencovatelnou funkci f v bodě x0 snadno nahlédneme, jak vypadá postačující podmínka spádovosti směru. Tvrzení: Nechť f je diferencovatelná v bodě x0 , d jednotkový vektor směru. Nechť platí dT gradf (x0 ) < 0 .
(3)
Potom d je spádovým směrem z bodu x0 (vzhledem k funkci f ). Poznámka: Víme totiž, že velikost výsledku levé strany nerovnice (3) je ||gradf (x0 )|| · ·cos ϕd , kde ϕd je úhel mezi směry danými vektorem d a vektorem gradf (x0 ). Podmínka zápornosti v předchozím tvrzení znamená, že ϕd ∈ ( π2 , π), takže směrový vektor d míří do poloprostoru (vyťatého tečnou nadrovinou k vrstevnici funkce f v bodě x0 ), kde hodnoty jsou (alespoň na malém okolí) nižší. Naopak směry, kde by zkoumané číslo bylo kladné, míří do opačného (otevřeného) poloprostoru, kde f (alespoň na malém okolí bodu x0 ) roste. Nejasná situace nastane, když vektor d míří do tečné nadroviny k vrstevnici funkce f v bodě x0 , tedy, když levá strana (3) je nulová. Pak mohou být všechny takové směry spádové, mohou být rovněž všechny takové směry růstové, mohou f = f2 f = f2
f = f2
f1
f1
f1 f = f1 f = f1
x0 f = f1
Obr.1a
x0 x0
Obr.1b
Obr. 1c
ale být i některé růstové a jiné spádové. Všechny tyto případy jsou na obr.1 po řadě zakresleny. Obrázek je kreslen pro funkci dvou proměnných, kde tečná nadrovina je tečnou (tedy přímkou) a směry, pro něž je dT gradf (x0 ) = 0 jsou právě dva. Na ve všech třech zobrazených případech jsou směry ”nad” tečnou k vrstevnici spádové, směry ”pod” tečnou k vrstevnici růstové. V situaci znázorněné na obr.1a jsou oba (červeně vyznačené) směry ve směru tečny k vrstevnici spádové, v situaci na obr.1b jsou oba tyto směry růstové a v situaci z obr.1c je jeden z těchto směrů růstový a druhý spádový. Pro funkce více proměnných by situace byla rozmanitější, protože směrů, pro něž je dT gradf (x0 ) = 0, je pak nekonečně mnoho. Definice: Říkáme, že omezení gi je v bodě x0 aktivní, jestliže platí gi (x0 ) = 0. Množinu všech indexů aktivních omezení v bodě x0 označujeme I(x0 ). Poznámka: Je-li omezení gi v bodě x0 aktivní, leží zmíněný bod na části hranice přípustné množiny, jež je popsaná právě omezením gi . Tvrzení: Nechť gi je v x0 diferencovatelná a I(x0 ) = {i}. Nechť dále pro směr reprezentovaný jednotkovým vektorem d platí dT gradgi (x0 ) < 0 .
(4)
Potom d je (z bodu x0 ) přípustným směrem vzhledem k množině P definované v (1).
2
Poznámka: 1. Jestliže je splněno (4), svírá vektor d s vektorem gradgi (x0 ) tupý úhel. Směr d tedy míří do toho poloprostoru (vyťatého tečnou nadrovinou k vrstevnici gi (x) = 0 v bodě x0 ), ve kterém leží množina P . Jestliže směrový vektor d splňuje opačnou relaci ke (4), míří mimo P . Je-li směrový vektor d k vektoru gradgi (x0 ) kolmý, záleží na konvexnosti hranice množiny P v okolí bodu x0 (obr.2). Na zmíněném obrázku jsou směry ”nad” tečnou k nulové vrstevnici omezující funkce nepřípustné, směry ”pod” tečnou přípustné a (dva červeně označené) směry kolmé ke gradientu omezující funkce jsou rovněž nepřípustné.
grad g i ( x 0)
x0 P
g i (x ) = 0
Obr.2 2. Pro případ více aktivních omezení je postačující podmínkou přípustnosti směru zřejmě platnost (4) pro všechna i ∈ I(x0 ). Není-li v bodě x0 aktivní žádné omezení (tedy I(x0 ) = ∅), je přípustný každý směr, neboť x0 pak leží v otevřeném vnitřku množiny P . Ukažme situaci na zadaném reliéfu vrstevnic funkce dvou proměnných f a zadaném popisu částí hranice přípustné množiny P . Situace nechť vypadá jako na obr.3. Přípustná množina P = {x; g1 (x) ≤ 0, g2 (x) ≤ 0} je definována pomocí dvou omezujících funkcí s vrstevnicemi odpovídajícími nulové konstantě (tedy s částmi hranice přípustné množiny) podle obrázku. Zeleně jsou značeny tečny k vrstevnicím cílové funkce (a příslušným obloučkem spádové směry), červeně tečny k vrstevnicím o nulové konstantě omezujících funkcí v bodech, kde je alespoň jedno omezení aktivní (a příslušným obloučkem přípustné směry). Protože na obrázku jsou vrstevnice cílové funkce i části hranice přípustné množiny zobrazeny jako konvexní funkce, vyplňují přípustné i spádové směry vždy jen otevřený poloprostor poklesu příslušejících funkcí. Na obrázku jsou znázorněny čtyři významné body. 1. Bod x1 je vnitřním bodem přípustné množiny, tudíž z něho jsou přípustné všechny směry. Spádové směry vyplňují poloprostor označený zeleně. Ten tvoří také poloprostor směrů, jež jsou současně přípustné i spádové. 2. V bodě x2 je aktivováno omezení g2 . Přípustné směry jsou označeny červeným obloučkem (otevřený poloprostor) a spádové zeleným obloučkem (opět otevřený poloprostor. Současně přípustné i spádové směry jsou dány otevřeným úhlem jakožto průnikem obou výše zmíněných poloprostorů. 3. V bodě x3 jsou aktivována obě omezení. Přípustné směry jsou dány průnikem poloprostorů přípustných směrů pro jedno každé omezení zvlášť (červeně označený otevřený úhel). Spádové směry jsou označeny zeleným obloučkem. Současně 3
f = f2 f = f3
f2
f1
x3
x2
f = f1
x1 g 2= 0
x4
g1= 0
Obr.3
přípustné i spádové směry tvoří oběma barvami označený otevřený úhel jakožto průnik obou výše diskutovaných úhlů. 4. V bodě x4 je aktivováno omezení g1 a poloprostor přípustných směrů (červený oblouček) má s poloprostorem spádových směrů (zelený oblouček) prázdný průnik. Je tedy D ∩ S = ∅. V bodě x4 tedy cílová funkce nabývá ostrého lokálního minima vzhledem k přípustné množině. Poznámka: Nechť nerovnicová omezení gi v (1) jsou pro i ∈ I(x0 ) diferencovatelná v bodě x0 . Označme symbolem D0 (x0 ) množinu všech směrů d, pro které jest dT gradgi (x0 ) ≤ 0 .
(5)
Pozor! Oproti (4) se zde vyskytuje neostrá nerovnice. Potom zřejmě platí D0 (x0 ) ⊂ D(x0 ) ⊂ D0 (x0 ) ,
kde D0 (x0 ) znamená uzávěr množiny D0 v topologii prostoru Rn . Platí pak následující důležité tvrzení. Tvrzení: Následující výroky jsou ekvivalentní: 1. S(x0 ) ∩ D0 (x0 ) = ∅ , 4
2. existují ui ≥ 0 takové, že gradf (x0 ) +
ui gradgi (x0 ) = 0 ,
X
(6)
i∈I(x0 )
3. existují ui ≥ 0 takové, že gradf (x0 ) +
m X
ui gradgi (x0 ) = 0
(7)
i=1
a zároveň
ui gi (x0 ) = 0 .
(8)
Poznámka: Tvrzení hovoří o gradientu cílové funkce f jako o lineární kombinaci gradientů v bodě x0 aktivních omezení s nekladnými koeficienty ui . Do bodu 3. byla zahrnuta všechna omezení (tedy i ta v bodě x0 neaktivní). Ta tam ale musela být zahrnuta s nulovými koeficienty ui . Proto k (7) musí být doplněny podmínky (8). Nazýváme je podmínkami komplementarity. Aktivní omezení v bodě x0 ovšem také může mít nulový koeficient ui lineární kombinace výše. Neaktivní omezení jej ovšem musí mít nulový. Tvrzení: Kuhnovy Tuckerovy nutné podmínky lokálního pomíněného minima: Nechť x0 je bod lokálního minima cílové funkce f vzhledem k množině (1). Nechť f a gi pro i ∈ I(x0 ) jsou v x0 diferencovatelné. Potom platí: 1. Existují nezáporné konstanty u0 a ui (ne všechny současně nulové), že u0 gradf (x0 ) +
X
ui gradgi (x0 ) = 0 .
(9)
i∈I
2. Existují nezáporné konstanty u0 a ui (ne všechny současně nulové), že u0 gradf (x0 ) +
m X
ui gradgi (x0 ) = 0
(10)
i=1
a zároveň
ui gi (x0 ) = 0 , i = 1, . . . , m .
(11)
3. Jsou-li navíc gradienty v bodě x0 aktivních omezení lineárně nezávislé, pak existují nezáporné (mohou být i všechny nulové) konstanty ui , že gradf (x0 ) +
m X
ui gradgi (x0 ) = 0
(12)
i=1
a zároveň platí (11).
Poznámka: Podmínkám (9) resp. (10) resp. (12) se říká podmínky stacionarity, podmínkám (11) podmínky komplementarity a podmínce nezávislosti gradientů aktivních omezení se říká podmínka regularity. 5
Poznámka: 1. Konstanta u0 v předchozím tvrzení může býti nenulová (potom jí celou rovnici podělíme, takže ji lze brát jednotkovou), nebo může býti nulová. Pak ovšem (9) resp. (10) vyjadřuje lineární závislost gradientů v x0 aktivních omezení (protože alespoň jedna z konstant ui jest nenulová). Do nutných podmínek minima tedy zahrnujeme i body lineární závislosti gradientů aktivních omezení. 2. Jestliže x0 leží uvnitř přípustné množiny, nejsou aktivní žádná omezení a (9) dává podmínku gradf (x0 ) = 0, tak jako u nepodmíněné minimalizace. Definice: Definujme funkci L(x, u) = L(x1 , . . . , xn , u0 , u1 , . . . , um ) = u0 f (x) +
m X
ui gi (x)
(13)
i=1
a nazveme ji Lagrangeovou funkcí úlohy pro cílovou funkci f a množinu P danou nerovnicovými omezeními gi . Podmínky stacionarity pak mají tvar gradx L(x, u) = u0 gradf (x) +
m X
ui gradgi (x) = 0 ,
(14)
i=1
kde gradx je gradient Lagrangeovy funkce tvořený pouze v proměnných x. Podmínky stacionarity a komplementarity představují celkem m + n rovnic pro stejný počet neznámých. Celkem n neznámých představují souřadnice stacionárního bodu cílové funkce a zbylých m neznámých jsou (pro u0 = 1) konstanty ui . Říkáme jim Lagrangeovy multiplikátory. Připomínáme, že kladnost multiplikátoru signalizuje aktivitu příslušného omezení, zatímco jeho nulovost nesignalizuje nic. Po vyřešení souřadnic stacionárních bodů je třeba zvlášť zkontrolovat, zda leží v přípustné množině. Poznámka: Protože platí max f (x) = − min[−f (x)], P
P
(15)
dostáváme při hledání maxima Lagrangeovu funkci s nekladným u0 . Je-li tato konstanta nenulová, prodělíme jí celou rovnici (9) resp. (10) (takže ji lze opět brát jednotkovou) a příslušné konstanty ui jsou pak nekladné. Je-li u0 = 0 znamená to i zde lineární závislost gradientů aktivních omezení. Příklad: Hledejme stacionární body funkce f (x, y) = x + y na přípustné množině P = {[x, y]; g1 = −x ≤ 0, g2 = −y ≤ 0, g3 = x + y − 1 ≤ 0 .} Řešení: O přípustné množině máme jasnou představu, protože vypadá jak jest uvedeno na obr.4. Zřejmě gradg1 ≡ [−1, 0], gradg2 ≡ [0, −1] a gradg3 ≡ [1, 1]. V místech aktivizace jediného omezení nemůže být jeho gradient nezávislý, protože je nenulový. Dvě omezení současně jsou aktivizována právě jen ve třech bodech, a to [0, 0], [1, 0] a [0, 1]. V těchto bodech jsou gradienty příslušných současně aktivizovaných omezení zřejmě lineárně nezávislé (nejsou jakožto vektory rovnoběžné). Lagrangeovu funkci lze tedy pro hledání minima formulovat pouze pro u0 = 1. Má tedy tvar L(x, y, u, v, w) = x + y − ux − vy + w(x + y − 1) . 6
y 1 g 1= 0
g3 = 0 P x g2 = 0
1
Obr.4
Podmínky stacionarity jsou ∂L = 1 − u + w = 0, ∂x ∂L = 1 − v + w = 0. ∂y
(16) (17)
Podmínky komplementarity jsou −ux = 0 , −vy = 0 , w(x + y − 1) = 0 .
(18) (19)
Vzhledem k rovnicím (18) rozlišíme 4 případy.
1. u = 0 nebo v = 0 (tři případy řešené najednou). Podle (16) nebo (17) vždy jest w = −1, což je spor s nezáporností multiplikátoru w. 2. x = y = 0 (čtvrtý případ). Podle (19) je w = 0 a podle (16) a (17) nakonec u = v = 1. Dostali jsme jediné řešení [x0 , y0 , u0 , v0 , w0 ] = [0, 0, 1, 1, 0]. Stacionárním bodem je počátek, ve kterém je zaručeně aktivizováno omezení g1 a g2 . O aktivizaci g3 nelze nic říci. Z náčrtu přípustné množiny vidíme, že ve stacionárním bodě aktivizováno není. Poznámka: Prozkoumáme-li úlohu na hledání maxima, stačí pro Lagrangeovu funkci stejného charakteru nacházet nekladné multiplikátory. Z výše diskutovaných čtyř případů dává případ x = y = 0 vzhledem k (19) w = 0, takže podle (16) a (17) je u = v = 1, což je spor s nekladností multiplikátorů. Ostatní tři případy dávají pro w = 0 buď u = 1 nebo v = 1, což je vždy spor s jejich nekladností. Podle (19) musí býti x + y − 1 = 0. Podle (16) a (17) je pak w = −1 a u = v = 0. Stacionárními body je celá přepona pravoúhlého trojúhelníka ohraničujícího přípustnou množinu a je v nich zaručeně aktivizováno omezení g3 . Příklad: Ukažte, že přípustná množina definovaná jako (viz obr.5) P = {[x, y]; −x ≤ 0, −y ≤ 0, y − (1 − x)3 ≤ 0}
obsahuje bod se závislými gradienty omezení. 7
y 1 g 1= 0
g3 = 0 P x g2 = 0
1
Obr.5
Řešení: Zřejmě platí gradg1 (x, y) ≡ [−1, 0]; gradg2 (x, y) ≡ [0, −1]; gradg3 (x, y) = [3(1 − x)2 , 1] . Protože žádný z gradientů omezení není nikde nulový, je závislost možná právě jen v bodech, kde jsou aktivizována dvě omezení. To je možné právě jen v bodech [x1 , y1 ] = [0, 1] a [x2 , y2 ] = [1, 0]. V prvním bodě jsou aktivizována omezení g1 a g3 , přičemž jest gradg1 (x1 , y1 ) = [−1, 0] a gradg3 (x1 , y1 ) = [3, 1]. Tyto gradienty jsou evidentně nezávislé. Ve druhém bodě jsou aktivizována omezení g2 a g3 , přičemž jest gradg2 (x2 , y2 ) = = [0, −1] a gradg3 (x2 , y2 ) = [0, 1]. Tyto gradienty jsou evidentně závislé.
Poznámka: Úlohu lze řešit též aplikací definice závislosti vektorů (což je tvar Kuhnových Tuckerových podmínek stacionarity Lagrangeovy funkce pro konstantu u0 = 0 při řešení minima jakékoliv cílové funkce na zadané přípustné množině). Tyto podmínky mají tvar −u + 3w(1 − x)2 = 0
(20)
−v + w = 0 ⇔ v = w .
(21)
Z (20) plyne u = 3w(1 − x)2 . Jestliže tedy w > 0, je pro x 6= ±1 i u > 0 a podle (21) i v > 0. To by ovšem znamenalo aktivizaci tří omezení v jediném bodě, což ve dvourozměrném prostoru není možné. Pro x = 1 (x = −1 neleží v přípustné množině) je u = 0 a podle (21) v = w > 0. Jsou tedy současně aktivována omezení g2 a g3 , takže y = 0. Bod [1, 0] je bod závislosti gradientů, který byl výše nalezen jinou metodou. Pro w = 0 je ovšem podle (20) a (21) i u = v = 0, což by signalizovalo nezávislost gradientů a to by byl spor s předpokladem. Každé omezení typu rovnice h(x) = 0 lze chápat jako současné splnění dvojice omezení typu nerovnice, a sice h(x) ≤ 0 a zároveň -h(x) ≤ 0. Jestliže je tedy přípustná množina definována prostřednictvím (2), dostáváme aplikací Kuhnových Tuckerových podmínek pro 2p omezení typu nerovnic existenci nezáporných konstant u0 , u1j a u2j , že u0 gradf (x0 ) +
p X
(u1j − u2j )gradhj (x0 ) (stacionarita) ;
j=1
8
u1j hj (x0 ) = 0 ; −u2j hj (x0 ) = 0 (komplementarita) .
Protože pro x0 ∈ P musí být všechna omezení aktivní, ztrácí podmínky komplementarity smysl. Odtud plynou Kuhnovy Tuckerovy nutné podmínky lokálního podmíněného minima funkce vzhledem k přípustné množině dané ve (2). Tvrzení: Nechť x0 je bod lokálního minima cílové funkce f vzhledem k množině (2). Nechť f a hj jsou v x0 diferencovatelné. Potom existuje u0 ≥ 0 a vj (j = 1, . . . , p) libovolná (ne současně všechny nulové), že u0 gradf (x0 ) +
p X
vj gradhj (x0 ) = 0 .
(22)
j=1
Poznámka: 1. Podobně jako pro případ omezení typu nerovnic, i zde při hledání maxima řešíme minimum cílové funkce −f . Významné hodnoty konstanty u0 jsou tedy pouze tři. Jednička pro hledání minima, mínus jednička pro hledání maxima a nula pro případ závislých gradientů omezujících funkcí. 2. Existenci konstanty u0 lze nahradit doplňujícím předpokladem lineární nezávislosti gradientů omezujících funkcí, čili podmínkou, že Jacobiova matice zobrazení h(x) (vektorové funkce vektorové proměnné) #
"
∂hj (x0 ) , j = 1, . . . , p, k = 1, . . . , n Jh (x0 ) = ∂xk má plnou hodnost, tedy hodnost p = min{p, n}. 3. Pro případ jediného omezení, tedy pro úlohu x0 = arg min f (x) ; P = {x, h(x) = 0} P
má Kuhnova Tuckerova podmínka pro minimum tvar gradf (x0 ) = −vgradh(x0 ) .
Gradient cílové funkce i omezení má v bodě minima (i maxima) týž směr, což znamená, že příslušná vrstevnice cílové funkce i omezení mají ve stacionárním bodě společnou tečnou nadrovinu. Pro funkce dvou proměnných se jedná o tečnu (přímku) a situace je znázorněna na obr.6. Definice: Definujme funkci L(x, v) = L(x1 , . . . , xn , v1 , . . . , vp ) = f (x) +
p X
vj hj (x)
(23)
j=1
a nazveme ji Lagrangeovou funkcí úlohy pro cílovou funkci f a množinu P danou omezeními hj (pro hledání minima). Podmínky stacionarity pak mají tvar gradx L(x, v) = gradf (x) +
p X
j=1
9
vj gradhj (x) = 0 ,
(24)
f = f2
f1
grad f ( x 0 ) = k grad h ( x 0 ) P f = f1 x0
h=0
Obr.6
kde gradx je gradient Lagrangeovy funkce tvořený pouze v proměnných x. Podmínky přípustnosti pak mají tvar gradv L(x, v) = [h1 (x), . . . , hp (x)] = 0 .
(25)
Podmínky stacionarity a přípustnosti představují celkem p + n rovnic pro stejný počet neznámých. Celkem n neznámých představují souřadnice stacionárního bodu cílové funkce a zbylých p neznámých jsou (pro u0 = 1) konstanty vj . Říkáme jim rovněž Lagrangeovy multiplikátory. Příklad: Řešme podmíněný extrém funkce f (x, y) = xy na přípustné množině P = = {[x, y]; x + y − 2 = 0} . Řešení: Pro hledání minima utvoříme Lagrangeovu funkci tvaru L(x, y, u) = xy + u(x + y − 2) .
Podmínky stacionarity mají tvar
∂L ∂L = y + u = 0; = x + u = 0, ∂x ∂y podmínka přípustnosti pak ∂L = x + y − 2 = 0. ∂u Odečtením prvních dvou podmínek získáme x = y a dosazením do třetí podmínky pak x = y = 1. Poznámka: 1. Pro hledání maxima by Lagrangeova funkce měla tvar L(x, y, u) = −xy + u(x + + y − 2). Řešením podmínek stacionarity a přípustnosti získáme stejný stacionární bod. Bod [x, y] = [1, 1] je tedy ”podezřelý” z obou extrémů. 2. Úlohu lze řešit též snížením počtu proměnných. Z podmínky přípustnosti je y = = 2 − x, takže řešíme extrém funkce jedné proměnné 10
g(x) = f (x, 2 − x) = 2x − x2
na celém prostoru R1 . Stacionární bod splňuje podmínku g ′ (x) = 2 − 2x = 0 ⇔ ⇔ x0 = 1 (takže i y0 = 1). Postačující podmínka g ′′ (x) ≡ −2 dává v nalezeném bodě maximum. Tvrzení: Postačující podmínky podmíněného extrému na množině definované omezeními typu nerovnic. Nechť stacionární bod x0 a vektor Lagrangeových multiplikátorů u0 splňují Kuhnovy Tuckerovy nutné podmínky podmíněného minima pro cílovou funkci f a přípustnou množinu danou v (1). Nechť funkce f a gi pro i ∈ I(x0 ) jsou dvakrát spojitě diferencovatelné v x0 a gradgi (x0 ) pro i ∈ I(x0 ) jsou lineárně nezávislé. Nechť navíc platí dT H x L(x0 , u0 )d > 0
(26)
(resp. < 0) pro takové (jednotkové) vektory směru d, pro které dT gradgi (x0 ) ≤ 0
(27)
pro všechna i ∈ I(x0 ). Pak x0 je bod ostrého lokálního minima (maxima) funkce f vzhledem k množině P . Jestliže existuje směrový vektor d1 splňující (27), pro nějž platí (26) a zároveň směrový vektor d2 splňující (27), pro nějž platí v (26) opačná nerovnice, nemá f v bodě x0 vzhledem k přípustné množině P lokální extrém. Tvrzení: Postačující podmínky podmíněného extrému na množině definované omezeními typu rovnic. Nechť stacionární bod x0 a vektor Lagrangeových multiplikátorů v 0 splňují Kuhnovy Tuckerovy nutné podmínky podmíněného minima pro cílovou funkci f a přípustnou množinu danou v (2). Nechť funkce f a hj jsou dvakrát spojitě diferencovatelné v x0 a gradhj (x0 ) jsou lineárně nezávislé. Nechť navíc platí dT H x L(x0 , v 0 )d > 0
(28)
(resp. < 0) pro takové (jednotkové) vektory směru d, pro které dT gradhj (x0 ) = 0 pro všechna j = 1, . . . , p .
(29)
Pak x0 je bod ostrého lokálního minima (maxima) funkce f vzhledem k množině P . Jestliže existuje směrový vektor d1 splňující (29), pro nějž platí (28) a zároveň směrový vektor d2 splňující (29), pro nějž platí v (28) opačná nerovnice, nemá f v bodě x0 vzhledem k přípustné množině P lokální extrém. Poznámka: 1. Výrazy na levých stranách (26) resp. (28) jsou kvadratické formy v souřadnicích směrového vektoru d s Hessovou maticí (vzhledem k proměnným x) Lagrangeovy funkce ve stacionárním bodě. Tam uvedené nerovnice znamenají pozitivní definitnost (resp. negativní definitnost, resp. indefinitnost) zmíněných forem. Tyto jejich vlastnosti ale nezkoumáme pro všechny směry d (tedy na celém prostoru Rn ), ale jen pro směry splňující (27) resp. (29). Podmínka (29) znamená, že směr d musí být kolmý ke gradientu všech aktivních omezujících funkcí. Musí tedy ležet v průniku tečných nadrovin k nulovým vrstevnicím všech aktivních omezujících funkcí. Podmínka (27) znamená, že směr d musí s gradientem aktivní omezující funkce 11
svírat tupý úhel. Musí tedy směřovat do toho poloprostoru (vymezeného tečnou nadrovinou k omezující funkci), ve které leží přípustná množina P . Toto musí být splněno pro všechny ve stacionárním bodě aktivní omezení. 2. Praktické výpočty se provádějí vyjádřením některých souřadnic směrového vektoru d z doplňujících podmínek (27) nebo (29) a dosazením do kvadratické formy. Získáme formu nižší dimenze, jíž zkoumáme na celém prostoru, popřípadě pro některé souřadnice omezeného rozsahu. 3. Tvrzení neřeší případ semidefinitnosti kvadratických forem. 4. Doplňující podmínky by bylo možno ještě oslabit, ale nebudeme se těmito detaily už zabývat. Příklad: Hledejme podmíněná minima funkce f (x, y) = (x − 2)2 + y 2 na přípustné množině P = {[x, y]; −x ≤ 0; −y ≤ 0; x2 + y 2 − 1 ≤ 0}.
Řešení: O přípustné množině máme přesnou představu, neboť se jedná o průnik prvního kvadrantu s (uzavřenou) kružnicí se středem v počátku o poloměru jedna (viz obr.7). y 1 g3 = 0
g 1= 0 P
x g2 = 0
1
Obr.7 Gradienty omezujících funkcí jsou zřejmě nenulové vektory a v (třech) bodech, kde jsou aktivní současně dvě omezení, jsou jejich gradienty zřejmě lineárně nezávislé. Stačí tedy v Lagrangeově funkci uvažovat u0 = 1. Lagrangeova funkce má tedy tvar L(x, y, u, v, w) = (x − 2)2 + y 2 − ux − vy + w(x2 + y 2 − 1) .
Kuhnovy Tuckerovy nutné podmínky stacionarity jsou
∂L = 2(x − 2) − u + 2wx = 0 , ∂x ∂L = 2y − v + 2wy = 0 . ∂y
(30) (31)
Podmínky komplementarity jsou −ux = 0 ; −vy = 0 ; w(x2 + y 2 − 1) = 0 . 12
(32) (33)
Kromě toho musíme akceptovat podmínky příslušnosti k přípustné množině P . Rovnicím (32) vyhovují čtyři případy kombinace nulovosti jednotlivých proměnných. 1. x = y = 0 . Podle (33) pak w = 0 a podle (30) potom u = −4, což je pro hledání minima spor s nezáporností Lagrangeových multiplikátorů. 2. x = v = 0 . S ohledem na (33) rozlišíme dva podpřípady. (a) w = 0 , odkud podle (30) je u = −4, což je opět spor s nezáporností multiplikátoru u (b) y = ±1 . Případ y = −1 nevyhovuje, protože příslušný bod neleží v přípustné množině. Je tedy y = 1 a z (31) pak plyne, že w = 1 a z (30) pak u = −4, což je opět spor s nezáporností tohoto čísla. 3. y = u = 0 . S ohledem na (33) rozlišíme dva podpřípady. (a) w = 0 , odkud podle (30) je x = 2, takže nalezený bod neleží v přípustné množině. (b) x = ±1 . Případ x = −1 nevyhovuje, protože příslušný bod neleží v přípustné množině. Je tedy x = 1 a z (31) pak plyne, že v = 0 a z (30) potom w = 1. Tento případ vyhovuje a dává řešení [x, y, u, v, w] = [1, 0, 0, 0, 1] . 4. u = v = 0 . S ohledem na (31) rozlišíme dva podpřípady. (a) y 6= 0. Z (17) pak plyne w = −1, což je spor s jeho nezáporností
(b) y = 0, odkud podle (33) (w už nulové být nemůže) x = ±1. Případ x = −1 neleží v přípustné množině, pročež x = 1 a z (30) plyne w = 1. Získali jsme tak stejný stacionární bod, jako v 3b. Jediný stacionární bod (pro hledání minima) je tedy bod [x, y, u, v, w] = [1, 0, 0, 0, 1] . Plyne odtud, že v bodě [x, y] = [1, 0] je zaručeně aktivní třetí omezení. O aktivitě zbylých omezení nelze výpočtem říci nic. Z obrázku je patrno, že ve zmíněném bodě je aktivní i první omezení, přestože k němu příslušný multiplikátor je nulový. Aplikujme nyní postačující podmínky minima. Zřejmě je ∂ 2L ∂2L ∂2L = 0. = 2 + 2w ; = 2 + 2w ; ∂x2 ∂y 2 ∂x∂y o stacionární bod, kde w = 1, je Hessova matice H x L(x0 , u0 ) =
"
4 0 0 4
#
.
Tato matice je pozitivně definitní vzhledem ke všem směrům (protože oba rohové hlavní minory jsou kladné). Funkce f má v bodě x0 ostré lokální minimum vzhledem k celému prostoru R2 , tedy jej má tím spíše i vzhledem k množině P . 13
Poznámka: Pokud bychom funkci zkoumali na maximum, hledáme stejnou metodou stacionární body, kde ovšem bereme multiplikátory nekladné. Dostali bychom jiné ”podezřelé” body, které bychom potvrdili (nebo také nikoliv) postačující podmínkou. V rámci procvičování látky si to proveďte. Příklad: Hledejme podmíněná minima funkce f (x, y) = x3 + 3y 2 + 6xy na přípustné množině P = {[x, y]; 2x2 − y ≤ 0}. Řešení: O přípustné množině máme opět přesnou představu (obr.8). Protože omezující
y
2
g=0
P x 1 Obr.8 podmínka je pouze jediná a platí pro ni gradg(x) = [4x; −1] 6= 0 ,
stačí se opět omezit na případ u0 = 1. Lagrangeova funkce má pro tuto úlohu tvar L(x, y, u) = x3 + 3y 2 + 6xy + u(2x2 − y) .
Podmínky stacionarity mají tvar
∂L = 3x2 + 6y + 4ux = 0 , ∂x ∂L = 6y + 6x − u = 0 . ∂y
(34) (35)
Podmínka komplementarity je jediná u(2x2 − y) = 0 .
(36)
Kromě toho je třeba ještě akceptovat podmínky incidence pracovního bodu úlohy s přípustnou množinou P . S ohledem na (36) rozlišíme dva případy. 1. u = 0 , odkud podle (35) je y = −x, což dosazeno do (34) dává 3x2 − 6x = 0 ⇔ 3x(x − 2) = 0 .
Dostáváme tak dvě možná řešení: x1 = y1 = 0 a x2 = 2 ; y2 = −2. Druhé řešení ovšem nesplňuje podmínku příslušnosti k P . Získali jsme jediné řešení [x0 , y0 , u0 ] = = [0, 0, 0] . 14
2. u 6= 0, takže podle (36) je y = 2x2 , což dosazeno do (34) a (35) dává soustavu 3x2 + 12x2 + 4ux = 0 ,
(37)
6x + 12x2 − u = 0 .
(38)
Z (38) plyne u = 6x(1 + 2x), což dosazeno do (37) dává 15x2 + 24x2 (1 + 2x) = 0 ⇔ 39x2 + 48x3 = 0 ⇔ x2 (39 + 48x) = 0 .
Tato rovnice má dvě řešení, a sice [x0 , y0 ] = [0, 0], které už bylo nalezeno a [x0 , y0 ] = =
− 39 ;2 48
·
39 48
2
. Z (38) potom plyne u0 = 6x0 (1 + 2x0 ) =
13 · 15 > 0. 64
Získali jsme tak dva stacionární body. [x0 , y0 ] = [0, 0], kde je u0 = 0, takže výpočtem nelze o aktivizaci omezení nic říci. Z obrázku geometrie množiny P (obr.8) vidíme, h i 39 39 že omezení je aktivováno. Druhým stacionárním bodem je [x0 , y0 ] = 48 −1; 24 kdy příslušný multiplikátor u0 je kladný. Omezení je aktivováno i zde, což je ověřeno přímým výpočtem. Prozkoumejme postačující podmínky. Zřejmě je ∂ 2L ∂2L ∂2L = 6. = 6x + 4u ; = 6 ; ∂x2 ∂y 2 ∂x∂y V bodě [x0 , y0 , u0 ] = [0, 0, 0] má Hessova matice Lagrangeovy funkce tvar H x L(0, 0, 0) =
"
0 6 6 6
#
.
Snadno se přesvědčíme, že tato matice je (na prostoru R2 ) indefinitní. Má tedy vzhledem k R2 sedlový bod. Tato informace zatím neříká nic o typu stacionárního bodu ve vztahu k přípustné množině P . Kvadratickou formu dT H x L(0, 0, 0)d = 6(d22 + 2d1 d2 )
(39)
budeme zkoumat pouze pro směry splňující podmínku dT gradg(x0 ) ≤ 0. Tato podmínka je ekvivalentní podmínce [d1 , d2 ]
"
0 −1
#
≤ 0 ⇔ d2 ≥ 0 .
(40)
Forma (39) má např. pro vektor dT1 = [1, 1] hodnotu 18, zatímco pro vektor dT2 = = [−1, 1] hodnotu -6. Protože oba zmiňované vektory splňují doplňující podmínku (40), je matice indefinitní i pro tyto směry a stacionární bod [x0 , y0 ] = [0, 0] je sedlovým bodem vzhledem hk přípustné množině P . Prozkoumáme ještě druhý stacionární bod, i 39 39 39 −1, 39 a u = − 1 − . Hessova matice Lagrangeovy funkce v kdy [x0 , y0 ] = 48 0 24 8 24 tomto bodě je H x L(x0 , y0 , u0 ) = 15
"
117 16
6
6 6
#
.
> 6 , jsou oba rohové hlavní minory této matice kladné a podle Hurwitzova Protože 117 16 kriteria je matice pozitivně definitní. Příslušný stacionární bod je minimem vzhledem ke všem směrům z prostoru R2 . Tím spíše je minimem i vzhledem k přípustné množině P. Příklad: Jaké rozměry musí mít kvádr daného objemu V > 0, aby vykazoval minimální povrch? Řešení: Jestliže označíme x, y, z délky hran kvádru, jedná se zřejmě o úlohu nalezení minima cílové funkce f (x, y, z) = xy + xz + yz (poloviční povrch) na přípustné množině P = {[x, y, z]; xyz − V = 0} . Lagrangeova funkce úlohy má zřejmě tvar L(x, y, z, u) = xy + xz + yz + u(xyz − V ) .
Kuhnovy Tuckerovy nutné podmínky dávají výrazy
∂L = y + z + uyz = 0 , ∂x ∂L = x + z + uxz = 0 , ∂y ∂L = x + y + uxy = 0 , ∂z ∂L = xyz − V = 0 . ∂u Z rovnic (41),(42) a (43) vyloučíme multiplikátor u. Vznikne
(41) (42) (43) (44)
x(y + z) − y(x + z) = (x − y)z = 0 ,
(45)
y(x + z) − z(x + y) = (y − z)x = 0 .
(46)
Řešíme pak soustavu √ (44),(45) a (46) pro neznámé x, y, z. Protože V > 0, jediné její 2 . Jediný stacionární řešení je x = y = z = 3 V . Z rovnice (41) pak dostaneme u = − √ 3 V bod tedy je [x0 , y0 , z0 , u0 ] =
"
√ 3
V,
√ 3
V,
√ 3
2 V , −√ 3 V
#
.
Aplikujme nyní postačující podmínky. Zřejmě platí ∂2L ∂2L ∂ 2L ∂2L ∂2L ∂2L = = = 0; = 1 + uz; = 1 + uy; = 1 + ux . ∂x2 ∂y 2 ∂z 2 ∂x∂y ∂x∂z ∂y∂z Proto Hessova matice má tvar 0 −1 −1 H x L(x0 , y0 , z0 , u0 ) = −1 0 −1 . −1 −1 0
K této matici příslušející kvadratické forma
dT H x L(x0 , y0 , z0 , u0 )d = −2(d1 d2 + d1 d3 + d2 d3 ) dT1
(47) dT2
je zřejmě indefinitní, jak se snadno přesvědčíme dosazením = [0, 1, 1] a = = [0, 1, −1]. Doplňující podmínka dT gradh(x0 ) = 0 má v našem případě tvar 16
y0 z0 √ 3 x [d1 , d2 , d3 ] 0 z0 = V 2 (d1 + d2 + d3 ) = 0 . x0 y0
(48)
Definitnost formy (47) zkoumáme pouze při splnění podmínky (48). Snížíme proto její dimenzi dosazením d3 = −d1 − d2 . Dostaneme formu na R2 ve tvaru
d2 −2[d1 d2 − d1 (d1 + d2 ) − d2 (d1 + d2 )] = 2(d21 + d1 d2 + d22 ) = 2 d1 + 2
!2
3 + d22 . 4
Doplněním na kvadrát vidíme, že tato forma je pozitivně definitní. Nalezený stacionární bod je tedy minimem cílové funkce vzhledem k přípustné množině P . Poznámka: Úlohu lze řešit rovněž snížením její dimenze. Z (44) například určíme z = a zkoumáme na celém prostoru R2 cílovou funkci V g(x, y) = f x, y, xy
!
= xy +
V xy
V V + ; x 6= 0, y 6= 0 . y x
Nutné podmínky jejího extrému jsou ∂g =y− ∂x ∂g =x− ∂y
V = 0, x2 V = 0. y2
(49) (50)
4
Z (49) plyne y = xV2 a dosazením do (50) x − xV = 0. Řešení x = 0 evidentně nevyhovuje, √ √ pročež jediným stacionárním bodem je x0 = 3 V a proto i y0 = xV2 = 3 V . Utvoříme 0 ještě Hessovu matici funkce g. Je ∂2g 2V ∂ 2 g 2V ∂ 2 g = 1. = ; = ; ∂x2 x3 ∂y 2 y 3 ∂x∂y Proto Hg(x0 , y0 ) =
"
2 1 1 2
#
.
Tato matice je podle Hurwitzova kriteria positivně definitní a tudíž cílová funkce g má √ 3 V v nalezeném bodě [x0 , y0 ] lokální minimum. Ze vztahu z = xy plyne, že i z0 = V .
17
