Výpočetní aspekty optimalizace

Sylabus

1. Duální simplexový algoritmus pro LP. Wolfeho algoritmus pro úlohy kvadratického programování

2. Úvod do výpočetní složitosti

3. Celočíselné lineární programování - základní vlastnosti, algoritmus B&B, Gomoryho řezy, úlohy rozvozu, rozvrhování, výroby a skladování

4. Lagrangeova dualita v nelineárním programování - slabá a silná věta o dualitě

5. Algoritmy pro úlohy nelineárního programování - (quasi-)Newtonova metoda ve více rozměrech, penalizační a bariérové metody, metody vnitřního bodu, SQP, duální algoritmy

6. Bendersova dekompozice, L-shaped algoritmus

7. Minimaxové úlohy - s aplikacemi v maticových hrách

8. Přehled optimalizačních úloh se speciální strukturou - semi-infinitní, semi-definitní a geometrické programování, SOCP, DC, MPEC

9. Dynamické programování

Anotace

Výpočetní postupy pro optimalizační úlohy. Algoritmy pro lineární, nelineární, celočíselné a stochastické programování.

Metoda větvení a mezí, metoda sečných nadrovin. Lagrangeova dualita, metody vnitřního bodu, bariérové a penalizační funkce.

Bendersova dekompozice. Úvod do výpočetní složitosti. Optimalizační úlohy se speciální strukturou.

Přehled softwarů pro optimalizaci a jejich praktické použití.