Efficient Algorithms for Large Optimization Problems

大型优化问题的高效算法

• 批准号: 12680433
• 负责人: MIZUNO Shinji
• 金额: $ 2.18万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12680433/
• 关键词: Optimization; Algorithm; Interior Point Method; Linear Programming; 最適化問題

This research aims to develop efficient algorithms for solving large optimization problems and to investigate their theoretical properties and practical usage. In 2000, we did basic research for the purpose. There are 3 types of variables, free variables, nonnegative variables and bounded variables. in large optimization problems. We investigated efficient algorithms which can handle all these types of variables simultaneously. In 2001, we studied algorithms for solving large problems with a special structure. Especially, we proposed a new algorithm for solving multistage stochastic programming problems. These problems could be very large when the number of stages is not small. We use the special structure of the problems and developed an efficient algorithm for them. In 2002, we investigated a new algorithm for solving large linear and nonlinear programming problems. The algorithm uses a logarithmic transformation to the variables in the problem. This transformation makes the path of centers smooth and the algorithm efficient. From some preliminary computational experiment, we found that the algorithm can solve large problems very quickly.

本研究旨在开发解决大型优化问题的有效算法，并研究其理论性质和实际用途。2000年，我们为此做了基础研究。有三种类型的变量，自由变量，非负变量和有界变量。大型优化问题。我们研究了有效的算法，可以同时处理所有这些类型的变量。在2001年，我们研究了解决具有特殊结构的大型问题的算法。特别地，我们提出了一个求解多阶段随机规划问题的新算法。当级数不小时，这些问题可能非常大。我们使用的特殊结构的问题，并开发了一个有效的算法。在2002年，我们研究了一个新的算法来解决大型线性和非线性规划问题。该算法对问题中的变量进行对数变换。这种变换使得中心的路径平滑，算法高效。通过初步的计算实验，我们发现该算法可以非常快速地解决大型问题。

项目成果

S. Mizuno and M. J. Todd: "On Two Homogeneous Self-Dual Systems for Linear Programming and Its Extensions"Mathematical Programming. 89, NO.3. 517-534 (2001)

S. Mizuno 和 M. J. Todd：“关于线性规划及其扩展的两个齐次自对偶系统”数学规划。

水野眞治: "特殊な構造を持つ線形計画問題の内点法"数理解析研講究録. 1297. 234-244 (2002)

水野真司：《特殊结构线性规划问题的内点法》数学分析研究记录1297.234-244（2002）。

中田和秀: "大規模線形方程式を解くためのクリロフ部分空間法の前処理"数理解析研講究録. 1228. 52-64 (2002)

Kazuhide Nakata：《求解大规模线性方程的Krylov子空间方法的预处理》数学分析研究讲座记录。1228. 52-64 (2002)

S.Mizuno, M.J.Todd: "On two Homogeneous Self-Dual Systems for LP and Its Extension"Mathematical Programming. 89. 517-534 (2001)

S.Mizuno，M.J.Todd：“关于 LP 的两个齐次自对偶系统及其扩展”数学规划。

S. Nishibu and S. Mizuno: "Interior Point Methods for Linear Programming with Bounded Variables"Optimization : Modeling and Algorithm 15, ISM Cooperative Research Report. 148. 250-261 (2002)

S. Nishibu 和 S. Mizuno：“有界变量线性规划的内点方法”优化：建模和算法 15，ISM 合作研究报告。