Informace k přednášce Konvexní optimalizace NMMB409

Povinná přednáška  pro studenty 1. ročníku nmgr studia oboru Matematika pro informační technologie (MIT)

Vyučující

Jiří Tůma - přednášky, Matěj Lébl - cvičení

Místo a čas

Seminární místnost katedry algebry, pondělí a středa 12:20 -13:50  (přednášky)

Posluchárna K11, středa 15:40 - 17:10 (cvičení)

Konzultace

Možno domluvit osobně po přednášce, e-mailem nebo telefonem 2 2191 3240.

Zkoušky

požadavky - kalkulus konvexních množin a konvexních funkcí, dualita pro lineární optimalizaci, pro obecnou kuželovou optimalizaci, slabá a silná  dualita

součástí zkoušky bude písemka

Zadání zkoušky, datové soubory janecek_data.txt, PL_data_fitting.txt

Požadavky na zápočet

maximálně tři absence na cvičení, domácí úkoly, zápočtová úloha na posledním cvičení

Literatura a další zdroje

Boyd and Vanderberge, Convex Optimization, zde
Přednášky a slajdy ke kurzu Convex Optimization 1, přednesenému na Stanford University v roce 2008 

Minikurz konvexní optimalizace přednesený Stephenem Boydem v Tübingenu v roce 2015

Ben-Tal and Nemirovski, Lectures on Modern Convex Optimization, zde

Stručné obsahy přednášek

3.10.2016 formulace úlohy matematické optimalizace, terminologie (účelová funkce, omezující podmínky, přípustné řešení, omezemná úloha, řešitelná úloha, optimální řešení, optimální hodnota), typické úlohy - slajdy č. 5-9 k minikurzu, typické modely vedoucí na optimalizační úlohy - slajd 10,  úloha na nejmenší čtverce - geometrický význam, analytické řešení, úloha lineárního programování - geometrický význam, str. 1-15 v knize

5.10.2016 formulace úlohy konvexní optimalizace, oblasti aplikací vedoucí na úlohy konvexní optimalizace - slajd 15 minikurzu, obtížnost rozpoznání, že úloha matematické optimalizace je konvexní - slajdy 1.9 - 1.11 kurzu, afinní a konvexní množiny, afinní a konvexní obal, konvexní kužel, kuželový obal, příklady konvexních množin (afinní množiny, poloprostory, euklidovské koule a elipsy), str. 20-30 v knize

10.10.2016 opakování pozitivně (semi)definitních matic, další příklady konvexních množin (koule a kužele určené normami, polyedry, pozitivně semidefinitní kužel, kužel druhého řádu),  str. 30 - 35 v knize

12.10.2016  operace zachovávající konvexitu (průnik, afiiní obraz a vzor konvexní množiny, kartézský součin, součet, množina všech řešení lineární maticové nerovnosti, obraz a vzor perspektivní a lineární lomenou funkcí), str. 31-42 knihy,  

17.10.2016  definice konvexní a konkávní funkce, ekvivalentní podmínka pro restrikce na přímku, ekvivalentní podmínka pomocí epigrafu/hypografu,  podmínky konvexity pro diferencovatelné a dvakrát diferencovatelné funkce, příklady (exponenciální funkce, mocniny, mocniny absolutní hodnoty, logaritmus, negativní entropie, normy, max-funkce, kvadratická-lomená funkce, log-sum-exp, geometrický průměr, log-det), str. 67-79 v knize,

19.10.2016 epigraf a hypograf funkce, úrovňové množiny (sublevel sets), operace s funkcemi zachovávající konvexitu, nezáporný vážený součet, složení s afinní funkcí (log-bariérová funkce, norma složená s afinní funkcí), bodové maximum a supremum (po částech lineární funkce, součet $r$ největších složek vektoru, vzdálenost k nejvzdáleněnšímu bodu konvexní množiny, maximální vlastní číslo symetrické matice), složení funkcí - odvození vlastností zajišťujících konvexitu složení, minimalizace (vzdálenost k nejbližšímu bodu konvexní množiny), perspektivita,  str. 79-90 knihy, informace o kvazikonvexních, log-konvexních a log-konkávních funkcích, str. 95-108 v knize,

Vše dosud uvedené je obsaženo v prvních čtyřech přednáškách. Ve videopřednáškách je i něco navíc, později se k tomu vrátíme.

24.10.2016  polyedry a polyedrálné reprezentovatelné množiny, Fourierova-Motzkinova eliminace,

26.10.2016  homogenni Farkasovo lemma, věta o alternativě pro soustavy lineárních nerovností, duální úloha k úloze lineárního programování, slabá věta o dualitě pro LP

31.10.2016 věta o dualitě pro lineární programování, nutná a postačující podmínka pro optimalitu řešení pro lineární programování, ekvivalentní formulace s lineární účelovou funkcí pro obecnou úlohu konvexní optimalizace, úlohy kvadratické optimalizace a jejich ekvivalentní formulace pomocí kuželů druhého řádu,

7.11.2016  uspořádání určené konvexním kuželem, bodový kužel a regulární kužel, duální kužel a jeho vlastnosti, optimalizační úloha kuželového programování (CP),

9.11.2016  duální úloha (CP*) k k úloze kuželového programování, její geometrický význam, věta o dualitě pro úlohu kuželového programování

14.11.2016 Bakalářské promoce

16.11.2016 Horní a dolní meze pro optimální hodnotu obecné úlohy s omezujícími nerovnostmi (IC), řešitelnost a neřešitelnost odpovídajících soustav nerovností, Slaterova podmínka, věta o alternativě pro obecnou úlohu (IC)

21.11.2016  Lagrangián a Lagrangeova duální funkce pro obecnou optimalizační úlohu s omezujícími nerovnostmi (IC), duální úloha (IC*), slabá dualita, věta o silné dualitě pro konvexní úlohu (IC) splňující Slaterovu podmínku, charakterizace silné duality pomocí sedlových bodů, "complementary slackness", Karush-Kuhn-Tuckerovy podmínky pro silnou dualitu, 

23.11.2016  dualita pro obecné úlohy s omezujícími nerovnostmi a rovnostmi, Lagrangián, Lagrangeova duální funkce, slabá a silná dualita, KKT-podmínky,
aplikace konvexní optimalizace na úlohy aproximace

28.11.2016  Úlohy na aproximaci a "fitting" 1

30.11.2016  Úlohy na aproximaci a "fitting" 2

5.12.2016  Statistické odhady 1

7.12.2016   Statistické odhady 2

12.12.2016  Geometrické úlohy 1

14.12.2016  Geometrické úlohy 2

19.12.2016 Algoritmy pro řešení úloh bez omezujících podmínek 1

21.12.2016  Algoritmy pro řešení úloh bez omezujících podmínek 2

4.1.2017  Algoritmy pro řešení úloh s omezujícími rovnostmi

9.1.2017  Metody vnitřního bodu 1

11.1.2017  Metody vnitřního bodu 2