Discrete and Continuous Optimization (summer 2019)

Time and Place

  • Lecture: Mondays 10:40 to 12:10 in S9

  • Tutorial: Mondays 16:30 to 18:00 in S1

Office hours:

By email appointment.

Topics

Discrete Optimization

  1. Introduction

  2. Shortest paths

  3. Minimum spanning trees

  4. Maximum flows

  5. Minimum cuts

  6. Matchings

  7. T-joins

  8. Travelling Salesman problem

Continuous Optimization

  1. Introduction to mathematical optimization

  2. Unconstrained optimization

  3. Convexity of sets and functions

  4. Convex Optimization: quadratic programming, cone programming, semidefinite programming

  5. Ellipsoid method

  6. Karush-Kuhn-Tucker optimality conditions

Lectures

18.2.2019: basic graph theory, random access machines, polynomial-time solvability, NP-hardness, integer linear programs and their relaxations

25.2.2019: shortest paths: Dijkstra vs Bellman-Ford, spanning trees: Kruskal and the partitioning LP

4.3.2019: primal-dual algorithm for MST, total unimodularity and max flows, path decomposition of flows and the dual of the flow LP

11.3.2019: min st-cuts from dual of flow LP, global min cuts via Karger's algorithm, bipartite matchings via the rank lemma and iterative rounding

18.3.2019: integrality of the perfect matching polytope, the Chinese Postman problem, T-joins

25.3.2019: computing T-joins, applications of T-joins, the T-join polyhedron, Subset Path TSP, parameterized algorithms

1.4.2019: Christofides' algorithm for TSP, Hoogeveen's algorithm for Path TSP, basic notions of continuous optimization

8.4.2019: unconstrained optimization: 1st and 2nd order optimality conditions, application: least square method, convex sets: characterizations and separability

15.4.2019: convex functions, first and second order characterizations

29.4.2019: convex optimization, quadratic programs, cone programs, weak duality of cone programs

6.5.2019: strong duality of cone programs, semidefinite programming, ellipsoid method, copositive programming

20.5.2019: KKT conditions for equality constraints, general constraints, and convex optimization using Slater's condition

Literature

  1. B. Korte and J. Vygen. Combinatorial Optimization. Springer, 4th edition, 2008.

  2. B. Guenin, J. Könemann, and L. Tunçel. A Gentle Introduction to Optimization. Cambridge University Press, 2014.

  3. L. C. Lau, R. Ravi, and M. Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, 2011.

  4. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

  5. D. Luenberger and Ye. Linear and Nonlinear Programming. Springer, 3rd edition, 2008.

  6. M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming. Theory and Algorithms. 3rd ed. John Wiley & Sons., 2006.

Other links

Exercise sheets