SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
Fundamentals of Nonlinear Optimization - NOPT018
Title: Základy nelineární optimalizace
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: https://kam.mff.cuni.cz/~hladik/ZNO/
Guarantor: prof. Mgr. Milan Hladík, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Optimalization
Is incompatible with: NOPX018
Is pre-requisite for: NOPT020
Is interchangeable with: NOPX018
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: 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.

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.

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