Interior Point Methods for Linear Programs and Their Applications

点击翻译按钮获取中文摘要

The purpose of this study is as follow.(1) Evaluation of complexity of primal-dual interior point algorithms for linear programs.(2) Applications of interior point algorithms to nonconvex quadratic programs and combinatorial optimization problems.(3) Development of software for linear programs with the use of interior point algorithms.(4) Extension of interior point algorithms to general convex programs.For the purpose (1), we proposed a method for controlling step lengths and a method for choosing an initial point from which an interior point for a linear program starts. We confirmed for the purpose (3) the effectiveness and efficiency of these new methods in computational experiments. We made investigation into nonconvex quadratic programs and combinatorial optimization problems, but we have not succeeded in incorporating interior point algorithms into the problems. We also extended the methods mentioned above in the purpose (1) to general convex programs.