Základy spojité optimalizace Grygarová 6.6.2012

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:

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.