General information

This graduate course is primarily intended for graduate students in optimization and systems theory, or other graduate students with a good background in optimization.
Schedule
Lectures will be given in the autumn of 2025 (tentatively twelve). First meeting Friday September 12, 2025, 8.15-10.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 thirty 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 decades. 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 SF2520 Applied Numerical Methods, or similar knowledge.
Examination
The examination is by five sets of homework assignments and an oral final exam.
Examiner
Anders Forsgren, room 3652, Lindstedtsvägen 25, tel. 08-790 71 27. E-mail: andersf@kth.se.
Information
For more information, see course memo.

Below is given a brief summary of planned contents of lectures in the course. It is not intended to be complete, but rather to assist students. Please check the course memo for relevant literature.

Brief summary of past lectures

Lecture 1, September 12. Introduction. Geometry. Extreme points and basic feasible solutions.

Lecture 2, September 19. An elementary proof of optimality conditions for linear programming. Homework assignment 1 was made available.

Lecture 3, October 3. Lagrangian relaxation. Lagrangian duality. Strong duality for linear programming. The simplex method. Primal simplex and dual simplex. The simplex method viewed as an active-set method.

Lecture 4, October 10. The simplex method. Anticycling via Bland's rule. Primal steepest edge. Brief mentioning of updating LU-factors of a basis. Homework 2 was made available.

Lecture 5, October 17. Karmarkar's method and its equivalence to a barrier method for linear programming.

Lecture 6, October 24. Interior methods. Existence of barrier trajectory. Homework 3 was made available.

Brief summary of planned lectures

Lecture 7, October 30. Why is simplex not polynomial? Basics of complexity of interior method.

Lecture 8, November 6. Interior methods, different types. Short step, long step, predictor-corrector. Homework 4 will be made available.

Lecture 9, November 13. Interior methods, different types, continued. Short step, long step, predictor-corrector.

Lecture 10, November 21. Infeasible path-following methods. Identification of exact solution. Identification of basic feasible solution and basis. Homework 5 will be made available.

Lecture 11, November 27. Higher-order interior methods.

Lecture 12, December 5. Summary.