ETH Mathematical Optmization Summary

Here you can find the explanations and definitions to summarize the content of the lecture about Mathematical Optimization - Prof. Dr. Robert Weismantel.

This course covers:

• Linear optimization: The geometry of linear programming, the simplex method for solving linear programming problems, Farkas' Lemma and infeasibility certificates, duality theory of linear programming.
• Nonlinear optimization: Lagrange relaxation techniques, Newton method and gradient schemes for convex optimization.
• Integer optimization: Ties between linear and integer optimization, total unimodularity, complexity theory, cutting plane theory.
• Combinatorial optimization: Network flow problems, structural results and algorithms for matroids, matchings and more generally, independence systems.

In this course, the lectures are only at the blackboard and concepts of linear algebra and analysis are prerequisites. Course webpage: https://www.math.ethz.ch/ifor/education/courses/fall-2017/mathematical-optimization.html Some notes/exercises can be found at the moodle website: https://moodle-app2.let.ethz.ch/auth/shibboleth/login.php Course assistants: Christoph Glanzer ([email protected])

Disclaimer

Please note that nothing found here is guaranteed to be complete and/or correct. Feel free to report mistakes and to do pull requests.

References

• Graph Theory: The course requires basic knowledge in graph theory. This is, for example, covered in Diestel's book (Chapters 1.1 to 1.7).

• Linear and Mixed Integer Linear Optimization -- Introduction to Linear Optimization. Bertsimas, Tsitsiklis. Athena Scientific, 1997. (Covers some material in the first half of the course) -- Optimization over Integers. D. Bertsimas, R. Weismantel. Dynamic Ideas, 2005. (Chapters 1-3 are relevant to the integer programming part of the course) -- Theory of Linear and Integer Programming. A. Schrijver. John Wiley, 1986. (Nearly whole book relevant to course - covers first half of course and also integer programming topics and complexity theory)

• Nonlinear Optimization -- Introductory Lectures on Convex Optimization: a Basic Course. Y. Nesterov. Kluwer Academic Publishers, 2003. (This entire book is relevant to four lectures on convex optimization, but we will may not explicitly cover this material in this course)

• Combinatorial Optimization -- Combinatorial Optimization. C.H. Papadimitriou. Prentice-Hall Inc., 1982. (Covers some of the combinatorial topics of the course)