KTH /
Engineering Science
/
Mathematics
/
Optimization and Systems Theory
SF3850 Numerical linear programming, 7.5 cr
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 information
page for relevant literature.
Brief summary of planned contents of lectures
Lecture 1, September 20.
Introduction. Geometry. Extreme points and basic feasible solutions.
Lecture 2, September 26.
An elementary proof of strong duality.
Lecture 3, October 3.
The simplex method. Primal simplex and dual simplex. The simplex
method viewed as an activeset method. Anticycling via Bland's rule. Homework
assignment 1 will be made available.
Lecture 4, October 10.
The simplex method. Updating the LU factors of the basis matrix. Generalized upper bounding techniques.
Steepest edge, primal steepest edge as well as
dual steepest edge. Homweork 2 will be 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.
Lecture 7, October 31.
Why is simplex not polynomial? Basics of complexity of interior method.
Lecture 8, November 7.
Interior methods, different types. Short step, long step, predictorcorrector.
Lecture 9, November 14.
Interior methods, different types, continued. Short step, long step,
predictorcorrector.
Lecture 10, November 21.
Feasible pathfollowing methods. Identification of exact
solution. Identification of basic feasible solution and
basis.
Lecture 11, November 28.
Infeasible interior methods.
Lecture 12, December 5.
Higherorder interior methods. Summary.
