PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
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 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
Virtuální mobilita / počet míst: 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
Výsledky anket   Termíny zkoušek   Rozvrh ZS   Nástěnka   
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: 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 -
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.

Požadavky ke zkoušce -
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.

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