Subjects

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

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 -

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: 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.