The recent remarkable developments of interior point algorithms began in 1984 with Karmarkar's polynomial-time interior point algorithm for linear programs using a log- arithmic potential function and a projective transformation. The progress has been made so rapidly and extensively that it seems difficult to get a comprehensive view over the entire field of interior point algorithms. Indeed, numerous interior point algo- rithms have been proposed for various mathematical programming problems, including linear programming, convcx quadratic programming and convex programming. Many computational experiments have also been reported together with various techniques for improving their practical computational efficiency. One way of summarizing the entire field would be to write a survey paper picking up some of the important results and stating their relationships. We will use a different approach because we arc more inter- ested in the common basic ideas behind the interior point algorithms developed so far than the individual algorithms and their relationships. Of course, it would be impossible to establish a common theory covering the entire field of interior point algorithms. We restrict ourselves to a certain subclass of interior point algorithms, and present a unified and basic theory for it. Even so, our theory involves many of the important notions that have been playing essential roles in this field.

Following Karmarkar's 1984 linear programming algorithm, numerous interior-point algorithms have been proposed for various mathematical programming problems such as linear programming, convex quadratic programming and convex programming in general. This monograph presents a study of interior-point algorithms for the linear complementarity problem (LCP) which is known as a mathematical model for primal-dual pairs of linear programs and convex quadratic programs. A large family of potential reduction algorithms is presented in a unified way for the class of LCPs where the underlying matrix has nonnegative principal minors (P0-matrix). This class includes various important subclasses such as positive semi-definite matrices, P-matrices, P*-matrices introduced in this monograph, and column sufficient matrices. The family contains not only the usual potential reduction algorithms but also path following algorithms and a damped Newton method for the LCP. The main topics are global convergence, global linear convergence, and the polynomial-time convergence of potential reduction algorithms included in the family.