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