Fundamentals of Nonlinear Optimization - NOPX018
Title: Základy nelineární optimalizace
Guaranteed by: Student Affairs Department (32-STUD)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Is provided by: NOPT018
Guarantor: prof. Mgr. Milan Hladík, Ph.D.
prof. RNDr. Martin Loebl, CSc.
Class: Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Optimalization
Pre-requisite : {NXXX007, NXXX008, NXXX009}
Incompatibility : NOPT018
Interchangeability : NOPT018
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
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)
Course completion requirements - Czech

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.

Last update: Hladík Milan, prof. Mgr., Ph.D. (05.10.2018)
Literature -

[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: Hladík Milan, prof. Mgr., Ph.D. (30.09.2021)
Requirements to the exam -

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: Hladík Milan, prof. Mgr., Ph.D. (24.09.2020)
Syllabus -
  • 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: Hladík Milan, prof. Mgr., Ph.D. (14.02.2023)