I teach the continuous part, whereas the discrete part is lead by Martin Loebl.
Schedule of lectures:
|(plan) 25.3.||Introduction: Discrete and continuous optimization, their relation, examples (flows in networks). Illustration on linear regression models: different norms, cardinality, signal reconstruction. [chapter 1]|
|(plan) 1.4.||Unconstrained optimization: optimality criteria of the first and second order, illustration on the least square problem. Convex sets. [chapter 2, section 3.1]|
|(plan) 8.4.||Convex functions, first and second order characterization, chain rules. [sections 3.2-4]|
|(plan) 15.4.||Convex optimization: basic properties of the optimal solutions, characterization of optimality, idea of the ellipsoid method for polynomial problems, [sections 4.1, 4.4.1]|
|(plan) 22.4.||An example of copositive programming as a hard subclass. Convex quadratic programming: formulation, complexity, examples. [sections 4.2, 4.4.2, 4.5.2]|
|(plan) 29.4.||Convex cone programming: formulation, convex cones, dual cones, the dual problem, weak and strong duality. Cone quadratic programming and semidefinite programming as examples. [section 4.3]|
|(plan) 6.5.||Karush-Kuhn-Tucker optimality conditions for the equation case, for the general case (with linear independence constraint qualification), and for convex problems (with the Slater condition). [chapter 5]|
|(plan) 13.5.||Algorithms. Line search: Armijo rule, Newton method. Unconstraint problems: gradient methods and Newton method. Constraint problems: methods of feasible directions (Frank-Wolfe, Zoutendijk), penalty and barrier methods. [sections 6.1-3]|
|(plan) 20.5.||Concave programming. Robust optimization with interval and ellipsoidal uncertainty. An application: robust PCA. [chapter 7, section 4.5.1]|
To obtain credits for the tutorial, it is needed to obtain at least 50% of the points of each series of homeworks.