Interior Point Methods for Linear Programs and Their Applications

线性规划的内点法及其应用

• 批准号: 03832017
• 负责人: KOJIMA Masakazu
• 金额: $ 1.28万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1991
• 资助国家: 日本
• 起止时间: 1991 至 1992
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-03832017/
• 关键词: Linear Program; Interior Point Method; Karmarkar's Method; Mathematical Program; Combinatorial Optimization; カ-マ-カ-法

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.

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

项目成果

今野 浩: "Parametric Simplex Algorithms for Solving a Special Class of Nonconvex Minimization Problems" Journal of Global Optimization. 1. 65-82 (1991)

Hiroshi Konno：“解决一类特殊非凸最小化问题的参数单纯形算法”全局优化杂志 1. 65-82 (1991)。

池辺 淑子: "Adjacency of the Best and Second Best Valued Solutions in Combinatorial Optimization Problems" Discrete Applied Mathematics.

Yoshiko Ikebe：“组合优化问题中最佳和次优解决方案的邻接”离散应用数学。

P.T.Thach: "A Generalized Convexity and Variational Inequalities for Quasiconvex Minimization" IHSS 92-50,Tokyo Institute of Technology. (1992)

P.T.Thach：“拟凸最小化的广义凸性和变分不等式”IHSS 92-50，东京工业大学。

小島 政和: "Potential Reduction Algorithms for Monotone Complementarity Problems" 統計数理研究所共同研究レポート. 35. 41-52 (1992)

小岛正和：“单调互补问题的潜在约简算法”统计数学研究所联合研究报告 35. 41-52 (1992)。

小島 政和: "Homotopy Continuation Methods for Nonlinear Complemen-tarity Problems" Mathematics of Operations Research. 16. 754-774 (1991)

Masakazu Kojima：“非线性互补问题的同伦延拓方法”运筹学数学 16. 754-774 (1991)。