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 2022
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• 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.
• Vyučující: doc. RNDr. Martin Branda, Ph.D.; Ing. Vít Procházka, Ph.D.
• Třída: M Mgr. PMSE; M Mgr. PMSE > Povinně volitelné
• Kategorizace předmětu: Matematika > Matematická ekonomie a ekonometrie, Optimalizace

Anotace

čeština

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í.

Poslední úprava: T_KPMS (04.05.2015)

angličtina

Computational approaches to optimization problems. Algorithms for linear, nonlinear, integer and stochastic programming problems. Branch and bound, cutting plane method. Lagrange duality, interior-point method, barrier and penalty functions. Benders decomposition. Introduction to computational complexity. Optimization problems with a special structure. Software tools for optimization.

Poslední úprava: T_KPMS (04.05.2015)

Cíl předmětu

čeština

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.).

Poslední úprava: T_KPMS (04.05.2015)

angličtina

Modern approaches to optimization are introduced. Real-life applications leading to linear, nonlinear, integer and stochastic programming problems are discussed. A special attention is paid to software tools (GAMS, Matlab etc.).

Poslední úprava: T_KPMS (04.05.2015)

Podmínky zakončení předmětu

čeština

Získání zápočtu je nutnou podmínkou pro účast na zkoušce.

Podmínky získání zápočtu: Odevzdání uspokojivého řešení 4 domácích úloh v daném termínu, které budou zadány v průběhu semestru.

Povaha zápočtu neumožňuje jeho opakování.

Poslední úprava: Branda Martin, doc. RNDr., Ph.D. (16.01.2024)

angličtina

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 hands in a satisfactory solution to each of five assignments (4 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.

Poslední úprava: Branda Martin, doc. RNDr., Ph.D. (16.01.2024)

Literatura

čeština

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.

Poslední úprava: T_KPMS (04.05.2015)

angličtina

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.

Poslední úprava: Branda Martin, doc. RNDr., Ph.D. (06.01.2021)

Metody výuky

čeština

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

Poslední úprava: T_KPMS (04.05.2015)

angličtina

Lecture + exercises.

Poslední úprava: T_KPMS (04.05.2015)

Požadavky ke zkoušce

čeština

Při zkoušce student dostane dvě otázky na témata probíraná v průběhu semestru. Student musí prokázat dostatečné porozumění danému tématu a umět aplikovat postupy na příkladech.

Poslední úprava: Branda Martin, doc. RNDr., Ph.D. (16.01.2024)

angličtina

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.

Poslední úprava: Zichová Jitka, RNDr., Dr. (05.03.2018)

Sylabus

čeština

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í

Poslední úprava: T_KPMS (04.05.2015)

angličtina

1. Dual simplex algorithm for LP. Wolfe algorithm for quadratic programming

2. Introduction to computational complexity

3. Integer linear programming - basic properties, branch-and-bound, cutting planes and Gomory cuts, vehicle routing problem, scheduling, lot-sizing, sparse optimization

4. Lagrange duality in nonlinear programming

5. Algorithms for nonlinear programming - quasi-Newton method, barier and penalty functions, interior point methods, SQP, alg. based on duality

6. Benders decomposition, L-shaped alg.

7. Minimax problems

8. Optimization problems with a special structure - semi-infinite, semi-definite and geometric prog., SOCP, DC, MPEC

9. Dynamic programming

Poslední úprava: T_KPMS (04.05.2015)

Vstupní požadavky

čeština

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 (NMFM204) a Teorie optimalizace (NMSA403).

Poslední úprava: Zichová Jitka, RNDr., Dr. (01.05.2021)

angličtina

This course assumes knowledge of:

• Linear programming (structure of the set of feasible solutions - extreme directions and rays, simplex algorithm, duality and its interpretation)

• Integer programming (branch & bound)

• Nonlinear programming (Karush-Kuhn-Tucker optimality conditions, constraint qualification conditions)

• Convexity of sets and functions

These topics are covered by Introduction to optimization (NMFM204), and Optimization theory (NMSA403).

Poslední úprava: Zichová Jitka, RNDr., Dr. (01.05.2021)