15. Použití lineární algebry v optimalizaci. Iterační algoritmy na volné lokální extrémy. Lineární programování. Konvexní množiny a funkce, konvexní úlohy. Dualita.
PREVIOUS
1 Metoda nejmenších čtverců
Metoda nejmenších čtverců je matematicko-statistická metoda používaná zejména při zpracování nepřesných dat(typicky experimentálních empirických dat získaných například měřením). Metoda je v základní podobě určená pro řešení nekompatibilních soustav lineárních rovnic(v obecnější podobě hovoříme o nelineární metodě nejmenších čtverců), díky čemuž je fakticky ekvivalentní tzv. lineární regresi.
Řešme nehomogenn soustavu linearnch rovnic Ax = b
A je matice o rozměrech m × n a soustava má řešení právě tehdy, když b ∈ rngA, jinak je soustava přeurčená(typicky, když m>n, víc rovnic než neznámých)
V našem případě řešíme přeurčenou soustavu, tedy hledáme takové x, že vzdálenost mezi body Ax a b je co nejmenší, tedy:
min{||Ax-b|||x ∈ R n }
Místo normy klidně můžeme minimalizovat její čtverec:
||Ax-b| | 2
1.1 Použití na regresi:
Regrese je modelování zavislosti proměnné y ∈ R na proměnné t ∈ T regresn funkcí y = f(t, x), která je známá, až na parametry x ∈ R n Je dán soubor dvojic ( t i , y i ) , i = 1, ... ,m, kde měření y i ∈ R jsou zatížena chybou. Úkolem je najít parametry x, aby y i f(t i , x). Podle metody nejmensch ctvercu tedy resme.
min x ∈ R n ∑ m i=1(f( t i ,x ) - y i ) 2
2 Analytické podmínky na lokální extrémy
2.1 Volné extrémy
V tomto případě hledáme lokální extrémy funkce.
Máme dva důležité typy bodů:
stacionární bod - bod, kde je funkce diferencovatelná a všechny parciální derivace jsou nulové.
kritický bod - bod, který je buď stacionární nebo v něm není funkce diferencovatelná.
2.1.1 Podmínka prvního řádu
Všechny kritické body jsou podezřelé z volného lokálního extrému.
1
Když počítáme příklad nejdříve uděláme všechny parciální derivace, následně je položíme rovny nule a vyřešíme soustavu rovnic => kritické body
2.1.2 Podmínky druhého řádu
f má v bodě x ostré lokální minimum[maximum] na X právě tehdy, když Hessova matice druhých derivací f''(x) je pozitivně
2
V příkladech hledáme vlastní čísla matice, když jsou všechna > 0, pak je poz. def.
[negativně
3
V příkladech hledáme vlastní čísla matice, když jsou všechna < 0, pak je neg. def.
] definitní.
Je-li f''(x) indefinitní
4
V příkladech hledáme vlastní čísla matice, když existuje vlastní číslo, které < 0 a zároveň existuje vlastní číslo, které >0, pak je matice indefinitní
, nemá f v x lokální minimum ani lokální maximum na X.
Je-li f''(x) pozitivně[negativně] semidefinitní, nevíme o tomto bodě jestli je minimem, maximem nebo ani jedno z toho.
2.2 Vázané extrémy
V tomto případě hledáme lokální extrémy funkce za určité podmínky dané nejčastěji jinou funkcí nebo funkcemi.
2.2.1 postup
Extrémy hledáme za pomoci lagrangeových multiplikátorů λ , řešíme rovnici:
f'( x ) + λ g'( x ) = 0 T
5
Tedy v praxi si napíšeme zadání a podmínky si převedeme do tvaru, kdy je na jedné straně rovnice nula a roznásobíme je λ 1 až λ n , tento výraz se nazývá Lagrangeova funkce, ze které spočítáme první derivace a vyřešíme soustavu rovnic, z níchž dostaneme body podezřelé z extrémů.(zjištění druhu extrému je podle skript i wernera složité a v OPT vůbec nebylo)
3 Numerické metody pro optimalizaci bez omezení
U všech dále zmíněných případů se jedná o iterační numerické metody pro nalezení volného lokálního minima diferencovatelných funkcí na množině R n
3.1 Gradientní metoda
Metoda volí směr sestupu jako záporný gradient funkce f v bode x k
PREVIOUS
1 Metoda nejmenších čtverců
2 Analytické podmínky na lokální extrémy
3 Numerické metody pro optimalizaci bez omezení