Numerical linear programming
This graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.
Time: Tue 2010-01-19 10.15 - 12.00
Location: Room 3721, department of mathematics, KTH, Lindstedtsvägen 25, 7th floor
Contact:
Subject area: Optimization and Systems Theory
Schedule
Lectures will be given in the spring of 2010 (tentatively twelve). First meeting Tuesday January 19, 2010, 10.15-12.00, in Room 3721, Lindstedtsvägen 25.
Summary of contents
The course deals with theory and algorithms for linear programming problems (LP problems).
From the 1940s untils about twentyfive years ago the simplex method, developed by Dantzig, was the only practically used method for solving LP problems. Khachian had in the late 1970s presented the polynomial ellipsoid method, but it had not been successful in practice.
When Karmarkar presented his interior method in 1984, all this changed. This method was polynomial and also claimed to be superior to the simplex method in practice.
Karmarkar's method lead to an "explosion" within the area of linear programming. Gill et. al. soon showed that Karmarkar's method was equivalent to a logarithmic barrier method, and the development of new interior methods was rapid.
This "competition" between the simplex method and interior methods has lead to significant improvement in both types of method over the last decade. The purpose of this course is to reflect this development. Some more advanced aspects of the simplex method are included, e.g., steepest edge, partial pricing, and of the interior-point methods e.g., primal-dual methods, affine-scaling methods, predictor-corrector methods. In particular, we try to understand how the different methods work.
Prerequisites
Suitable prerequisites are the courses SF2812 Applied linear optimization and DN2251 Applied numerical methods III, or similar knowledge.
Examination
The examination is by five sets of homework assignments and an oral final exam.