Course Introduction

• Prerequisite：Calculus and Linear Algebra
• Recommended for： graduate students
• Introduction：

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 state-of-the-art 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 primal-dual method. After discussing the sensitivity analysis, we will look into the concept of computational complexity and show that the simplex method, in the worst-case analysis, exhibits exponential complexity. Hence, the ellipsoid method is introduced as the first polynomial-time 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 polynomial-time solvability. We then study the affine scaling variants, containing the primal, dual, primal-dual algorithms, of Karmarkar’s methods. The concepts of central trajectory and path-following are also included. The eight topic reveals the insights of interior-point methods from both the algebraic and geometric viewpoints. It provides a platform for the comparison of different interior-point algorithms and the creation of new algorithms. We extend the results of interior-point-based 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.

• Syllabus：

1. Introduction
2. Geometry of Linear Programming
3. The Revised Simplex Method
4. Duality Theory and Sensitivity Analysis
5. Complexity Analysis and the Ellipsoid Method
6. Karmarkar's Projective Scaling Algorithm
7. Affine Scaling Algorithms
8. Insights into the Interior-Point Methods
9. Affine Scaling for Convex Quadratic Programming
10. Implementation of Interior-Point Algorithms

• Reference：

1. S.-C. Fang and S. Puthenpura, Linear Optimization and Extensions: Theory and Algorithms, AT&T - Prentice-Hall, Englewood Cliffs, NJ, 1993.
2. M.S. Bazaraa, H.D. Sherali, and C.M. Shetty, Nonlinear programming: theory and algorithms (3rd ed.), Wiley, New York, 2006.