67.696/92.696 Advanced Linear and Nonlinear Programming

• Course Outline: The first half of the course will examine polyhedral theory, the simplex method, decomposition methods for large scale linear programming problems, and the ellipsoid method. The second half will cover interior point methods for linear programming, which have been developed since 1984. Interior point methods can be regarded as methods for nonlinear programming applied to linear programming. They can also be used to solve nonlinear programming problems.
  1. Polyhedral theory: (2-3 weeks)
     The feasible region of a linear programming problem is a polyhedron, ie, the intersection of a finite collection of half spaces. The structure of polyhedra is discussed, including the Goldman Resolution theorem, and the Weyl and Minkowski theorems.
  2. The simplex algorithm: (1-2 weeks)
     The simplex method is the traditional method for solving linear programming problems. I will discuss the simplex method in matrix terms, and indicate how it can be implemented efficiently.
  3. Decomposition methods for large scale problems: (1 week)
     Some large linear programs can be broken into smaller ones and the polyhedral structure of linear programming can be exploited to develop an algorithm.
  4. The ellipsoid algorithm: (1 week)
     The ellipsoid algorithm was the first polynomial algorithm for linear programming. It was developed originally as an algorithm for nonlinear programming.
  5. Column generation methods: (1-2 weeks)
     These can be used to solve stochastic programming problems, multicommodity flow problems, integer programming problems, and Lagrangian relaxations of various problems including vehicle routing problems.
  6. Interior point methods: (7-8 weeks)
     Karmarkar introduced an algorithm for linear programming in 1984 which has led to a considerable amount of research and the development of a whole class of interior point methods. Topics to be discussed include the similarity of these algorithms to traditional nonlinear programming methods, the polynomial complexity of many of these algorithms, the asymptotic rate of convergence of the algorithms, and the computational results achieved. Interior point methods for quadratic programming problems and general convex problems will also be discussed. Efficient linear algebra techniques will also be discussed.
• Grading policy: The grade will be determined by three elements: homework, a midterm exam, and a presentation. The three elements will be equally important. I will give out a homework approximately every two weeks. The homeworks will probably contain some computational work. There will be a take home midterm exam. The presentation will be of one or two recent papers in interior point methods. You will also have to write a summary/analysis of the paper(s).
  You should learn a fair amount from the homeworks. Therefore, try working out the solutions on your own. If you have difficulties, you may talk to me or to other students about the homeworks, but you must write up your solutions on your own. The exam must be all your own work. The presentations will be individual. You may discuss your paper(s) with other people and with me, but your summary must be your own work, and you will obviously have to do your own presentation.
• Office Hours: Monday, Wednesday 2-4pm.
• Textbooks:

  Recommended:	R. Saigal, Linear Programming: A Modern Integrated Analysis. Kluwer Academic Publisher, 1995.
  Current papers:	Because there is a great deal of continuing research on interior point methods, I will draw some material from current papers. I will put several papers on reserve as the semester progresses.
  On reserve:	V. Chvátal, Linear Programming. Freeman, 1983. Covers most of the first half of the course.
  	Fang and Puthenpura, Linear Optimization and Extensions. AT&T, Prentice-Hall 1993. Not as detailed as Chvátal on traditional material. However, contains five chapters on interior point methods, describing some of the important results up through early 1991.
  	K. G. Murty, Linear Programming. Wiley, 1983. Similar to Chvátal.
  	Nemhauser et al., Optimization. North-Holland, 1989. Several different authors contribute chapters on various aspects of optimization. This book is at a fairly high level. Chapter 2 is a good description of linear programming. Chapter 5 contains several useful results in polyhedral theory.
  	Fiacco and McCormick, Nonlinear programming; sequential unconstrained minimization techniques. Wiley, 1968. The techniques presented in this book can be specialized to give interior point methods for linear programming.
  	H. Karloff, Linear Programming. Birkhauser, 1991. Has one chapter on Karmarkar's original algorithm.
  	N. Megiddo, editor, Progress in Mathematical Programming: interior-point and related methods. Springer-Verlag, 1989. Contains eight interesting papers.

• Prerequisites: 67.411/92.473 and 67.412/92.474, or permission of instructor. Familiarity with linear programming and linear algebra will be assumed. As can be gathered from the outline, the course will be largely theoretical. Some elements of 67.611 and 67.613, such as the Karush-Kuhn-Tucker optimality conditions and Newton's method, will be used, although it is not necessary to have seen this material before.
• The World Wide Web: This outline, the homeworks, and other information will be available online.
• Academic Integrity: Student-teacher relationships are based on mutual trust. Acts which violate this trust undermine the educational process. The Rensselaer Handbook defines various forms of academic dishonesty and procedures for responding to them. The penalties for cheating can include failure in the course, as well as harsher punishments.
• Appealing grades: As with any other administrative question regarding this course, see me in the first instance. If we are unable to reach agreement, you may appeal my decision to the Chair of the Math Sciences department.

  Back to my homepage