401-3901-00L Mathematical Optimization
Semester | Herbstsemester 2018 |
Dozierende | R. Weismantel |
Periodizität | jährlich wiederkehrende Veranstaltung |
Lehrsprache | Englisch |
Kurzbeschreibung | Mathematical treatment of diverse optimization techniques. |
Lernziel | Advanced optimization theory and algorithms. |
Inhalt | 1) 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. 2) Nonlinear optimization: Lagrange relaxation techniques, Newton method and gradient schemes for convex optimization. 3) Integer optimization: Ties between linear and integer optimization, total unimodularity, complexity theory, cutting plane theory. 4) Combinatorial optimization: Network flow problems, structural results and algorithms for matroids, matchings, and, more generally, independence systems. |
Literatur | 1) D. Bertsimas & R. Weismantel, "Optimization over Integers". Dynamic Ideas, 2005. 2) A. Schrijver, "Theory of Linear and Integer Programming". John Wiley, 1986. 3) D. Bertsimas & J.N. Tsitsiklis, "Introduction to Linear Optimization". Athena Scientific, 1997. 4) Y. Nesterov, "Introductory Lectures on Convex Optimization: a Basic Course". Kluwer Academic Publishers, 2003. 5) C.H. Papadimitriou, "Combinatorial Optimization". Prentice-Hall Inc., 1982. |
Voraussetzungen / Besonderes | Linear algebra. |