Základy nelineární optimalizace - NOPX018

• Anglický název: Fundamentals of Nonlinear Optimization
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022 do 2024
• Semestr: zimní
• E-Kredity: 6
• 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: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NOPT018
• 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
• Prerekvizity : {NXXX007, NXXX008, NXXX009}
• Neslučitelnost : NOPT018
• Záměnnost : NOPT018

Anotace

čeština

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.

Poslední úprava: T_KAM (26.04.2017)

angličtina

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.

Poslední úprava: T_KAM (26.04.2017)

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

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.

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

Literatura

čeština

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.

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

angličtina

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

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

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

angličtina

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

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

Sylabus

čeština

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

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

angličtina

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

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