Konvexní optimalizace ZS 2018/19
Rozvrh
Po, 15:40 – 17:10, přednáška v K9
Út, 10:40 – 12:10, přednáska v seminárce Katedry algebry (3. patro)
Čt 12:20 – 13:50, cvičení v K7 (vede Barbora Hudcová)
Podmínky pro zápočet
Získat dostatek bodů z domácích úkolů a desetiminutovek na cvičeních.
Celkem bude 12 sad domácích úkolů (každý za 10 bodů) a 12 desetiminutovek na cvičení. K získání zápočtu potřebuje aspoň 160 bodů (tj. dvě třetiny). Za napravení chyb/děr v opraveném řešení je možné získat až 50 % bodů zpátky.
K přihlášení se ke zkoušce potřebujete zápočet.
Pro nástin toho, co můžete očekávat v desetiminutovkách, se podívejte na patnáctiminutovky z loňska
Konzultace
Konzultace po dohodě e-mailem na kazda@karlin.mff.cuni.cz.
Čtenářské úkoly
Abyste byli připraveni na domácí úkoly a cvičení, učiňte následující. Data jsou termíny, do kdy je danou věc potřeba udělat:- Do 8.10.2018:
- Do 16.10.2018:
- Projděte si kapitolu 4 skript, soustřeďte se především na definici (a význam):
- konvexního optimalizačního problému
- kvadratického programu
- kuželového programu (míněn je second order cone program, část 4.4.2, ne cone program)
- semidefinitního programu
- geometrického programu (vč. pojmu posynom).
- Do 29.10.2018:
V kapitole 4 skript se podívejte na:
- definici vektorového optimalizačního problému (4.7.1)
- příklady vektorových a vícekriteriálních optimalizačních problémů (příklad 4.9, sekce 4.7.6)
Domácí úkoly
Krom výjimečných případů (nemoc) se domácí úkoly odevzdávají na začátku cvičení. Pokud je to v zadání výslovně uvedeno, posílejte své programy nebo jejich výstupy před termínem odevzdání na mou adresu kazda@karlin.mff.cuni.cz (v tom případě program nemusíte tisknout).
- Sada 1, termín odevzdání je 12:21, 18. 10. 2018
- Sada 2, termín odevzdání je 12:21, 25. 10. 2018
- Sada 3 , termín odevzdání je 12:21, 1.11.2018 Data k úloze 4
- Sada 4, termín odevzdání je 12:21, 8.11.2018
- Sada 5, termín odevzdání je 12:21, 15.11.2018
- Sada 6, termín odevzdání je 12:21, 22.11.2018
- Sada 7, termín odevzdání je 12:21, 29.11.2018
- Sada 8, termín odevzdání je 12:21, 6.12.2018, opravena chyba v první úloze
- Sada 9, termín odevzdání je 12:21, 13.12.2018 Data k úloze o goblinech
- Sada 10, termín odevzdání je 12:21, 20.12.2018
- Sada 11, termín odevzdání je 12:21, 3.1.2019
- Sada 12, termín odevzdání je 12:21, 10.1.2019
Bez důkazu můžete používat tvrzení z běžných přednášek bakalářského studia a z přednášky. Jinak je třeba v úlohách, které žádají důkaz, vše podrobně dokázat.
Pokud se chcete při řešení poradit s kamarády a kamarádkami, jen do toho, ale řešení sepisujte samostatně a svá sepsaná řešení nesdílejte. Stejná pravidla platí i pro programy.
Program přednášek (změna programu vyhrazena)
- 1. 10. 2018: Úvod, základní optimalizační termíny (přípustné řešení, optimální řešení, optimální hodnota), ochutnávka úloh (nejmenší čtverce, lineární programování)
- 2. 10. 2018: Konvexní množiny, afinní a konvexní obal, konvexní kužel, kužel pozitivně (semi)definitních matic
- 8. 10. 2018: Vlastní kužele, uspořádání vůči kuželu konvexní funkce
- 9. 10. 2018: Jak poznat konvexní funkci z derivací, epigraf funkce, kvazikonvexní funkce, příklady složitějších konvexních funkcí, Jensenova nerovnost
- 15. 10. 2018: Operace zachovávající konvexitu, taxonomie konvexních optimalizačních problémů s příklady
- 16. 10. 2018: LP, FLP, QP, QCQP, SOCP, geometrické programování, převod optimalizačních problémů na ekvivelentní problémy
- 22. 10. 2018: Dokončení geometrického programování, podmínky pro optimalní řešení
- 23. 10. 2018: Zobecněné nerovnosti a jejich použití
- 29. 10. 2018: Kuželové programování, multikriteriální/vektorová optimalizace
- 30. 10. 2018: Nutná a postačující podmínka pro optimální řešení vektorového optimalizačního problému, Lagrangeova duální funkce
- 5. 11. 2018: Slabá věta o dualitě, dualita LP, formulace silné věty o dualitě
- 12. 11. 2018: Důkaz silné věty o dualitě poprvé
- 13. 11. 2018: Dokončení důkazu silné věty o dualitě ze zobecněné Slaterovy podmínky, komplementarita
- 19. 11. 2018: Karush-Kuhn-Tuckerovy podmínky pro silnou dualitu.
- 20. 11. 2018: Dualita a senzitivita na vstupní podmínky.
- 26. 11. 2018: Dualita a teorie her.
- 27. 11. 2018: Regrese, aproximace, fitování funkcí a pod. Minimalizace Ax-b vůči různým normám.
- 3. 12. 2018 : Robustní aproximace, aplikace duality a aproximace ve strojovém učení pro Support Vector Machines
- 4. 12. 2018 : Odhady metodou maximální věrohodnosti
- 10. 12. 2018:Bayesovské odhady
- 11. 12. 2018: Návrh detektorů a experimentů
- 17. 12. 2018: D-optimální návrh experimentů, elipsoidy
- 18. 12. 2018: Löwnerův-Johnův elipsoid, gradientový sestup
- 7. 1. 2019: Newtonova metoda, minimalizace funkce omezené na afinní prostor
- 8. 1. 2019: Metody vnitřního bodu
Program cvičení (změna programu také vyhrazena)
- 4. 10. 2018: Jednoduché lineární a konvexní úlohy, seznámení s knihovnou CVXOPT. Úlohy ze cvičení.
- 11.10.2018: Rozpoznávání konvexních množin a funkcí. Úlohy ze cvičení
- 18.10.2018: Vlastnosti optimálních řešení, práce s konvexními funkcemi. Úlohy ze cvičení
- 25.10.2018: Převod optimalizačních úloh do ekvivalentního tvaru Úlohy ze cvičení
- 1.11.2018: Kuželové programování. Úlohy
- 8.11.2018: Duální kužele. Úlohy
- 15.11.2018: Duální problémy. Úlohy
- 22.11.2018: KKT podmínky Úlohy
- 29.11.2018: Hry s nulovým součtem, aproximace vůči normě. Úlohy
- 6.12.2018: Metoda maximální věrohodnosti, robustní aproximace. Úlohy
- 13.12.2018: Testování hypotéz. Úlohy
- 20.12.2018: Elipsoidy, afinní invariance Úlohy
- 3.1.2019: Elipsoidy Úlohy
- 10.1.2019: Rozšiřující témata pro algoritmy na řešení konvexních problémů Úlohy
Skripta a přednášky ze Stanfordu
- Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
- Slajdy prof. Boyda
- Videa z Boydových přednášek
- CVXOPT
- Jupyter