Decompositions in Interior Point Algorithms

Abstract In 1984 N. Karmarkar of AT&T Bell Laboratories introduced an interior point algorithm for linear programming. The algorithm has a polynomial time complexity bound and has been established, following extensive computational experimentation, as a viable competitor to the classic simplex algorithm for the solution of large-scale linear programs. A flurry of re search activities followed Karmarkar’s work and several interior point algorithms were developed for linear programming, convex quadratic programming, convex programming, linear complementarity problems, and nonlinear complementarity problems. Different mathematical tools have been employed to develop and analyze these algorithms. Depending on the theory underlying the mathematical analysis the algorithms are classified as potential reduction algorithms, path following algorithms, barrier function algorithms, affine scaling algorithms, and projective scaling algorithms.