SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Fundamentals of Nonlinear Optimization - NOPT018
Title in English: Základy nelineární optimalizace
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. Mgr. Milan Hladík, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Optimalization
Annotation -
Last update: T_KAM (26.04.2017)
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.
Course completion requirements - Czech
Last update: 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.

Literature - Czech
Last update: 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.

Requirements to the exam - Czech
Last update: 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.

Syllabus -
Last update: T_KAM (26.04.2017)
  • 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.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html