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