Course Introduction
《Linear Programming》 

This course introduces a unified view that treats the simplex, ellipsoid, and interior point methods in an integrated manner. To expose graduate students interested in learning stateoftheart techniques in the areas of linear programming and its natural extension. We will organize this course into ten subjects. We first introduce the linear programming problems with modeling examples and provide a short review of the history of linear programming. The basic terminologies are defined to build the fundamental theory of linear programming and tor form a geometric interpretation of the underlying optimization process. The next topic will cover the classical simplex methods and corresponding theories including the revised simplex, duality theorem, dual simplex method, the primaldual method. After discussing the sensitivity analysis, we will look into the concept of computational complexity and show that the simplex method, in the worstcase analysis, exhibits exponential complexity. Hence, the ellipsoid method is introduced as the first polynomialtime algorithm for linear programming. From this point onward, we focus on the nonsimplex approaches. The next subject is centered around the recent advances of Karmarkar’s algorithm and its polynomialtime solvability. We then study the affine scaling variants, containing the primal, dual, primaldual algorithms, of Karmarkar’s methods. The concepts of central trajectory and pathfollowing are also included. The eight topic reveals the insights of interiorpoint methods from both the algebraic and geometric viewpoints. It provides a platform for the comparison of different interiorpoint algorithms and the creation of new algorithms. We extend the results of interiorpointbased linear programming techniques to quadratic and convex optimization problems with linear constrain. The important implementation issues for computer programming are addressed in the last subject.
