Interior Point Methods for Some Special Classes of Optimization Problems
摘要
The Ellipsoid Method was the first polynomial-time method for solving linear programming (LP), which was proposed by Soviet mathematician, L. G. Khachiyan in 1979. However, the first practical polynomial-time method for linear programming problems was Karmarkar’s interior-point method, proposed in 1984. Many variations of interior-point methods have been proposed afterward and these are extended for convex optimization problems. Since then, the advancement of interior point methods has happened very fast in both theory and practice. The purpose of this chapter is to present some basic interior-point methods for linear optimization. Finally, we present a unified interior point method proposed by Kojima et al. that solves LP, linear fractional programming problems, and convex optimization problems with linear constraints.