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.