|
|
|
|
I teach the lecture jointly with Martin Loebl. I have the continuous part, whereas Martin Loebl the discrete part.
Schedule of lectures:
| 19.2. |
Unconstrained optimization: optimality criteria of the first and second order, illustration on the least square problem. Convex sets.
[chapter 2, sections 3.1-3.2] |
| 26.2. |
Convex functions: first and second order characterization, chain rules.
Convex optimization: basic properties of the optimal solutions, characterization of optimality. [sections 3.3-3.4, 4.1] |
| 5.3. |
Quadratic optimization: formulation, complexity, the convex case, two examples.
Convex optimization and complexity: the idea of the ellipsoid method for polynomial-time problems and an example of copositive optimization as a hard problem. [sections 4.2, 4.5] |
| 12.3. |
Convex cone programming: formulation, convex cones, dual cones, the dual problem, weak and strong duality (no proof for the strong duality).
Special cases: Cone quadratic programming and semidefinite programming. [section 4.4] |
| 19.3. |
KKT (Karush–Kuhn–Tucker) optimality conditions for the equality-constrained problem and for the general case. Types of conditions assuming linear independence and those based on Slater’s condition for a convex problem. A sufficient KKT condition.
[chapter 5] |
| 26.3. |
Algorithms. Line search: Armijo rule, Newton's method. Unconstrained optimization: gradient methods and Newton's method. Constrained optimization: feasible direction methods (Frank–Wolfe), penalty and barrier methods.
[sections 6.1-6.3] |
| (plan) 2.4. |
Concave programming. Robust optimization with interval and ellipsoidal uncertainty. An application: robust PCA.
[chapter 7, section 4.6.1] |
Literature:
