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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Interior Point Methods for Some Special Classes of Optimization Problems

  • S. K. Neogy,
  • Rina Chakravorty,
  • Sajal Ghosh

摘要

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.