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

1. Introduction

2. Shortest paths and minimum spanning trees

3. Maximum flows and minimum cuts

4. Maximum matchings (unweighted and weighted)

5. Chinese postman problem

6. T-joins

7. TSP variants: subset TSP, path TSP

Continuous Optimization

1. Introduction to mathematical optimization

2. Unconstrained optimization

   • First and second order optimality conditions

   • Least square method

3. Convexity

   • Convex sets

   • Convex Functions

   • First and second order characterizations

4. 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

5. Karush-Kuhn-Tucker optimality conditions

   • Equation case

   • General case

6. 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)

1. totally unimodular matrices and integer polytopes

2. shortest paths and minimum spanning trees

3. max flows

4. minimum weight matchings and primal-dual algorithm for spanning trees

5. convex sets and functions

6. convex programming

7. cones and their duals

8. ellipsoid method, SDPs and strong duality

Literature

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

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

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

4. 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]