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.
Last update: 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.
Course completion requirements - Czech
Last update: 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.
Literature -
Last update: 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.
Last update: 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.
Requirements to the exam -
Last update: 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.
Last update: 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.
Syllabus -
Last update: 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.
Last update: 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.