Discrete and Continuous Optimization (summer 2018)
Time and Place
Lecture: Mondays 14:00 to 15:30 in S9
Tutorial: Mondays 15:40 to 17:10 in S9
Office hours:
By email appointment.
Topics
Discrete Optimization
Introduction
Shortest paths and minimum spanning trees
Maximum flows and minimum cuts
Maximum matchings (unweighted and weighted)
Chinese postman problem
T-joins
TSP variants: subset TSP, path TSP
Continuous Optimization
Introduction to mathematical optimization
Unconstrained optimization
First and second order optimality conditions
Least square method
Convexity
Convex sets
Convex Functions
First and second order characterizations
Convex Optimization
Basic properties
Quadratic programming
Cone programming
Duality
Cone quadratic programming
Semidefinite programming
Computational complexity
The good case: ellipsoid method
The bad case: copositive programming
Karush-Kuhn-Tucker optimality conditions
Equation case
General case
Algorithms
Line search: Armijo rule
Unconstrained problems: Gradient method
Constrained problems
Methods of feasible directions
Penalty and barrier methods
Lectures
19.2: definitions of graphs, polynomial time algorithms, the classes P and NP, NP-hardness, ILPs, LPs, polytopes
26.2: Dijkstra's algorithm, Bellman-Ford algorithm, Prim's algorithm, the spanning tree polytope
5.3: residual graphs and augmenting paths, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, flow LP
12.3: Edmonds blossom algorithm, perfect matching LP, minimum weight perfect matchings
19.3: T-joins and their applications
26.3: subset path TSP: parameterized algorithm, path TSP: approximation algorithm, the T-join polytope
9.4: basic terminology (constraint functions, local/global (strict) minima), 1st and 2nd order optimality conditions for unconstrained optimization, application: least square method, characterizations and properties of convex sets and convex functions
16.4: 1st & 2nd order characterizations, multiplying and composing convex functions, optima of convex programs on open and closed domains, hardness of quadratic programming
23.4: applications of quadratic programming, cone programming: different kinds of cones, weak and strong duality
30.4: cone quadratic programming, semidefinite programming, ellipsoid method
7.5: copositive programming, KKT conditions, line search (Newton method, Armijo's rule)
14.5: algorithms for unconstrained optimization (gradient method, Newton method) and constrained optimization (method of feasible direction, penalty method, barrier method), robust optimization with interval uncertainty, robust PCA
Exercise sheets
(see file list below)
totally unimodular matrices and integer polytopes
shortest paths and minimum spanning trees
max flows
minimum weight matchings and primal-dual algorithm for spanning trees
convex sets and functions
convex programming
cones and their duals
ellipsoid method, SDPs and strong duality
Literature
B. Korte and J. Vygen. Combinatorial Optimization. Springer, 4th edition, 2008.
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.
Other links
F. Augugliaro, A.P. Schoellig, and R. D’Andrea, Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach, EEE/RSJ International Conference on Intelligent Robots and Systems, 2012: pp. 1917–1922. [Youtube video]