Teorie optimalizace - NMSA413

• Anglický název: Optimisation Theory
• Zajišťuje: Katedra pravděpodobnosti a matematické statistiky (32-KPMS)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 8
• Rozsah, examinace: zimní s.:4/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: čeština, angličtina
• Způsob výuky: prezenční
• Garant: doc. RNDr. Petr Lachout, CSc.; doc. RNDr. Martin Branda, Ph.D.
• Vyučující: doc. RNDr. Martin Branda, Ph.D.; doc. RNDr. Petr Lachout, CSc.; Ing. Vít Procházka, Ph.D.
• Třída: M Mgr. FPM; M Mgr. FPM > Volitelné; M Mgr. PMSE; M Mgr. PMSE > Povinné
• Kategorizace předmětu: Matematika > Optimalizace
• Neslučitelnost : NMSA403
• Záměnnost : NMSA403
• Je neslučitelnost pro: NMSA403
• Je prerekvizitou pro: NMEK450, NMEK521
• Je záměnnost pro: NMSA403

Anotace

čeština

Optimalizace v ekonomii a v matematické statistice. Základy konvexní analýzy. Teorie lineárního a nelineárního programování. Symetrická úloha nelineárního programování. Předpoklady: Lineární algebra, funkcionální analýza (funkce více proměnných, vázané extrémy).

Poslední úprava: Omelka Marek, doc. Ing., Ph.D. (07.12.2020)

angličtina

Optimization in economy and in mathematical statistics. Basis of convex analysis. Theory of linear and nonlinear programming. Symmetric nonlinear programming. Supposed knowledge: Linear algebra, functional analysis (functions with several arguments, constraint extrema problems).

Poslední úprava: Omelka Marek, doc. Ing., Ph.D. (07.12.2020)

Cíl předmětu

čeština

Vyložit základní postupy a metody používané při hledání optimálního řešení zadané úlohy. Studenti se dozvědí potřebnou teorii a dané postupy si na numerických příkladech osvojí.

Poslední úprava: Omelka Marek, doc. Ing., Ph.D. (30.11.2020)

angličtina

To give explanation and theoretical background for standard optimization procedures. Students will learn necessary theory and practice their knowledge on numerical examples.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)

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

čeština

+---------------------------------------------------------------------------

Zakončení předmětu

+---------------------------------------------------------------------------

K zakončení předmětu je nutno získat zápočet ze cvičení a úspěšně složit zkoušku.

Zápočet ze cvičení je nutnou podmínkou pro účast na zkoušce.

Podmínky pro získání zápočtu ze cvičení jsou uvedeny na webu:

https://www2.karlin.mff.cuni.cz/~branda/mbOpt11.html

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

angličtina

+---------------------------------------------------------------------------

Course finalization

+---------------------------------------------------------------------------

The course is finalized by a credit from the exercises class and exam.

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

Conditions for receiving credits from exercises class are available on the web page:

https://www2.karlin.mff.cuni.cz/~branda/mbOpt11.html

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

Literatura

Bazaraa, M.S.; Sherali, H.D.; Shetty, C.M.: Nonlinear programming: theory and algorithms. Wiley, New York, 1993.

Dantzig, G.B.; Thapa, M.N.: Linear programming. 1,2. Springer, New York, 1997.

Plesník, J.; Dupačová, J.; Vlach, M.: Lineárne programovanie. Alfa, Bratislava, 1990. (in Czech)

Rockafellar, T.: Convex Analysis. Springer-Verlag, Berlin, 1975.

Literatura pro další studium:

Bertsekas, D.P.: Nonlinear programming. Athena Scientific, Belmont, 1999.

Luenberger, D.G.; Ye, Y.: Linear and Nonlinear Programming. 3rd edition, Springer, New York, 2008.

Rockafellar, T.; Wets, R. J.-B.: Variational Analysis. Springer-Verlag, Berlin, 1998.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)

Metody výuky

čeština

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

Poslední úprava: Omelka Marek, doc. Ing., Ph.D. (30.11.2020)

angličtina

Lecture + exercises.

Poslední úprava: Omelka Marek, doc. Ing., Ph.D. (30.11.2020)

Požadavky ke zkoušce

čeština

+---------------------------------------------------------------------------

Požadavky ke zkoušce jsou:

+---------------------------------------------------------------------------

Zkouška má písemnou a ústní část. Písemná část předchází části ústní, její nesplnění znamená, že celá zkouška je hodnocena známkou nevyhověl(a) a ústní částí se již nepokračuje. Známka ze zkoušky se stanoví na základě hodnocení písemné a ústní části.

Po nesložení zkoušky je při příštím termínu nutno opakovat obě části zkoušky, písemnou i ústní.

U zkoušky je zkoušena látka v rozsahu odpředneseném na přednášce a partií určených přednášejícím k samostudiu.

Zápočet je nutnou podmínkou pro účast na zkoušce.

Podmínky pro získání zápočtu ze cvičení jsou:

• Odevzdání vyřešeného domácího úkolu ve stanoveném termínu.

• Úspěšné složení písemného testu na konci semestru (nutné získat alespoň 70% bodů).

• Skládání zápočtu nelze opakovat.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (14.02.2024)

angličtina

+---------------------------------------------------------------------------

Requirements to exam

+---------------------------------------------------------------------------

The exam is contained from a written part and an oral part. Written part is foregoing to oral part.

If written part is not fulfilled, whole exam is marked as non-satisfactory, and oral part is not treated.

Mark from the examination is determined considering results from both written and oral part.

If student did not pass the exam, he must repeat both written part and oral part next time.

Examination is checking knowledge of all topics read at the lecture and parts given to self-study by the course lecturer.

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

Conditions for receiving of a credit from practical class are:

• Handing in solved homework by the deadline.

• Successful passing of a test at the end of the semester (it is necessary to get at least 70% of available points).

• Attempt to receive a credit from practical class cannot be repeated.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (14.02.2024)

Sylabus

čeština

1. Typy optimalizačních úloh a jejich formulace. Aplikace v ekonomii a v matematické statistice.

2. Vybrané partie z konvexní analýzy (konvexní množiny, konvexní kužele, krajní body, krajní směry).

3. Vybrané partie z teorie reálných funkcí. Diferencovatelnost v Peanově smyslu. Konvexní funkce více proměnných (epigraf, subgradient, subdiferenciál).

4. Věty o oddělitelnosti množin (Farkasova věta).

5. Teorie lineárního programování (struktura množiny přípustných řešení, základní věta lineárního programování, dualita).

6. Přímá metoda řešení úloh lineárního programování, simplexová metoda, duální simplexová metoda, postoptimalizace.

7. Teorie nelineárního programování (globální podmínka optimality, Karushovy-Kuhnovy-Tuckerovy podmínky optimality, podmínky regularity).

8. Symetrická úloha nelineárního programování.

9. Lineární a konvexní programování jako speciální případ nelineárního programování.

10. Dopravní problém jako speciální typ úlohy lineárního programování.

11. Hlavní myšlenky algoritmů pro nelineární programování.

12. Maticové hry a lineární programování, minimaxová věta.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)

angličtina

1. Optimization problems and their formulations. Applications in economy and in mathematical statistics.

2. Selected parts of convex analyses (convex sets, convex cones, extreme points, extreme directions).

3. Selected parts of functional theory. Differentiation in Peano sense. Convex functions with several variables (epigraph, subgradient, subdiferential).

4. Separation theorems (Farkas theorem).

5. Theory of linear programming (structure of the set of all feasible solutions, basic theorem of linear programming, duality).

6. Direct method for solving linear programming, simplex method, dual simplex method, postoptimization.

7. Theory of nonlinear programming (saddle point condition, Karush-Kuhn-Tucker optimality conditions, constraint qualifications).

8. Symmetric nonlinear programming.

9. Linear and convex programming as a particular case of nonlinear programming.

10. Transport problem as a particular case of linear programming.

11. Main ideas of algorithms for nonlinear programming.

12. Matrix games and linear programming, minimax theorem.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)

Vstupní požadavky

čeština

Lineární algebra, funkcionální analýza.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)

angličtina

Linear algebra, functional analysis.

Poslední úprava: Lachout Petr, doc. RNDr., CSc. (05.12.2020)