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í
• Způsob výuky: prezenční
• Garant: doc. RNDr. Petr Lachout, CSc.; doc. RNDr. Martin Branda, 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

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

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

angličtina

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

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

Cíl předmětu

čeština

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

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

angličtina

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

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

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

čeština

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

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

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

angličtina

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

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

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

Literatura

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

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.

Metody výuky

čeština

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

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

angličtina

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

Lecture + exercises.

Požadavky ke zkoušce

čeština

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

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

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.

angličtina

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

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

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.

Sylabus

čeština

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

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.

angličtina

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

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.

Vstupní požadavky

čeština

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

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

angličtina

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

Linear algebra, functional analysis.