3 Podmínky optimality
V této kapitole budeme předpokládat, že jsme se dozvěděli o
bodu x+,
v němž by mohlo být optimum (minimum kriteriální funkce). Našim
úkolem je rozhodnout, zda v daném bodě optimum skutečně je nebo
zda se jedná o planý poplach. Bod x+
je bodem z N-rozměrného
reálného prostoru (má N
reálných souřadnic x1,
x2, ..., xN).
Dále budeme předpokládat, že řešíme obecný optimalizační problém (NCP, non-linearly
constrained problem), že tedy minimalizujeme kriteriální funkci,
doplněnou sadou omezujících podmínek.
Body, které splňují omezující podmínky, budeme nazývat přípustnými
body. Všechny přípustné body dohromady tvoří přípustnou oblast. Pokud
je optimalizační problém bez přípustných bodů, hovoříme o nepřípustném
problému. Optimalizace s omezujícími podmínkami musí probíhat vždy
v přípustné oblasti.
Pokud je náš optimalizační problém omezen např. podmínkami
(3.1)
|
leží
přípustné body ve čtverci s levým horním rohem v bodě [-1, +1] a
s pravým dolním rohem v bodě [+1, -1], jak je naznačeno na obr.
3.1. Při hledání optima tedy neprohledáváme celý nekonečný prostor [x
1, x 2] , ale pohybujeme se pouze po
ploše červeného čtverce s konečně velkou plochou. Optimalizace
probíhá pouze v přípustné oblasti.
Optimalita bodu x+
je definována jeho vztahem k okolním bodům. Je-li x+ přípustný bod
optimalizačního problému (NCP) a je-li N( x+, d)
množina přípustných bodů, ležících do vzdálenosti d od x+, pro níž je splněno:
- F( x) je definována
na N( x+, d),
- F( x+)<
F( x) pro
všechna x z množiny
N( x+, d),
potom x+ je silným
lokálním minimem.
Zjednodušeně řečeno - bod x+
je optimem, pokud v něm kriteriální funkce nabývá nejmenší funkční
hodnoty.
Uvedená definice optima je sice jasná, nicméně prakticky nepoužitelná.
Kdybychom chtěli určovat optimum podle uvedené definice, museli bychom
počítat hodnotu kriteriální funkce F( x) v celé oblasti N( x+, d).
U hladkých kriteriálních a omezujících funkcí lze přitom nalézt mnohem
praktičtější podmínky optimality. V následujících odstavcích si
uvedeme, jaké podmínky optimality lze formulovat pro vybrané třídy
optimalizačních problémů.
3.1 Neomezená optimalizace, funkce jedné proměnné
Zabýváme se minimalizací funkce F( x), kde x
je reálné číslo. Pokud je funkce F( x) dvakrát
spojitě diferencovatelná (tj. lze vypočíst její první a druhou
derivaci) a pokud v konečném bodě x+ existuje lokální
minimum, musí pro toto minimum platit:
-
Hodnota první derivace kriteriální funkce v optimu je nulová
(3.2) |
Podmínku nazýváme podmínkou optimality prvního řádu. Pokud je tato podmínka splněna, je bod x+ bodem stacionárním (může se v něm nacházet minimum, maximum nebo inflexní bod, jak je naznačeno na obr. 3.2). Podmínka v podstatě říká, že tečna ke kriteriální funkci je v bodě x+ rovnoběžná s vodorovnou osou.
Podmínku optimality prvního řádu také nazýváme podmínkou stacionarity. Bod, v němž první derivace funkce nabývá nulové hodnoty, je bodem stacionárním.
- Hodnota druhé derivace kriteriální funkce v optimu je kladná
(3.3) |
Podmínku nazýváme podmínkou optimality druhého řádu. Pokud je tato podmínka splněna současně s podmínkou prvního řádu, vybereme ze tří případů vykreslených na obr. 3.2 případ b. Je-li druhá derivace kladná, pak se totiž jedná o funkci konkávní (záporná hodnota druhé derivace popisuje konvexní funkci 3.2a a nulová hodnota inflexní bod 3.2c).
Abychom mohli s jistotou říci, že se v bodě x+ nachází optimum, stačí nám v případě hladké funkce jedné proměnné vypočíst prvou a druhou derivaci a do výsledných vztahů dosadit bod x+. Numerický příklad uvádíme ve vrstvě B.
3.2 Neomezená optimalizace, funkce více proměnných
Dříve, než přistoupíme k obecné formulaci podmínek optimality, pokusme se je intuitivně odvodit pro případ rotačního paraboloidu, který je funkcí proměnných x1, x2 (viz obr. 3.3).
Ve stacionárním bodě musí být tečná rovina ke kriteriální funkci rovnoběžná s rovinou [x1, x2] . Tato tečná rovina je určena směrnicemi dvou různých tečen ke kriteriální funkci. Nejsnáze lze postupovat tak, že spočteme směrnici tečny ve směru x1 jako parciální derivaci kriteriální funkce podle x1, že spočteme směrnici tečny ve směru x2 jako parciální derivaci kriteriální funkce podle x2, a že obě směrnice vzájemně složíme
(3.4) |
Je zřejmé, že vektor t z tečné roviny bude mít nulovou směrnici tehdy, budou-li obě parciální derivace ve vztahu (3.4) rovny nule pro bod x+, v němž předpokládáme optimum.
Parciální derivace funkce podle souřadných proměnných tvoří složky gradientu této funkce. Pro obecný N-rozměrný případ tedy dostáváme
(3.5) |
Podmínku stacionarity můžeme tedy zobecnit do formy požadavku, aby všechny složky gradientu byly ve stacionárním bodě nulové. Má-li vektor všechny své složky nulové, je nulová i jeho velikost (délka, norma). V literatuře se nejčastěji setkáme s podmínkou stacionarity formulovanou: norma gradientu je ve stacionárním bodě nulová.
Na obr. 3.4 je znázorněno, jak se situace z obr. 3.2 (funkce jedné proměnné) změní pro případ funkce dvou proměnných. Asi nejzajímavějším případem je případ c - u funkce jedné proměnné se jednalo o inflexní bod, u funkce dvou proměnných tomu odpovídá bod sedlový: v jednom směru má kvadratický průběh funkce konvexní charakter, ve směru druhém charakter konkávní.
Nyní se soustřeďme na podmínku optimality druhého řádu, která nám z případů obr. 3.4a až 3.4c umožní vybrat ten, v němž se nachází minimum. Stejně jako v případě funkce jedné proměnné využijeme i zde informaci, kterou poskytuje druhá derivace funkce (informace o křivosti funkce). V případě funkce více proměnných
úplnou informaci o křivosti obsahuje tzv. Hessova matice (hessián)
(3.6) |
Je-li hessián pozitivně definitní, je kriteriální funkce konkávní a v bodě x+ se nachází minimum. Je-li hessián negativně definitní, je funkce konvexní a v bodě x+ je maximum. Je-li hessián indefinitní, je x+ sedlovým bodem.
Hessián je pozitivně definitní tehdy, když výsledkem součinu
(3.7) |
je kladné číslo pro libovolný nenulový sloupcový vektor y (obdobě je tomu v případě negativní definitnosti). Nicméně, prakticky nelze uvedenou definici nijak použít - museli bychom zkoušet výsledek násobení (3.7) pro všechny možné vektory y.
Praktičtější přístup je založen na počítání vlastních čísel Hessovy matice v bodu x+. Jsou-li všechna vlastní čísla kladná, je funkce pozitivně definitní, jsou-li všechna záporná, je funkce negativně definitní, jsou-li některá vlastní čísla kladná a některá záporná, je funkce indefinitní.
Nyní si ještě připomeňme, co to jsou vlastní čísla. Pro libovolnou čtvercovou matici A existuje nejméně jeden skalár k a odpovídající nenulový vektor l takový, že
(3.8) |
Skalár k nazýváme vlastním číslem a vektor l vlastním vektorem. Vztah (3.8) můžeme přepsat do tvaru
(3.9) |
kde I je jednotková matice (jedničky na hlavní diagonále, mimo ni nuly). Z formy zápisu (3.9) vyplývá, že u vlastního vektoru je důležitý pouze směr a nikoli velikost (velikostí lze obě strany rovnice 3.9 pokrátit). Pokud je matice A symetrická (jak je vidět ze vztahu 3.9, je to případ Hessovy matice), jsou všechna vlastní čísla reálná a matice má N lineárně nezávislých vlastních vektorů, kde N je rozměr matice.
V MATLABu počítáme vlastní čísla pomocí m-funkce eig. Konkrétní příklad na podmínky optimality u vícerozměrných kriteriálních funkcí uvádíme ve vrstvě B.
3.3 Omezená optimalizace
Nyní si stručně vysvětlíme, jak se změní podmínky optimality v případě omezení optimalizačního problému podmínkami. Pro jednoduchost předpokládejme, že minimalizace kriteriální funkce F( x) je omezena lineární rovností
(3.10) |
Pro dvojrozměrný stavový prostor je situace naznačena na obr. 3.5. Zatímco při neomezené optimalizaci prohledáváme při minimalizaci celý stavový prostor (pohybujeme se po celém povrchu rotačního paraboloidu nalevo), při omezení lineární rovností se můžeme pohybovat pouze v rámci omezující roviny (3.10), která je kolmá na stavovou rovinu a která v rotačním paraboloidu vysekne červenou parabolu. Jedna omezující podmínka tedy snížila rozměr problému o jednu dimenzi.
V případě omezené optimalizace lze tedy podmínky optimality definovat následovně:
- musí být splněna omezující podmínka (3.10),
- norma průmětu gradientu do omezující podmínky musí být rovna nule.
- průmět hessiánu do omezující podmínky musí být pozitivně definitní.
Právě uvedené schéma je nutno modifikovat pro případ omezení lineární nerovností (na hranici platí přístup uvedený pro rovnost, uvnitř přípustného poloprostoru platí pravidla pro neomezenou optimalizaci) i pro nelineární omezující podmínky (k nelineární hranici vedeme tečnu, která v daném bodě vytváří lineární aproximaci hranice - tím jsme nelineární omezení převedli zpět na omezení lineární). Těmito případy se však vzhledem k jejich relativní složitosti nebudeme zabývat.