Optimisation Theory - NMSA413

• Title: Teorie optimalizace
• Guaranteed by: Department of Probability and Mathematical Statistics (32-KPMS)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: winter
• E-Credits: 8
• Hours per week, examination: winter s.:4/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Guarantor: doc. RNDr. Petr Lachout, CSc.; doc. RNDr. Martin Branda, Ph.D.
• Class: M Mgr. FPM; M Mgr. FPM > Volitelné; M Mgr. PMSE; M Mgr. PMSE > Povinné
• Classification: Mathematics > Optimization
• Incompatibility : NMSA403
• Interchangeability : NMSA403
• Is incompatible with: NMSA403
• Is pre-requisite for: NMEK450
• Is interchangeable with: NMSA403

Annotation

English

Last update: 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).

Czech

Last update: 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).

Aim of the course

English

Last update: 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.

Czech

Last update: 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í.

Course completion requirements

English

Last update: 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

Czech

Last update: 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

Literature

Last update: 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.

Teaching methods

English

Last update: doc. Ing. Marek Omelka, Ph.D. (30.11.2020)

Lecture + exercises.

Czech

Last update: doc. Ing. Marek Omelka, Ph.D. (30.11.2020)

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

Requirements to the exam

English

Last update: doc. RNDr. Martin Branda, Ph.D. (02.10.2022)

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

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 exercises class credit is necessary to sign up for the exam.

Conditions for receiving of a credit from exercises 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 exercises class cannot be repeated.

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

Alternative requirements to exam in crisis situation

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

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

• Written part will be organized as a written test either in a full-time form or in a distance online form.

• Oral part will be organized either in a full-time form or in a distance online form.

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 specified by the course lecturer.

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

Alternative conditions for receiving of a credit from exercises class in crisis situation are:

• Handing in solved homework by the deadline.

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

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

Czech

Last update: doc. RNDr. Martin Branda, Ph.D. (02.10.2022)

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

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.

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

Alternativní požadavky ke zkoušce v krizové situaci jsou:

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

Zkouška má písemnou a ústní část.

• Písemná část bude formou písemného testu buď prezenčně nebo distančně online.

• Ústní část zkoušky bude buď prezenčně nebo distančně online.

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.

Při 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 určeném přednášejícím.

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

Alternativní 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é vypracování domácího úkolu na konci semestru (nutné získat alespoň 70% bodů).

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

Syllabus

English

Last update: 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.

Czech

Last update: 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.

Entry requirements

English

Last update: doc. RNDr. Petr Lachout, CSc. (05.12.2020)

Linear algebra, functional analysis.

Czech

Last update: doc. RNDr. Petr Lachout, CSc. (05.12.2020)

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