Interior Point Methods of Mathematical Programming

The text provides an overview of the research in interior point methods since the publication of N. Karmarkar's seminal paper in 1984. Leading international experts have contributed to the book with summaries of their relevant areas of specialization. Part I gives an overview of basic variants of interior point algorithms for linear programming. Duality-theory for LP and sensitivity analysis is developed. Results on the affine scale, path following, potential reduction, infeasible interior point methods and implementation strategies are discussed. Part II deals with nonlinear programming. Here necessary smoothness conditions are introduced and illustrated. Algorithms for general smooth convex problems, complementarity and semidefinite optimization problems are presented. The implementation of barrier methods for general nonlinear optimization problems is also considered. Part III covers some application areas such as combinatorial optimization, global optimization and VLSI design.