Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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 2024
Semester:	winter
E-Credits:	5
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, 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.
Teacher(s):	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

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)