Základy spojité optimalizace - NMMB438

• Anglický název: Fundamentals of Continuous Optimization
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: letní
• E-Kredity: 6
• 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: čeština, angličtina
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NOPT046
• Garant: prof. Mgr. Milan Hladík, Ph.D.; prof. RNDr. Martin Loebl, CSc.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinně volitelné
• Kategorizace předmětu: Matematika > Optimalizace
• Neslučitelnost : NOPT046
• Záměnnost : NOPT046

Anotace

čeština

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. Pro absolvování předmětu jsou vhodné (nikoli však nutné) předběžné znalosti lineárního programování, např. z přednášky NOPT048 Lineární programování a kombinatorická optimalizace (dříve Opt. Metody).

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (25.01.2018)

angličtina

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. Previous knowledge of linear programming, e.g. from NOPT048 Linear Programming and Combinatorial Optimization (formerly Optimization Methods) is advisable (but not required).

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (25.01.2018)

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

čeština

Pro zápočet je potřeba získat dostatečný počet bodů na zápočtové písemce, která je součástí závěrečné zkoušky. Body lze získat i za aktivitu na cvičení. Účast na cvičení není povinná.

Bližší informace k zápočtům jsou k dispozici na stránce:

https://kam.mff.cuni.cz/~hladik/DSO

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (19.02.2026)

angličtina

To receive course credit, it is necessary to obtain a sufficient number of points on the credit test, which is part of the final exam. Points can also be earned for active participation in the exercise sessions. Attendance at the exercise sessions is not mandatory.

More detailed information about course credit requirements is available on the website:

https://kam.mff.cuni.cz/~hladik/DSO

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (19.02.2026)

Literatura

čeština

Doprovodný text (pro část spojité optimalizace):

https://kam.mff.cuni.cz/~hladik/DSO/text_dso.pdf

Další literatura:

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (30.09.2021)

angličtina

Electronic textbook (for the continuous part):

https://kam.mff.cuni.cz/~hladik/DSO/text_dso_en.pdf

Further references:

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.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (30.09.2021)

Požadavky ke zkoušce

čeština

Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních. Zkouška má písemnou a ústní část. Zkouška může mít kontaktní nebo distanční formu.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (19.02.2026)

angličtina

The exam requirements correspond to the course syllabus in the scope covered during lectures and exercise sessions. The exam consists of a written and an oral part. The exam may take place either in person or in a remote format.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (19.02.2026)

Sylabus

čeština

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (07.04.2016)

angličtina

Fundamentals of discrete optimization:

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

• Shortest paths and minimum spanning trees and relations.

• Maximum matching and applications, relation to flows in networks. Algorithms for matchings. Postman problem.

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

• Comparisons of hard and polynomial problems.

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

Poslední úprava: Feldmann Andreas Emil, doc., Dr. (14.02.2018)