Interior Point Methods for Linear Programs and Their Applications

本研究的目的如下。(1)线性规划原始-对偶内点算法的复杂性评价。(2)内点算法在非凸二次规划和组合优化问题中的应用。(3)利用内点算法开发线性规划软件。(4)将内点算法推广到一般凸规划.为了达到目的（1），我们提出了一种控制步长的方法和一种选择初始点的方法.我们在计算实验中证实了这些新方法的有效性和效率。我们对非凸二次规划和组合优化问题进行了研究，但还没有成功地将内点算法应用到这些问题中。我们还将上述目的（1）中的方法推广到一般的凸规划。

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.