|
|
|
|
Přednášku vedu společně s M. Loeblem.
Přednáška je rozvržena na pondělí od 15:40.
Cvičení není třeba rozvrhovat, koná se formou domácích úkolů a konzultací.
Při distanční výuce se bude přednáška konat pomocí aplikace zoom. Prihlašovací údaje dostanete e-mailem.
Probraná a plánovaná témata:
| 5.10. | Připomenutí konvexity: konvexní množiny, konvexní funkce, konvexní optimalizace. Kvazikonvexní a explicitně kvazikonvexní funkce: definice, příklady, charakterizace pomocí sublevel sets a prvních derivací.
[skripta: kapitoly 1-2 a sekce 3.1] |
| 12.10. | Zjišťování kvazikonvexity: maximum, součin, podíl, skládání funkcí atp. Kvazikonvexní funkce v optimalizaci: ostré lokální minimum je globálním, množina optimálních řešení je konvexní, podmínka optimality. Zobecněné lineární frakcionální programování a von Neumannův model růstu. Pseudokonvexní funkce: vztah ke konvexním a kvazikonvexním, podmínky optimality v pseudokonvexní optimalizaci.
[skripta: sekce 3.2-3.5] |
| 19.10. | Připomínka Farkasova lemmatu, Gordanova věta. Nutné podmínky optimality: podmínky Fritze Johna, Karush-Kuhn-Tuckerovy (KKT) podmínky. Kvalifikace omezení pro KKT: lineární nezávislost, Slaterova podmínka a Abadieho podmínka.
(bez důkazu pomocného lemmatu a vztahů 3 kvalifikací omezení)
[skripta: sekce 4.1-4.2 (do věty 4.13)] |
| 26.10. | KKT a lieární relaxace, postačující KKT podmínky pro optimalitu, podoba KKT pro lineární a kvadratické programování.
Lagrangeova dualita: duální funkce a duální úloha, slabá dualita, geometrická interpretace, mez na optimální hodnotu.
[skripta: sekce 4.2-4.3, 5.1] |
| 2.11. |
Lagrangeova dualita: silná dualita a příklady, analýza citlivosti.
[skripta: sekce 5.2-5.3] |
| 9.11. |
Lagrangeova dualita pro konvexní kvadratické programování a semidefinitní programování. Aplikace prvního v Support vector machines.
[skripta: sekce 5.5-5.6] |
| 16.11. |
L1-metody pro problémy kardinality: příklady, aproximace a její interpretace, minimalizace hodnosti matice.
[skripta: kapitola 6] |
| plán od 23.11. | Přednáší Martin Loebl. |
Zápočtové úkoly: PDF
Literatura:
