After following the course the student is able to:
- Explain how the Gauss algorithm provides a proof of main theorems in matrix theory.
- Describe how the Fourier-Motzkin algorithm leads to a constructive proof of the Farkas Lemma.
- Explain the basic idea behind strong duality of linear programs and the minmax theorem for matrix games.
- Describe and sketch the special properties of convex sets and convex functions.
- Describe the theoretical basis of different methods for solving smooth (unconstrained) minimization problems and explain the working of these algorithms.
- Apply the theoretical results to solve concrete (exercise) problems connected with the learned topics as well as to apply the proofs in a modified context.
Optimization problems appear in many real life situations. The course aims to provide an introduction into algorithmic principles and fundamental ideas of linear and nonlinear optimization. The course enables the student to follow more advanced courses in continuous and discrete optimization.|
The course starts with the topic of algorithmic methods for solving linear equations and linear inequalities. The Farkas lemma provides the basis for duality results in linear optimization. Strong duality of linear programs, sensitivity and matrix games are treated. We then study the properties of convex sets and convex functions. These properties play an important role in optimization and applied analysis. We deal with the theoretical results and algorithmic methods for nonlinear (unconstrained) programming. In particular we discuss descent methods, methods of conjugate directions, Newton methods and modern Quasi-Newton algorithms.