PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Výpočetní aspekty optimalizace - NMEK436
Anglický název: Computational Aspects of Optimisation
Zajišťuje: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2018
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: angličtina, čeština
Způsob výuky: prezenční
Garant: doc. RNDr. Martin Branda, Ph.D.
Třída: M Mgr. PMSE
M Mgr. PMSE > Povinně volitelné
Kategorizace předmětu: Matematika > Matematická ekonomie a ekonometrie, Optimalizace
Prerekvizity : NMSA403
Anotace -
Poslední úprava: T_KPMS (04.05.2015)
Výpočetní postupy pro optimalizační úlohy. Algoritmy pro lineární, nelineární, celočíselné a stochastické programování. Metoda větvení a mezí, metoda sečných nadrovin. Lagrangeova dualita, metody vnitřního bodu, bariérové a penalizační funkce. Bendersova dekompozice. Úvod do výpočetní složitosti. Optimalizační úlohy se speciální strukturou. Přehled softwarů pro optimalizaci a jejich praktické použití.
Cíl předmětu -
Poslední úprava: T_KPMS (04.05.2015)

Studenti se seznámí s aktuálními přístupy k řešení optimalizačních úloh. Podíváme se na reálné aplikace vedoucí na optimalizační úlohy lineárního, nelineárního, celočíselného a stochastického programování. Důraz bude rovněž kladen na řešení konkrétních úloh pomocí vhodného softwaru (GAMS, Matlab apod.).

Podmínky zakončení předmětu - angličtina
Poslední úprava: RNDr. Jitka Zichová, Dr. (05.03.2018)

The exercise class credit is necessary to sign up for the exam.

Requirements for exercise class credit: The credit for the exercise class will be awarded to the student who is present at the exercise class sessions (two absences are tolerated) and hands in a satisfactory solution to each of four assignments (3 standard and one final) by the prescribed deadline.

The nature of these requirements precludes any possibility of additional attempts to obtain the exercise class credit.

Literatura
Poslední úprava: T_KPMS (04.05.2015)

Bazaraa, M.S., Sherali, H.D., Shetty, C.M. (2006): Nonlinear programming: theory and algorithms. Wiley, Singapore.

Boyd, S., Vandenberghe, L. (2004): Convex Optimization, Cambridge University Press, Cambridge.

Charamza, P. et. al. (1993): Modelling system GAMS, MFF UK, (in Czech).

Kopa, M. et al. (2008): On Selected Software for Stochastic Programming, Matfyzpress, Prague.

Nocedal, J., Wright, S.J. (2006): Numerical optimization. Springer, New York.

Metody výuky -
Poslední úprava: T_KPMS (04.05.2015)

Přednáška + cvičení.

Požadavky ke zkoušce - angličtina
Poslední úprava: RNDr. Jitka Zichová, Dr. (05.03.2018)

The exam consists of two questions focused on the topics discussed during the lectures. The students must prove that they understand to the methods and algorithms and are able to apply them to examples.

Sylabus -
Poslední úprava: T_KPMS (04.05.2015)

1. Duální simplexový algoritmus pro LP. Wolfeho algoritmus pro úlohy kvadratického programování

2. Úvod do výpočetní složitosti

3. Celočíselné lineární programování - základní vlastnosti, algoritmus B&B, Gomoryho řezy, úlohy rozvozu, rozvrhování, výroby a skladování

4. Lagrangeova dualita v nelineárním programování - slabá a silná věta o dualitě

5. Algoritmy pro úlohy nelineárního programování - (quasi-)Newtonova metoda ve více rozměrech, penalizační a bariérové metody, metody vnitřního bodu, SQP, duální algoritmy

6. Bendersova dekompozice, L-shaped algoritmus

7. Minimaxové úlohy - s aplikacemi v maticových hrách

8. Přehled optimalizačních úloh se speciální strukturou - semi-infinitní, semi-definitní a geometrické programování, SOCP, DC, MPEC

9. Dynamické programování

Vstupní požadavky -
Poslední úprava: doc. RNDr. Martin Branda, Ph.D. (24.04.2018)

Vstupní požadavky zahrnují znalosti:

  • Lineárního programování (struktura množiny přípustných řešení - krajní body a směry, simplexový algoritmus, dualita a její interpretace)
  • Celočíselného programování (branch & bound)
  • Nelineárního programování (Karush-Kuhn-Tuckerovi podmínky optimality, podmínky regularity)
  • Konvexita množin a funkcí

Tato témata jsou pokryta přenáškami Úvod do optimalizace (NMSA336) a Teorie optimalizace (NMSA336).

 
Univerzita Karlova | Informační systém UK