Základy nelineární optimalizace

Sylabus

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

Anotace

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.