Optimalizační techniky a algoritmy

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Obsahem předmětu je výklad různých druhů optimalizačních technik spolu s algoritmy pro jejich reálné použití. Jedná se o klasické optimalizační techniky, numerické metody optimalizace, úlohy lineárního programování, metody nelineárního programování, dynamické programování, variační metody ve statistice a techniky stochastické aproximace.

Požadavky:

Základní kurzy matematické analýzy a lineární algebry (dle přednášek na FJFI ČVUT v Praze 01MA1, 01MAB2-4, 01LA1, 01LAB2).

Osnova přednášek:

Cílem přednášky je předložit matematické modely různých druhů optimalizačních technik spolu s algoritmy pro jejich reálné použití. Postupy budou ilustrovány a odzkoušeny na praktických úlohách z prostředí pravděpodobnosti a statistiky (regresní analýza, markovské procesy, maximálně věrohodné odhady, apod.).

1. Klasické optimalizační techniky: Zobecněná Lagrangeova metoda, Everettova věta, aplikace: statistický multikomponentní systém, PCA metoda hlavních komponent. Užitečné nerovnosti pro optimalizaci: klasické, kolmogorovská, Chernoffova, Kantorovichova. Numerické metody optimalizace: Fisherova skórovací metoda, EM algoritmus pro neúplná data. Lineární programování: Duální úloha pro Neyman-Pearsonovo zobecněné lemma.

2. Metody nelineárního programování: Sedlové body, Kuhn-Tuckerovy podmínky. Kvadratické programování, Konvexní programování, Čebyševova aproximace, Stochastické programování s pravděpodobnostní vazbou, Geometrické programování, Kondenzační metoda, Aplikace: regresní model s vazbou, odhad pravděpodobností markovského řetězce, model s komponentní variancí v navrhování experimentů, odhad parametrů směsi hustot.

3. Dynamické programování: Deterministický a stochastický model řízení, Bellmanův princip optimality, Pontrjaginův princip maxima, aplikace: deterministický řídící proces, lineární stochastický řídící proces, shluková analýza, obecné markovské řídící procesy, bayesovské řešení pro odhad populace ryb, sekvenční odhadování, optimální návrh experimentů.

4. Variační metody ve statistice: Euler-Lagrangeovy rovnice, postačující podmínky pro extrém, Neyman-Pearsonova technika, nelineární momentový problém, princip maximální entropie, robustní M- a L-odhady, Fisherova informace, penalizovaný odhad metodou maximální věrohodnosti, Wilcoxon-Mann-Whitney testovací statistika.

5. Techniky stochastické aproximace: Neparametrická iterační Robbins-Monroova procedura, distribuční a obecný případ, Kiefer-Wolfowitzův přístup, rekurzivní odhadování, aplikace: nejlepší asymptoticky normální odhad. Metoda náhodného prohledávání, Simulovné žíhání - optimalizace, Kritéria optimality v simulacích.

Osnova cvičení:

1. Klasické optimalizační techniky, EM-algoritmus, Lineární programování.

2. Nelineární programování, regresní model s vazbou, odhad pravděpodobností markovského řetězce, model s komponentní variancí v navrhování experimentů, odhad parametrů směsi hustot.

3. Dynamické programování: deterministický řídící proces, lineární stochastický řídící proces, shluková analýza, obecné markovské řídící procesy, bayesovské řešení pro odhad populace ryb, sekvenční odhadování, optimální návrh experimentu.

4. Euler-Lagrangeovy rovnice, postačující podmínky pro extrém, Neyman-Pearsonova technika, nelineární momentový problém, princip maximální entropie.

5. Nejlepší asymptoticky normální odhad, metoda náhodného prohledávání, Simulovné žíhání - optimalizace, Kritéria optimality v simulacích.

Cíle studia:

Znalosti:

Klasické optimalizační techniky, lineární programování, nelineární programování, dynamické programování, Euler-Lagrangeovy rovnice, postačující podmínky pro extrém, techniky stochastické aproximace.

Schopnosti:

Zvolit správnou optimalizační metodu pro řešení daného typu úlohy, zhodnocení výhod a nevýhod vzhledem k teoretické i numerické náročnosti navržené optimalizace.

Studijní materiály:

Povinná literatura:

[1] J.S. Rustagij, Optimization Techniques in Statistics, London Academic Press, Inc 1994.

Doporučená literatura:

[2] J.Jahn, Introduction to the Tudory of Nonlinear Optimization, Berlin Springer 1996.

Poznámka:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů: