PředmětyPředměty(verze: 849)
Předmět, akademický rok 2019/2020
   Přihlásit přes CAS
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 2019 do 2019
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. 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
Anotace -
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.
Podmínky zakončení předmětu
Poslední úprava: doc. 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
Poslední úprava: T_KAM (26.04.2017)

[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
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (05.10.2018)

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

Sylabus -
Poslední úprava: T_KAM (26.04.2017)
  • 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.

 
Univerzita Karlova | Informační systém UK