3 Podmínky optimality - příklady

Nyní si na konkrétních příkladech ukážeme způsob testování optimality předem daného bodu. Pro jednoduchost začneme funkcí jedné proměnné, pokračovat budeme funkcí dvou proměnných.

3.1 Funkce jedné proměnné

Mějme následující funkci jedné proměnné:

(3.1)

Myslíme si, že tato funkce má minima v bodech x1 = -1, x2 = 0 a x3 = +1. Našim úkolem je ověřit, zda tomu tak skutečně je.

Nejprve se zaměříme na podmínku stacionarity. Vypočteme první derivaci funkce (3.1)

(3.2)

a vyčíslíme její hodnotu v bodech x1, x2 a x3. Zatímco v prvním a třetím bodě vychází derivace nulová, v druhém bodě je hodnota první derivace -2. Zatímco v bodech x1 a x3 je podmínka optimality prvního řádu splněna, v bodě x2 splněna není, a tudíž minimum v něm určitě nebude.

V dalším kroku musíme ověřit, zda se v bodech x1 a x3 nachází minimum, maximum či inflexní bod. Musíme tedy vypočíst druhou derivaci kriteriální funkce

(3.3)

a vyčíslit její hodnotu v bodech x1 a x3. V obou případech dostáváme hodnotu +802. Kladná hodnota druhé derivace potvrzuje minimum v bodech x1 a x3.

O správnosti výpočtu se můžeme přesvědčit na obr. 3.1, na němž je vykreslen průběh funkce (3.1) v okolí počátku souřadné osy. Z průběhu je vidět, že v bodech x1 a x3 se nacházejí skutečně minima a že v malé vzdálenosti od bodu x2 má funkce své lokální maximum.

3.2 Funkce dvou proměnných

Mějme následující funkci dvou proměnných:

(3.4)

Funkce (3.4) se nazývá Rosenbrockova funkce. Rosenbrockova funkce má tvar banánovitého údolí se strmými srázy v jednom směru a s plochým dnem ve směru druhém. To je z hlediska optimalizačních metod "vražedná kombinace", a proto Rosenbrockovu funkci používáme k testování vlastností optimalizačních metod. Průběh Rosenbrockovy funkce v okolí počátku souřadného systému je nakreslen na obr. 3.2.

Našim úkolem je ověřit, zda se v bodě [1, 1] nachází minimum Rosenbrockovy funkce.

Abychom mohli ověřit splnění podmínky optimality prvního řádu, musíme vypočíst gradient funkce (3.4)

(3.5)

Dosadíme-li do (3.5) za x1 = 1 a za x2 = 1, vyjde hodnota obou složek gradientu nulová. Norma gradientu je tedy v bodě [1, 1] nulová, takže se v tomto bodě může nacházet minimum, maximum nebo sedlový bod. Abychom mohli rozhodnout o tom, která ze tří uvedených možností nastává, musíme vypočíst Hessovu matici

(3.6)

Dále dosadíme do (3.6) za x1 = 1 a za x2 = 1 a vypočteme v MATLABu pomocí funkce eig vlastní čísla hessiánu k1 = 1001,6 a k2 = 0,4. Obě vlastní čísla jsou kladná, hessián je pozitivně definitní a v bodě [1,1] se tedy nachází minimum Rosenbrockovy funkce.

3.3 Když neznáme derivace ...

Při řešení praktických optimalizačních úloh jsme schopni analyticky vypočíst hodnoty derivací v předpokládaném optimu spíše výjimečně. Navrhujeme-li např. nějakou anténu, máme v počítači k dispozici její numerický model, který pro dané rozměry a danou frekvenci vypočte proudové rozložení na anténním vodiči nebo rozložení intenzity pole v anténní apertuře. Numerický model v podstatě zobrazuje rozměry jako stavové proměnné na elektrické veličiny jako posuzované parametry optimalizačního problému. Analytické vyjádření kriteriální funkce neznáme, a proto musíme gradient a hessián počítat numericky.

Numerický výpočet gradientu je založen na náhradě parciálních derivací středovými diferencemi (obr. 3.3). Počítáme-li hodnotu první derivace funkce v bodě x, počítáme směrnici červené tečny. Uděláme-li úkrok h nad hodnotu x a úkrok h pod hodnotu x, vytvoříme modrý pravoúhlý trojúhelník, jehož přepona má směrnici blízkou směrnici tečny. Shoda obou směrnic bude tím lepší, čím menší úkrok h zvolíme. Matematicky můžeme náhradu derivace diferencí zapsat následovně:

(3.7)

Ze vztahu (3.7) však dále vyplývá, že délku úkroku nemůžeme nepřiměřeně zkracovat. Při dělení velmi malým číslem totiž narůstá numerická chyba výpočtu (3.7).

Počítáme-li pomocí středových diferencí druhou derivaci, postupujeme ve dvou krocích:

- pomocí diferencí spočteme první derivace v bodech x-h a x+h

(3.8)

- středovou direrencí z diferencí (3.8) vytvoříme odhad druhé derivace v bodě x.

Při středovém diferencování musíme pečlivě hlídat body, v nichž byl odhad derivace vypočten.

Nyní si ukážeme popsaný postup na konkrétním příkladu. V matlabovském souboru rosenbrock.m je uložena Rosenbrockova funkce (3.4). Předpokládáme, že obsah souboru neznáme a že jen umíme na základě hodnot x1 a x2 vypočíst funkční hodnotu. Našim úkolem je opět zjistit, zda se v bodě [1,1] nachází minimum Rosenbrockovy funkce či nikoli.

Začněme podmínkou stacionarity a pomocí středových diferencí vyjádřeme složky gradientu cond01.m:


function g = cond01( x)

 h = 1e-6;

X1(1,1) = rosenbrock( [x(1,1) + h; x(2,1)]);
X1(2,1) = rosenbrock( [x(1,1) - h; x(2,1)]);

X2(1,1) = rosenbrock( [x(1,1); x(2,1) + h]);
X2(2,1) = rosenbrock( [x(1,1); x(2,1) - h]);

g(1,1) = (X1(1,1) - X1(2,1)) / (2*h);
g(2,1) = (X2(1,1) - X2(2,1)) / (2*h);

Při počítání první složky gradientu pracujeme jen s první proměnnou, zatímco druhá souřadná proměnná zůstává konstantní. Při počítání druhé složky postupujeme obdobně. Při délce úkroku h = 10-6 vycházejí hodnoty složek gradientu menší než 10-10, při délce úkroku h = 10-8 klesají hodnoty složek gradientu pod 10-13. Lze tedy říci, že s klesající délkou úkroku h konverguje norma gradientu k nule, a tudíž lze podmínku stacionarity považovat za splněnou.

Nyní se tedy soustřeďme na podmínku optimality cond02.m:


function g = cond02( x)

h = 1e-8;

X1(1,1) = rosenbrock( [x(1,1) + 2*h; x(2,1)]);
X1(2,1) = rosenbrock( [x(1,1) ; x(2,1)]);
X1(3,1) = rosenbrock( [x(1,1) - 2*h; x(2,1)]);

f1 = (X1(1,1) - X1(2,1)) / (2*h);
f2 = (X1(2,1) - X1(3,1)) / (2*h);

G(1,1) = (f1 - f2) / (2*h);

X2(1,1) = rosenbrock( [x(1,1); x(2,1) + 2*h]);
X2(2,1) = rosenbrock( [x(1,1); x(2,1)]);
X2(3,1) = rosenbrock( [x(1,1); x(2,1) - 2*h]);

f1 = (X2(1,1) - X2(2,1)) / (2*h);
f2 = (X2(2,1) - X2(3,1)) / (2*h);

G(2,2) = (f1 - f2) / (2*h);

X3(1,1) = rosenbrock( [x(1,1) + h; x(2,1) + h]);
X3(2,1) = rosenbrock( [x(1,1) + h; x(2,1) - h]);
X3(3,1) = rosenbrock( [x(1,1) - h; x(2,1) + h]);
X3(4,1) = rosenbrock( [x(1,1) - h; x(2,1) - h]);

G(1,2) = (X3(1,1) - X3(2,1) - X3(3,1) + X3(4,1)) / (2*h)^2;
G(2,1) = G(1,2);

g = eig( G);

V prvních dvou blocích počítáme pomocí středových diferencí druhou derivaci podle x1 a druhou derivaci podle x2. Dostáváme tak složky Hessovy matice G(1,1) a G(2,2). Výpočet odpovídá výše popsanému postupu (viz vztah 3.8).

Prvky Hessovy matice G(1,2) a G(2,1) počítáme podle vztahu

(3.9)

Při volbě délky úkroku h = 10-8 získáme vlastní čísla hessiánu, která jsou totožná s analytickým výpočtem.