scientific article; zbMATH DE number 1131479

From MaRDI portal
Publication:4382667





The book is concerned with interior point methods for solving optimization problems. This area has received much attention recently for various reasons. Many researchers have found some of these methods to be far more efficient than the simplex method on a wide range of large calculations, while its polynomial time properties are fundamental to research on complexity. The author highlights in this book the underlying interior point geometry, combinatorics, and the potential theory for convex inequalities. The worst-case complexity bound for interior point algorithms is studied. Some of the recent results on average case analysis and asymptotic analysis are also presented. The discussion on several effective implementation techniques frequently used in interior point linear programming software is an added feature of the book. The book contains ten chapters and each chapter is followed by `Notes' and `Exercises'. The first chapter is an introduction and discusses some of the mathematical preliminaries required in subsequent chapters. Several decision and optimization problems, models of computation and several basic numerical procedures used in the subsequent chapters are also presented here. The second chapter deals with the geometry of inequalities and interior point algorithms. Some of the important concepts, such as `Center', `Volume' and potential of a polytope are discussed here. The third chapter is devoted to the computation of analytic center. The fourth chapter considers five interior point linear programming algorithms, namely. Karmarkar's projective algorithm, the path-following algorithm, the potential reduction algorithm, the primal-dual algorithm including the predictor-corrector algorithm, and the affine scaling algorithm. The fifth chapter deals with the worst-case complexity bound for interior point algorithms. The main issues discussed in this chapter are arithmetic operation, termination and initialization techniques. The sixth chapter is devoted to the study of average case analysis where the idea is to obtain rigorous probabilistic bounds on the number of iterations required by an algorithm to reach some termination criteria. The average complexity results of interior point algorithms for solving the random linear programming model of Todd are presented here. Chapter 7 discusses asymptotic convergence analysis and contains complexity results obtained from applying a predictor-corrector algorithm to both linear programming as well as linear complementarity problems. The eighth chapter illustrates the working of potential functions and interior point algorithms for solving broader convex optimization problems including positive semi-definite programming and monotone complementarity problems. Chapter 9 deals with the working of interior point algorithms for solving non-convex optimization problems including fractional programming and general quadratic programming problems and suggests some directions for future research. The tenth chapter is devoted to the discussion of several effective implementation techniques such as the presolver process, the high-order predictor corrector method, the homogeneous and self-dual method, and the optimal basis identifier. The last section on `Notes' in each chapter is useful and keeps the reader informed about the developments in the areas covered. The author could have given hints to the selected exercises listed at the end of each chapter and included them in an appendix at the end for the benefit of a reader.




Cited in
(only showing first 100 items - show all)


Describes a project that uses

Uses Software






This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382667)