Desata prednaska z operacniho vyzkumu

Parovani, nelinearni programovani

Obsah

Volny extrem - Metoda nejvetsiho spadu

Metoda nejvetsiho spadu je jednou z metod aproximace volneho extremu pro funkci vice promennych. Je zalozena na pojmu gradientu.
Gradient
Gradient funkce f: R^n --> R v bode x je n-tice hodnot (df/dxi(x)) = grad f(x). Antigradient je hodnota -graf f(x).

Gradient udava smer nejrychlejsiho rustu funkce f v bode x, antigradient smer nejrychlejsiho klesaci. V bodech, kde ma funkce f lokalni extrem je gradient roven nulovemu vektoru.

Postup metody nejvetsiho spadu (pro minimalizaci)
Vyjdeme z pocatecni aproximace x=(x1,..,xn). Spocitame antigradient -grad f(x) (pri maximalizaci pouzijeme primo gradient) a polozime fi(t)=f(x-t*grad f(x)). Najdeme lokalni minimum t' funkce jedne promenne f(t), napriklad Newtonovou metodou . Pak polozime x'=x-t'*grad f(x) a pouzijeme x' jako dalsi aproximaci extremu. Tento postup opakujeme tak dlouho, dokud hodnota normy (velikosti) vektoru grad f(x) neklesne pod predem danou hranici.
Priklad
Hledame volny extrem funkce dvou promennych f(x,y)=(x-1)^2+(y-2)^2. Jako pocatecni aproximaci zvolime x0=(0,0).

Spocitame derivace funkce f podle jednotlivych promennych: df/dx(x,y)=2x-2, df/dy=2y-4.

V bode x0=(0,0) je gradient roven graf f(0,0)=(-2,-4), antigradient je roven vektoru (2,4). Budeme tedy minimalizovat funkci fi(t)=f(x-t*grad f(x0)) = f(x0+t(2,4)) = f(2t,4t) = (2t-1)^2+(4t-2)^2 = 20t^2-20t+5. Lokalni minimum teto funkce je v bode t=1/2 (lze zjistit napriklad pomoci prvni derivace). Jako dalsi aproximaci x1 tedy vezmeme bod x1=x0-t*graf f(x0) = (0+1/2*2,0+1/2*4) = (1,2).

V tomto bode uz je grad f(x1) = (0,0), jedna se tedy primo o lokalni extrem. Z konvexnosti funkce f plyne, ze se jedna o lokalni minimum.

V uvedenem priklade diky specialnimu tvaru funkce metoda konecneho spadu skoncila po prvnim kroku nalezenim extremu. Obecne se vsak jedna o metodu infinitni a aproximacni, tedy po konecnem poctu kroku neni zaruceno nalezeni extremu, ale pouze jeho aproximace. Presvedcit o tom se lze napriklad u minimalizace funkce f(x,y)=2*(x-1)^2+(y-2)^2.

Vazany extrem - Lagrangeovy multiplikatory

Metoda Lagrangeovych multiplikatoru je zakladni metoda pro hledani vazaneho extremu pro klasickou ulohu nelinearniho programovani. Jejim zakladem je nasledujici veta
Lagrangeova veta
Necht funkce f:R^n --> R ma v bode x0 vazany lokalni extrem na mnozine M dane resenim soustavy rovnic gj(x)=0 j=1,..,m. Necht maji funkce f i vsechny funkce gi v okoli bodu x0 spojite vsechny parcialni derivace (postacuje i slabsi podminka). Potom existuji cisla lambda_1,... , lambda_m takova,ze pro funkci plati
Postup vypoctu
Soustava rovnic z predchozi vety obsahuje n+m rovnic pro n+m neznamych x1,...,xn,lambda_1,...,lambda_m. Vyresenim teto soustavy rovnic dostaneme pozadovany vazany extrem.
Priklad
Najdeme vazany lokalni extrem funkce f(x,y)=x^2+2y^2+2x na kruznici K dane rovnici g(x,y)=x^2+y^2-4 = 0.

Vsechny uvedene funkce splnuji predpoklady Lagrangeovy vety. Vazany extrem (x0,y0) musi tedy splnovat nasledujici soustavu 3 rovnic o 3 neznamych:

Resenim teto soustavy dostaneme 4 body: (2,0) (-2,0) (1,odm(3)), (1,-odm(3)). V prvnich dvou ma funkce lokalni minimum, v druhych dvou lokalni maximum.
Tuto stranku vytvoril Tomas Vanicek a jedna se o soucast prednasek ze Systemove analyzy a operacniho vyzkumu pro obor Inzenyrstvi zivotnioho prostredi Stavebni fakulty Ceskeho vysokeho uceni technickeho v Praze.