Fundamentals of Continuous Optimization - NMMB438

• Title: Základy spojité optimalizace
• Guaranteed by: Department of Algebra (32-KA)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2016 to 2016
• Semester: summer
• E-Credits: 6
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Is provided by: NOPT046
• Guarantor: doc. Hans Raj Tiwary, M.Sc., Ph.D.
• Class: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Classification: Mathematics > Optimization
• Incompatibility : NOPT046
• Interchangeability : NOPT046

Annotation

English

Last update: doc. Mgr. Jan Kynčl, Ph.D. (25.01.2018)

Review course covering fundamental fields of optimization, incl. computational methods. There are countless examples from almost all branches of human doing leading to problems coming under this discipline. Introduction to several other courses specialized in the solution of particular classes of optimization problems.

Czech

Last update: doc. Mgr. Jan Kynčl, Ph.D. (25.01.2018)

Přehledová přednáška pokrývající základní oblasti optimalizace, včetně výpočetních metod. Na úlohy spadající pod tuto problematiku vede nesčetné množství problémů z téměř všech oborů lidské činnosti. Má velmi široké možnosti použití. Úvod k dalším přednáškám specializovaným na řešení jednotlivých tříd optimalizačních úloh.

Literature

English

Last update: prof. Mgr. Milan Hladík, Ph.D. (30.09.2021)

M.S. Bazaraa, H.D. Sherali, C.M. Shetty: Nonlinear Programming, Wiley, New Jersey, 2006.

S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, 2009.

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinatorial Optimization. Wiley, New York, 1998.

Syllabus

English

Last update: doc. Andreas Emil Feldmann, Dr. (14.02.2018)

Fundamentals of discrete optimization:

• Introduction, examples of optimization examples and techniques. Analysis of algorithms, implementation and complexity.

• Euler walk, greedy algorithms, shortest path and relations.

• Maximum matching and applications, relation to flows in networks. Heuristics and algorithms for matchings (incl. probabilistic). Postman problem.

• Traveling salesman problem (TSP): heuristics, applications and relations.

• Comparisons of hard and polynomial algorithms: TSP, postman problem, Euler tours, minimal spanning tree, minimal Steiner tree.

Fundamentals of continuous optimization:

• Convex functions and sets

• Convex optimization

• Quadratic programming

• Cone programming and duality

• Karush-Kuhn-Tucker optimality conditions

• Basic methods

• Programming with uncertain data, robust optimization

Czech

Last update: prof. Mgr. Milan Hladík, Ph.D. (07.04.2016)

Základy diskrétní optimalizace:

• Úvod, příklady optimalizačních problémů a optimalizačních technik. Analýza algoritmů, implementace, složitost.

• Eulerovská procházka, hladový algoritmus, nejkratsi cesta a jejich souvislosti.

• Párování a aplikace, souvislost s toky v sítích. Heuristiky a algoritmy, i pravděpodobnostní, na párování. Problém pošťáka.

• Problém obchodního cestujícího (TSP): heuristiky, aplikace a souvislosti

• Porovnání těžkých a polynomiálních problémů: TSP, problém pošťáka, Euler tours, minimální kostra, minimální Steiner tree.

Základy spojité optimalizace:

• Konvexní funkce a množiny

• Konvexní optimalizace

• Kvadratické programování

• Kuželové programování a dualita

• Karush-Kuhn-Tuckerovy podmí­nky optimality

• Základní metody

• Programování s nepřesnými daty, robustní optimalizace