Mathematical treatment of diverse optimization techniques.
Objective
Advanced optimization theory and algorithms.
Content
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.
Literature
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.