På svenska Print Search Contact

Optimization and Systems Theory
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 active-set 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, predictor-corrector.

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

Lecture 10, November 21. Feasible path-following methods. Identification of exact solution. Identification of basic feasible solution and basis.

Lecture 11, November 28. Infeasible interior methods.

Lecture 12, December 5. Higher-order interior methods. Summary.

Published by: Optimization and Systems Theory, KTH
Anders Forsgren, andersf@kth.se

Last updated: 2016-09-27