Operations Research or Statistics
This is a sequel to the basic course on linear programming, which covers duality theory and the simplex method with its variants, topics whose knowledge is a prerequisite for the present course. We will study polynomial-time algorithms for linear programming, although our focus will be primarily on the practical rather than theoretical efficiency of the solution methods. We will start with the ellipsoid method and its significance beyond linear programming: the equivalence of separation and optimization. We will then review the main types of interior point methods: affine scaling algorithms, potential reduction methods, path following algorithms of the primal and primal-dual variety. Our emphasis will be on the basic techniques of the interior point approach, common to most of these algorithms, like barrier functions, search directions, Newton steps, strictly complementary pairs of solutions, etc. , but we will also review some implementation issues. Additional topics to be discussed include linear programs with complementarity constraints, elements of game theory, robust linear programming.
Lecture: 100min/wk and Recitation: 50min/wk