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
Introduction
Shortest paths
Minimum spanning trees
Maximum flows
Minimum cuts
Matchings
T-joins
Travelling Salesman problem
Continuous Optimization
Introduction to mathematical optimization
Unconstrained optimization
Convexity of sets and functions
Convex Optimization: quadratic programming, cone programming, semidefinite programming
Ellipsoid method
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
B. Korte and J. Vygen. Combinatorial Optimization. Springer, 4th edition, 2008.
B. Guenin, J. Könemann, and L. Tunçel. A Gentle Introduction to Optimization. Cambridge University Press, 2014.
L. C. Lau, R. Ravi, and M. Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, 2011.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
D. Luenberger and Ye. Linear and Nonlinear Programming. Springer, 3rd edition, 2008.
M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming. Theory and Algorithms. 3rd ed. John Wiley & Sons., 2006.