Základy nelineární optimalizace - NOPT018

• Anglický název: Fundamentals of Nonlinear Optimization
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní 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: nevyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://kam.mff.cuni.cz/~hladik/ZNO/
• Garant: prof. Mgr. Milan Hladík, Ph.D.; prof. RNDr. Martin Loebl, CSc.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Optimalizace
• Je neslučitelnost pro: NOPX018
• Je prerekvizitou pro: NOPT020
• Je záměnnost pro: NOPX018

Anotace

čeština

Poslední úprava: T_KAM (26.04.2017)

Základní kurz nelineární optimalizace, věnovaný teoretickým poznatkům a možnostem použití. Předpokládají se znalosti lineárního programování a hodí se i znalosti předmětu Diskrétní a spojitá optimalizace (NOPT046). Předmět se obvykle koná jednou za dva roky.

angličtina

Poslední úprava: T_KAM (26.04.2017)

Basic course of nonlinear optimization devoted to theoretical fundamentals as well as applications. We assume knowledge of linear programming and recommend completion of the course Discrete and continuous optimization (NOPT046) before. The course is usually held once every two years.

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

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

K získání zápočtu je potřeba alespoň 30% bodový zisk z každé vypsané série domácích úkolů. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů. Zápočet není podmínkou pro konání zkoušky.

Literatura

čeština

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

Doprovodný text k části přednášky:

https://kam.mff.cuni.cz/~hladik/ZNO/text_zno.pdf

Další literatura:

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

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

[3] B. Gärtner, J. Matoušek: Approximation Algorithms and Semidefinite Programming, Springer, Heidelberg, 2012.

angličtina

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

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

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

[3] B. Gärtner, J. Matoušek: Approximation Algorithms and Semidefinite Programming, Springer, Heidelberg, 2012.

Požadavky ke zkoušce

čeština

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

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. Zápočet není podmínkou pro konání zkoušky.

angličtina

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

The exam is oral and consists of questions on subjects covered by the lectures. The exam can have the present or the distant form.

Sylabus

čeština

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

• Zobecněné konvexní funkce (kvazikonvexní a pseudokonvexní) a jejich význam v optimalizaci

• Podmínky optimality: Karush-Kuhn-Tuckerovy podmínky, podmínky Fritze Johna. Kvalifikace omezení (Slaterova podmínka) a speciální případy podmínek optimality.

• Lagrangeova duální úloha - slabá a silná dualita, geometrická interpretace, použití pro aproximaci. Sedlové body Lagrangeovy funkce a různé interpretace.

• Speciální úlohy konvexního programování: kvadratické, semidefinitní aj.

• Semidefinitní programování a aproximace těžkých problémů. Goemansův-Williamsonův algoritmus pro MAX-CUT. Lovászova theta-funkce.

angličtina

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

• Generalized convex functions (quasi-convex and pseudo-convex) and their importance in optimization

• Optimality conditions:: Karush-Kuhn-Tucker conditions and Fritz John conditions. Constraint qualification (Slater condition) and special cases of optimality conditions.

• Lagrange dual problem - weak and strong duality, geometric interpretation, application in approximation. Saddle points of the Lagrange function and various interpretations.

• Special problems of convex optimization, including quadratic and semidefinite programming.

• Semidefinite programming in detail. Approximation of hard problems. Goemans-Williamson MAX-CUT algorithm. Lovász theta-function.