Základy spojité optimalizace Grygarová 6.6.2012

mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Základy spojité optimalizace Grygarová 6.6.2012

Příspěvek od mathemage »

Téma: parametrické programování

nějak výrazně to nečetla, spíš pokládala dobře mířené otázky, kterým testovala, zda tomu rozumím (dle jejich slov není třeba umět každou maličkost, ale rozumět tomu - samozřejmě vtip je v tom, že veškerá "moudrost" je schovaná v důkazech, takže teprve po jejich přečtení jste schopni vymýšlet správné odpovědi).

Doplňující otázky:
1) Proč se vůbec zabýváme PP? - Vyžaduje to praxe. Někdy není přesné zadání (účelové funkce, matice množiny řešení, pravé strany...).
2) 1-paramatrické programování (1 parametr jen v cílové funkci) - co se stane při lineární závislosti obou vektorů cílové funkce? - Zredukuje se na úlohu LP (rozborem možností porovnání \alpha a \lambda pro c = \alpha c' se zbavíme parametru \lambda).
3) Proč je obor řešitelnosti konvexní množina? - Sjednocení intervalů, důležité je, že jsou sousední (díra mezi 2 intervaly by nám zkazila konvexnost, ale nenastane, páč pak by dle 2. věty PP musel 1 z dané párů oborů řešitelnosti spadnout do nekonečného intervalu, kde to řešitelné není).
4) 1. základní věta LP + může se stát, že množina optimálních řešení je sjednocení nějakých 2 hran (obecně stěn)? - Ne, jejich konvexní obal musí celý být v množině optimálních řešení (konvexní kombinace nám dá stejnou hodnotu cíl. funkce, takže zase optimum). Spadl by do toho i vnitřek, 2 hrany jsou prostě málo...

"Triviální zkouška, opravdu se stačí učit den a půl"? -> dva neprošli, 1 za 3, 2 za 1; takže si to přeberte sami, kolik do toho chcete dávat času :twisted:
Naposledy upravil(a) mathemage dne 21. 12. 2012 21:54, celkem upraveno 1 x.
Carpe Diem!
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Základy spojité optimalizace Grygarová 6.6.2012

Příspěvek od Davpe »

Přidám tu ještě zážitky z termínu 27.06.2012

Téma: Nelineární programování - jen teorie bez algoritmů
(další témata co padala: parametrické, celočíselné, vícekriteriální, nelineární - jen algoritmy)

Úlohu NLP a jak se liší od ostatních disciplín
- alespoň jedna z funkcí není lineární

Co je konvexní programování
- všechny funkce musí být konvexní

Pak si stěžovala, že ji někdo neuměl nadefinovat ani konvexní funkci a chtěla ji nadefinovat (což jsem zpaměti nevěděl) a tvářila se jako že když to nezvládnu, tak mě vyhodí (tohle byl můj druhý pokus a když po mě minule chtěla nadefinovat něco co jsem nezvládl, tak se tvářila stejně). Nakonec jsem to teda vymyslel.

Jak poznáme konvexní funkci
- Hessova matice je PSD

Co když funkce není diferenciovatelná, lze nějak poznat že je konvexní
- součet či pozitivní lin. kombinace konvex. funkcí je konvexní
(tady jsem nevěděl, ale napsala na vedlejší papír součet tří konvexních funkcí, tak mi to docvaklo

Nejdůležitější vlastnost konvexních funkcí
- lokální minimum konvexní funkce je absolutní
a náčrt důkazu (načrtl jsem ji 2D důkaz, ale chtěla to obecně, trik je tam, že se to převede to 2D (jakoby pohled shora)

K-T podmínky
(chtěla význam 2. podmínky - optimum je uvnitř množiny funkcí g_j, a co získáme kombinací 4. a 3. podmínky (že u =0 nebo g_j =0 nebo tak něco)

pak se zeptala na dualitu, jen definice, zmínila se, že existují i jiné duality

K čemu jsou K-T podmínky
- bod který je splňuje je optimum

Pro jaké úlohy jsou K-T podmínky obzvlášť vhodné
- kvadratické programování - díky derivacím se to převede na soustavu lineárních rovnic

Tím NLP skončilo (díkybohu se neptala na kvazi/pseudo konvexní a různé jiné hnusy a že jich tam bylo)

Pak se ptala na LP, konkrétně jak získáme další optimální řešení když už jedno máme (ta mají stejnou hodnotu cílové funkce)
- V tabulce najdeme v kriteriálním řádku nulu (u nebázické), a provedeme krok SM.

Co když jsou všechny hodnoty v tomto sloupci záporné
- pak tam leží celá úsečka (to jsem nevěděl)

Výsledně za 1, celkem jsem to tam motal (sama říkala, že to je těsné, přišlo mi to spíš na dvojku) a dost jsem toho nechápal (naštěstí se na to buď neptala nebo se mi to povedlo zamlžit). Sama říkala, že to je přehledová přednáška a že je těžké to jen tak proletět.

Jo a i když máta zadáno jedno téma, tak poté, co ho proberete se ptá na jiné téma (kolegy co měl celočíselné se ptala na nelineární a Franka-Wolfa, dalšího co měl vícekriteriální se ptala na parametrické, mě na lineární apod.)

Jo a přede mnou dostali 3 jedničku, jednoho vyhodila a jeden za 3.
Odpovědět

Zpět na „Ostatní“