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
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,
Lecture 10, November 21.
Feasible path-following methods. Identification of exact
solution. Identification of basic feasible solution and
Lecture 11, November 28.
Infeasible interior methods.
Lecture 12, December 5.
Higher-order interior methods. Summary.