Interior Point Methods

Update: August 19th, 2008

In 1984, Narendra Karmarkar of AT&T Bell Laboratories, announced an exciting breakthrough in linear programming. Karmarkar’s LP algorithm attracted considerable attention in the scientific community, and even the popular press, due to Karmarkar’s claims of massive speedups, typically by factors of 10-50, compared with the times required by the simplex method on large linear programs.

Although disagreement over Karmarkar’s solution times immediately ensued, all experimental evidence indicated that the new algorithm required a relatively small number of iterations, typically 30-60, to obtain near-optimal solutions to linear programs of virtually any size. The fact that problems with tens of thousands of variables required roughly the same number of iterations as problems with a few hundred variables indicated that the method had tremendous practical potential, at least for large-scale linear programming.

This course discusses the recent developments in interior algorithms both for linear and nonlinear programming with particular emphasis in path following techniques. It gives a unified theory of polynomial-time interior-point methods. Researchers involved in the development of interior-point methods can investigate more general problems rather than focusing on linear programming.

In many fields of engineering, convex problems arise that are not linear or quadratic, but are of a form that can be handled by these methods. Applications cover a wide variety of difficult important problems, from quadratic programming to finding extremal ellipsoids, from extremal eigenvalue problems arising in control theory to geometric programming. Engineers working with shape design, limits of performance controllers, numerical robust stability analysis, design of structures, optimizing planning, transportation, and oil refinery and allocation will benefit from using these methods.

Audience

Graduate students working in the areas of optimization, mathematical programming, or control theory will find this course invaluable for studying interior-point methods for linear and quadratic programming, polynomial-time methods for nonlinear convex programming, and efficient computational methods for control problems and variational inequalities.

Prerequisite

A background in linear algebra and nonlinear programming is necessary to understand the course.

Topics

  1. Introduction: An overview of Central Path Methods.
  2. Tools of Interior Point and Non-Path-following Methods.
    • Affine Scaling Method.
    • Karmarkar’s Method
  3. Barrier Functions and Analytic Center.
  4. Methods of Analytical Centers.
  5. Primal-Dual Methods.
  6. Potential Reduction Methods.
  7. Implementation Issues.
    • Discussion on CPLEX.
    • Discussion on LOQO.
  8. Extensions to convex, integer and multiobjective programming.
  9. Applications in Machine Learning and Neural Networks.
  10. Applications in Financial Planning.
  11. Applications in Design of Structures.
  12. Semidefinite Programming.

Optional Textbooks

Grading and Project

There will be no tests. Grades will be determined by student’s solution to problems distributed during the semester. In addition, each student will be required to make an oral presentation and submit a project.

Comments are closed.
TOP