Discrete and Continuous Optimization (summer 2021)

Time and Place

• Lecture: Wednesdays 9:00 to 10:30 (in S4)

• Tutorial: Wednesdays 10:40 to 12:10 (in S10)

Zoom registration (Note: you only need to register once. You can then reuse the link you obtained in the confirmation email.)

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

Lecture videos and content

3.3.2021: video. Basic graph theory, random access machines, polynomial-time solvability, NP-hardness, integer linear programs and their relaxations

10.3.2021: video. Polyhedra, Dijkstra's algorithm, Bellman-Ford algorithm, Kruskal's algorithm

17.3.2021: video 1, video 2. Complementary slackness, primal-dual algorithm for MST partition LP, flow LP, total unimodularity

24.3.2021: video. Path flow LP, min st-cuts, min-cut max-flow theorem, global min cuts, Karger's algorithm

31.3.2021: video. Analysis of Karger's algorithm, the perfect matching polytope, proof of its integrality

7.4.2021: video. Integrality of matching polytope, Chinese Postman problem, T-joins

14.4.2021: video. Computing T-joins, FPT algorithm for Subset Path TSP, Christofides' approximation for TSP

21.4.2021: video. Hoogeveen's approximation for path TSP, basic definitions of continuous optimization, first-order necessary condition, second-order sufficient and necessary conditions

28.4.2021: video. Least square method, convex sets and functions

5.5.2021: video. First- and second-order characterizations, optimality of convex programs, NP-hardness of quadratic programs, portfolio design using convex quadratic programs

12.5.2021: no lecture

19.5.2021: video. Cone programming, weak and strong duality of cone programs, semidefinite programming

26.5.2021: video. Ellipsoid method, copositive programming, KKT conditions

2.6.2021: video. proof of KKT conditions, KKT conditions for convex programming

Lecture notes

Available via this link using the provided credentials. Lecture #5 (31.3.2021) can be found in a separate file. The two slides of the tutorial on 26.5.2021 (with a sketch of the solutions for exercise 11.1) are available here and here.

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.

Exercise sheets