Konvexní optimalizace
Rozvrh
Po, 14:00 – 15:30, přednáška v K8
Út, 12:20 – 13:50, cvičení v K5
St, 17:20 – 18:50 12:20 – 13:50, přednáška v K7
Podmínky pro zápočet
Získat dostatek bodů z domácích úkolů a patnáctiminutovek na cvičeních.
Celkem bude 12 sad domácích úkolů (každý za 10 bodů) a 12 patnáctiminutovek na cvičení.
K získání zápočtu potřebuje aspoň 160 bodů (tj. dvě třetiny) a body je potřeba získávat průběžně
(se záchrannými úlohami navíc se nepočítá).
Zápočet potřebujete k přihlášení se ke zkoušce.
Konzultace
Konzultační hodiny: Každý pátek od 12.20 do 13.50 11.00 do 12.30 v malé seminárce Katedry algebry (vystoupejte do 3. patra, vejděte na KA a jděte směrem na konec chodby – malou seminárku budete míjet po pravé ruce)
Č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 9.10.2017:
- Stáhněte si skripta
- Projděte si kapitolu 3 skript, naučte se především definici konvexní, konjugované a kvazikonvexní funkce.
- Nainstalujte a zprovozněte CVXOPT pro Python 3 (doporučená verze Pythonu je 3.5.4).
- Pro zájemce: Nainstalujte si CVXPY, který toho umí víc než CVXOPT.
- Do 16.10.2017:
- 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 23.10.2017:
Z kapitoly 3 a 4 skript si nastudujte:
- definici monotonie vůči zobecněné nerovnosti (sekce 3.6)
- definici konvexity vůči zobecněné nerovnosti (sekce 3.7)
- definici optimalizačního problému se zobecněnými nerovnostmi v omezeních (4.6)
- definici vektorového optimalizačního problému (4.7.1)
- Do 30.10.2017 si přečtěte v kapitole 5:
- Definici Lagrangeovy duální funkce
- Jak Lagrangeova duální funkce souvisí s dolními odhady optimální hodnoty
- Jak Lagrangeova duální funkce souvisí s konjugovanými funkcemi (sekce 5.1.6)
- Do 6.11.2017 si přečtěte v kapitole 5:
- Definici Lagrangeova duálního problému
- Co to znamená silná dualita a proč je užitečná
- Znění Slaterovy podmínky pro silnou dualitu
- Do 13.11.2017 si přečtěte v kapitole 5:
- Co je to komplementarita (complementary slackness)
- Znění KKT podmínek
- Do 20.11.2017 si přečtěte v kapitole 5:
- Znění KKT podmínek
- Jak dualita souvisí s hrami s nulovým součtem
- Jak optimální duální řešení souvisí s cenami jednotlivých omezení
- Do 27.11.2017 si přečtěte v kapitole 6:
- Co je to reziduál, aproximační/regresní problém, penalizační funkce
- Rozmyslete si, proč nejmenší čtverce nemusí vždy být jediná správná aproximační metoda
- Do 4.11.2017 si přečtěte v kapitole 7:
- Co jsou to odhady metodou maximální věrohodnosti (maximum likelihood estimation)
- Co je to logistická regrese
- Co je to maximální a posteriori odhad (připomeňte si při té příležitosti Bayesovu větu)
- Do 11.11.2017 si přečtěte v kapitole 8:
- Co je to Čebyševův střed množiny a jak zhruba se počítá (8.5)
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, 10.10.2017
- Sada 2, termín odevzdání je 12:21, 17.10.2017 Data k úloze 5
- Sada 3 (opraven překlep v první úloze), termín odevzdání je 12:21, 24.10.2017
- Sada 4, termín odevzdání je 12:21, 31.10.2017
- Sada 5, termín odevzdání je 12:21, 7.11.2017
- Sada 6, termín odevzdání je 12:21, 14.11.2017
- Sada 7, termín odevzdání je 12:21, 21.11.2017
- Sada 8 (opraveny nerovnosti ve čtvrté úloze), termín odevzdání je 12:21, 28.11.2017
- Sada 9, termín odevzdání je 12:21, 5.12.2017 Data k úloze o goblinech
- Sada 10, termín odevzdání je 12:21, 12.12.2017
- Sada 11, termín odevzdání je 12:21, 19.12.2017
- Sada 12 (opravená 2. a 4. úloha; nečekejte příliš dobrou konvergenci gradientové metody), termín odevzdání je 12:21, 9.1.2017
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)
- 2.10.2017: Úvod, základní optimalizační termíny (přípustné řešení, (ne)omezená úloha, (ne)přípustná úloha, optimální řešení, optimální hodnota), ochutnávka úloh (nejmenší čtverce, lineární programování)
- 4.10.2017: Konvexní množiny, afinní a konvexní obal, konvexní kužel
- 9.10.2017: Dokončení konvexních množin, pozitivně (semi)definitní matice, konvexní funkce
- 11.10.2017: Jak poznat konvexní funkci z derivací, epigraf funkce, kvazikonvexní funkce, operace zachovávající konvexitu, příklady složitějších konvexních funkcí
- 16.10.2017: Jensenova nerovnost, konjugovaná funkce, taxonomie konvexních optimalizačních problémů s příklady, pojmy účelová funkce a omezující podmínky
- 18.10.2017: LP, QP, QCQP, SOCP, FLP, příklady převodu optimalizačních problémů do jednoduššího (např. konvexního) tvaru
- 23.10.2017: Geometrické programování, podmínky pro optimalní řešení
- 25.10.2017: Zobecněné nerovnosti a jejich použití
- 30.10.2017: Kuželové programování, multikriteriální optimalizace
- 1.11.2017: Lagrangeova duální funkce, slabá věta o dualitě, dualita LP
- 6.11.2017: Dualita a konjugované funkce, silná věta o dualitě pro úlohy splňující Slaterovu podmínku
- 13.11.2017: Důkaz silné věty o dualitě poprvé
- 15.11.2017: Dokončení důkazu silné věty o dualitě ze zobecněné Slaterovy podmínky, komplementarita
- 20.11.2017: Dualita a teorie her
- 22.11.2017: Karush-Kuhn-Tuckerovy podmínky pro silnou dualitu. Dualita pro
zobecněné nerovnosti (kuželové programování). Dualita a senzitivita na vstupní podmínky.
- 27.11.2017: Regrese, aproximace, fitování funkcí a pod. Minimalizace Ax-b vůči
různým normám.
- 29.11.2017: Robustní aproximace, aplikace duality a aproximace ve strojovém učení pro Support Vector Machines
- 4.12.2017 : Odhady metodou maximální věrohodnosti
- 6.12.2017 : Bayesovské odhady
- 11.12.2017: Testování hypotéz, návrh experimentů
- 13.12.2017: A-, D- a E-optimální návrh experimentů, Löwner-Johnův elipsoid, maximální vepsaný elipsoid
- 18.12.2017: Algoritmy pro konvexní optimalizaci, úvod do minimalizace bez omezujících podmínek
- 20.12.2017: Gradientový sestup, Newtonova metoda
- 3.1.2018: Algoritmy pro řešení úloh s omezujícími rovnostmi
- 8.1.2018: Metody vnitřního bodu 1
- 10.1.2018: Metody vnitřního bodu 2
Program cvičení (změna programu také vyhrazena)
Skripta a přednášky ze Stanfordu