Teaching

Linear optimization deals with the optimization of linear functions over sets described by linear inequalities and is one of the oldest and most developed subfields of mathematical optimization. Many practical problems, for example in the planning of traffic or communication networks, production planning or commodity transport, can be formulated as so-called linear programs. Due to its long history, linear optimization has laid the foundation for various central concepts in mathematical optimization. These include duality theory and the importance of convexity.

The lecture Linear optimization thus offers a useful introduction to the field of mathematical optimization. Topics taught include:

• fundamentals of polyhedral theory (representations of polyhedra, Weyl's theorem, Minkowski's theorem, faces, characterizations of vertices, etc.),
• theoretical foundations of linear programming (standard forms of linear programs, existence of solutions, attainment of the solution in vertices of the feasible region, canonical forms, etc.),
• primal and dual simplex algorithm,
• duality (dual linear program, strong and weak duality theorem, Farkas lemma, complementary slackness theorem),
• use of optimization software,
• applications of linear programming.

This course is taught in German.

Recommended literature:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Dantzig, G. B., Thapa, M. N.: Linear Programming 1 - Introduction. Springer Series in Operations Research. Springer-Verlag, New York, 1997, pp. xxxviii+435.
• Dantzig, G. B., Thapa, M. N.: Linear Programming 2 - Theory and Extensions. Springer Series in Operations Research. Springer-Verlag, New York, 2003, pp. xxvi+448.
• Lauritzen, N.: Undergraduate Convexity - From Fourier and Motzkin to Kuhn and Tucker. World Scientific Publishing Co. Pte. Ltd, Hackensack, NJ, 2013, pp. xiv+283.
• Padberg, M.: Linear Optimization and Extensions. Second Edition. Vol. 12. Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999, pp. xxii+501.
• Luenberger, D. G., Ye, Y.: Linear and Nonlinear Programming. Fourth Edition. Vol. 228. International Series in Operations Research & Management Science. Springer, Cham, 2016, pp. xiv+546.

The lecture is a continuation of  Linear optimization. Linear optimization problems are generalised in the sense that the objective function and the constraints no longer have to be linear. However, the class of nonlinear optimization problems is far too large to be able to provide efficient solution methods. Therefore, additional requirements are imposed. The course deals with specially structured convex optimization problems that can be solved efficiently and are relevant for applications.

In the first part of the lecture, interior-point methods - i.e. solution methods from nonlinear optimization - are introduced for linear optimization problems. The second part deals with different classes of specially structured convex optimization problems and their relationship between each other. The third part deals with applications and modelling aspects. In the last part, global optimization - i.e. problems that can no longer be solved efficiently - is presented in outline.

This is an introductory course with the aim of gaining an overview of important topics and concepts of continuous optimization. The lecture Continuous optimization, which is offered in the following semester, can be taken as an in-depth course.

This course is taught in German.

Recommended literature:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Lauritzen, N.: Undergraduate Convexity - From Fourier and Motzkin to Kuhn and Tucker. World Scientific Publishing Co. Pte. Ltd, Hackensack, NJ, 2013, pp. xiv+283.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.
• Anjos, M. F., Lasserre J. B. (eds.): Handbook on semidefinite, conic and polynomial optimization. Vol. 166. International Series in Operations Research & Management Science. Springer, New York, 2012, pp. xii+960.

Optimization problems are often classified as either continuous or discrete. In continuous optimization, an objective function is optimized over a continuum. In this lecture, this set will be a convex or nonconvex subset of Rⁿ.
Optimality conditions, duality theory and numerical methods will be discussed for continuous optimization problems. In particular, generalized concepts of differentiability (subdifferentials) are discussed. Continuous optimization plays an important role in numerous applications in the natural and social sciences as well as in engineering and finance.

The lecture follows on from the Introduction to continuous optimization, but can also be heard without it with some additional effort. Linear optimization is recommended as a basis.

This course is taught in German.

Recommended literature:

• Rockafellar, R. T.: Convex Analysis. No. 28. Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1970, pp. xviii+451.
• Borwein, J. M., Lewis, A. S.: Convex analysis and nonlinear optimization - Theory and examples. Vol. 3. CMS Books in Mathematics. Springer-Verlag, New York, 2000, pp. x+273.

This course provides a foundational understanding of key concepts and algorithms in discrete optimization. The topics of teh course include fundamental problems such as:

• shortest path
• maximum flow
• minimum cost flow
• traveling salesman problem
• integer linear programming
• optimization on matroids and the greedy algorithm

There is a particular focus on modeling practical applications. 

Although not sequential, the course 'Algorithmics (Grundlagen der Algorithmik)' by Professor Komusiewicz is recommended as a further course in this topic.

This course is taught in German.

In the Bachelor's seminar optimization students learn to familiarise themselves independently with a defined topic in mathematical optimization, to prepare and to present it. It is therefore recommended that students have already completed at least one course mathematical optimization, e.g. Linear optimization, Introduction to continuous optimization, Introduction to discrete optimization or Practical mathematics and modelling: optimization. During the preparation for the presentation, there is the opportunity to attend individual consultations to clarify open questions and discuss progress. A written composition of your own presentation topic at the end of the semester offers the opportunity to practise writing scientific texts according to scientific standards. This makes the Bachelor's seminar optimization an ideal preparation for writing a bachelor's thesis.

This seminar is taught in German.

The lecture Practical optimization is an application-oriented supplement to initial prior knowledge in the field of mathematical optimization, which may have been acquired, for example, in one of the courses Linear optimization, Introduction to continuous optimization or Introduction to discrete optimization. Selected topics are prepared by the students and presented in class. In preparation for this, there are opportunities for regular individual consultations to answer questions and discuss progress. However, the focus is on the students' independent work. A written composition of their own presentation topic at the end of the semester offers the opportunity to practise writing scientific texts according to scientific standards (e.g. in preparation for writing a bachelor's thesis).

The presentation topics vary and include the modelling of application problems, the solving of specific optimization problems using software and the implementation of optimization algorithms.

This course is taught in German.

In the course Practical mathematics and modelling: optimization the basics of various areas of mathematical optimization are developed from a user's perspective. Many problems in logistics, production planning and financial mathematics can be formulated as specially structured linear or convex optimization problems. Students learn about the underlying optimization problems and their properties using various applications as examples. The content is not presented in a formal mathematical way, but the lecture aims to train students in the modelling of optimization problems and the application of optimization and to give them as broad an overview as possible of problem classes and methods. Against this background, the course is also suitable for students with no previous knowledge of mathematical optimization. Among other things, the following will be taught

• fundamentals of linear programming (standard forms of linear programs, modelling techniques, simplex algorithm, duality, etc.),
• fundamentals of general optimization problems (sufficient and necessary optimality conditions, KKT conditions, Lagrange duality, etc.),
• descent methods,
• classes of convex optimization problems.

This course is taught in German.

Recommended literature:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.
• Jungnickel, D.: Optimierungsmethoden - Eine Einführung. Third Edition. Springer-Lehrbuch. Springer Berlin, Heidelberg, 2015, pp. xvi+279.
• Papageorgiou, M., Leibold, M., Buss, M.: Optimierung - Statische, dynamische, stochastische Verfahren für die Anwendung. Fourth Edition. Springer Berlin, Heidelberg, 2015, pp. xix+538.

The course Mathematical models for optimization problems examines aspects of various areas of mathematical optimization from a user and application perspective and is also suitable for students without prior knowledge in the field of mathematical optimization. The focus of the lecture is on the modelling of application problems as optimization problems. In particular, the aim is to teach students the ability to recognise which type of optimization problem is involved in a specific application and which software is suitable for solving it. The contents of the course include

• fundamentals of linear programming (standard forms of linear programs, modelling techniques, duality, etc.),
• linear optimization in the field of graph theory (shortest paths, Ford's algorithm, feasible potentials, maximum flow problems, Ford and Fulkerson's algorithm, max-flow-min-cut duality, minimum cost flow problems, etc.),
• classes of convex optimization problems.

This course is taught in German.

Recommended literature:

• Vanderbei, R. J.: Linear Programming - foundations and extensions. Fourth Edition. Vol. 196. International Series in Operations Research & Management Science. Springer, New York, 2014, pp. xxii+414.
• Cook, W. J., Cunningham, W. H., Pulleyblanc, W. R., Schrijver, A.: Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc, New York, 1998, pp. x+355.
• Ahuja, R. K., Magnanti, T. L., Orlin, J. B.: Network flows - Theory, algorithms and applications. Prentice Hall, Inc, Englewood Cliffs, NJ, 1993, pp. xvi+846.
• Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, 2004, pp. xiv+716.

In the Master's seminar optimization students learn to independently study a current research topic in mathematical optimization, prepare it and present it in class. At the beginning of the semester they typically receive an article from a scientific journal, the content of which must be analysed. It is therefore recommended to have completed at least one advanced course in mathematical optimization, e.g. Vector optimization or Convex analysis and nonsmooth optimization. During the preparation for the presentation there is the opportunity to attend individual consultations to clarify open questions and discuss progress. A written composition of your own presentation topic at the end of the semester offers the opportunity to practise writing scientific texts according to scientific standards. This makes the Master's seminar optimization an ideal preparation for writing a master's thesis.

Convexity is a fundamental property in optimization. In convex optimization problems, local optimal solutions are also global, making these problems particularly significant. Moreover, many specific classes of convex optimization problems can be solved approximately in polynomial time.

This course offers a systematic exploration of convex sets and convex functions. We delve into convex optimization problems, with a special focus on developing an abstract duality theory. The course does not assume any form of differentiability; instead, we work with subgradients, which generalize the concept of derivatives.

Recommended literature:

• Bertsekas, D.: Convex Optimization Theory. Athena Scientific, 2009.
• Hiriart-Urruty, J.-B., & Lemaréchal, C.: Fundamentals of Convex Analysis. Springer-Verlag, 2001.
• Borwein, J. M.; Lewis, A. S.: Convex Analysis and Nonlinear Optimization. Springer-Verlag, 2006.
• Rockafellar, R. T.: Convex Analysis. Princeton University Press, 1970.

The course Semidefinite optimization and approximation of convex sets deals with the question of how the concept of convergence or the limit of a sequence of real numbers can be generalized to sequences of sets. For this purpose, sequences of closed convex sets are considered and two concepts of convergence are systematically studied. For the special case of bounded sequences, the Hausdorff distance, which also defines a metric on the space of nonempty compact subsets of Rⁿ, is suitable for capturing the convergence of sequences of sets. For sequences that are not necessarily bounded, the convergence with respect to the Hausdorff distance is generalized to the so-called Painlevé-Kuratowski convergence and connections between the two concepts are investigated. By identifying closed convex sets in Rⁿ with closed convex cones in Rⁿ⁺¹, the space of nonempty convex subsets of Rⁿ can even be equipped with a metric.

These notions of convergence are used to develop algorithms to approximate convex sets by polyhedra. These algorithms require the solution of special convex programs. In order to be able to solve them practically, the restriction to certain convex sets is necessary. So-called projected spectrahedra turn out to be suitable here. These are closely related to semidefinite optimization, which is why the basics and duality theory of these play another central role in the course.

It is recommended to have attended the course Convex analysis and nonsmooth optimization in advance in order to be familiar with important concepts of convex analysis. However, this is not a prerequisite. Contents of the course include:

• fundamentals of semidefinite programming (standard forms of semidefinite programs, weak and strong duality, applications),
• convergence concepts for sequences of closed convex sets (Hausdorff convergence, Painlevé-Kuratowski convergence, etc.),
• spectrahedra and projected spectrahedra (set calculus for projected spectrahedra, etc.),
• algorithms for the polyhedral approximation of projected spectrahedra.

Recommended literature:

• Rockafellar, R. T., Wets, R. J.-B.: Variational analysis. Vol. 317. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998, pp. xiv+733.
• Todd, M. J.: Semidefinite Optimization. Vol. 10. Acta Numerica. 2001, pp. 515-560.
• Rockafellar, R. T.: Convex Analysis. No. 28. Princeton Mathematical Series. Princeton University Press, Princeton, NJ, 1970, pp. xviii+451.
• Blekherman, G., Parrilo, P. A., Thomas, R. R. (eds.): Semidefinite optimization and convex algebraic geometry. Vol. 13. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2013, pp. xx+476.

Vector linear programming problems are linear programs with a vector-valued objective function. These problems arise in applications where multiple objective functions are to be optimized simultaneously. Such applications are particularly common in economics and engineering. There are also other applications that are less immediately obvious, such as in algorithmic geometry for calculating convex polyhedra, in multivariate statistics for computing quantiles, and in deriving certain inequalities in information theory. Topics covered in the lecture include:

• Problem formulation and solution concepts
• Applications
• Duality
• Solution methods

The lecture addresses current research questions. Knowledge of Linear Programming is recommended as a prerequisite.

Recommended literature:

• Ehrgott, M. (2005). Multicriteria Optimization. Springer.
• Luc, D. T. (2016). Multiobjective Linear Programming. Springer.
• Löhne, A. (2011). Vector Optimization with Infimum and Supremum. Springer.
• Recent papers on the topic

Set optimization extends vector optimization by incorporating a set-valued objective function. Specifically, polyhedral convex set optimization extends vector linear programming. Set optimization is a relatively new field, and this course addresses recent developments in this area.

This course builds upon the concepts introduced in the course Vector Linear Programming therefore, it is recommended to take that course first. Topics covered include:

• Problem setting and solution concepts
• Applications
• Solution methods

Recommended literature:

• Recent papers on the topic