Discrete and Continuous Optimization (NOPT046), summer semester 2019/2020 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]

### Tutorial

To obtain credits for the tutorial, it is needed to obtain at least 50% of the points of each series of homeworks.

Homeworks: PDF

### Literature

Textbook: (in Czech; the version in English is continuously updated)