半正定値計画問題に対する高速数値計算手法に関する基礎研究

半定规划问题高速数值计算方法基础研究

• 批准号: 07680456
• 负责人: 小島 政和
• 金额: $ 1.34万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07680456/
• 关键词: 半正定値計画問題; 数理計画; 内点法; 線形計画; 組合せ最適化

本研究の目的『主双対内点法を半正定値計画問題を解く実用的な数値解法として発展させる』に沿って以下の研究を行った.1.研究代表者の小島等のグループが提案した線形計画問題の高速解法を半正定値計画問題に拡張し,その実験用ソフトウエアをMathematicaを用いて試作し,Power Machintosh状で改良のための数値実験を行った.2.上記1で試作したソフトウエアを改良し,C++言語で書き直し,3種類のワークステイションSPARC Station,Silicon Graphis,SONY RISC NEWSに実装した.この際,大規模な半正定値計画問題を計算効率よく高速に解くため,過疎なデータ構造を扱えるような工夫を組み込んだ.このソフトウエアは誰でも使えるように公開している.3.上記2のソフトウエアを組み合わせ最適化問題(グラフ分割問題,2次割り当て問題,最大クリーク問題等)や非凸2次計画問題から生ずるさまざまな半正定値計画問題に適用し,計算実験を続けている.4.これまでの実験を等して,提案した方法は局所的な収束性に難があることが判明した.これを改良するために2つの方法(a)予測子修正子法の組み込み(b)新しい探索方向を提案し,その理論的な基礎作りをした。

The purpose of this study is to study the numerical solution of semi-definite value planning problem by using the principal pair interior point method. Power Machinist's improved form and numerical values are implemented in the following ways: 1. Try to improve the form of Machinist,C++ language, 3. Try to improve the form of Machinist,Silicon Graphis,SONY RISC NEWS. At this time, large-scale semi-definite planning problem calculation efficiency, high speed solution, through the structure of the structure of the group time. 3. On 2. The optimization problem (2-order partition problem, 2-order partition problem, maximum partition problem, etc.) 2-order non-convex programming problem 3-order non-convex programming problem 4-order non-convex programming problem 5-order non-convex programming problem 6-order non-convex programming problem 7-order non-convex programming problem 7-order non-convex programming problem 8-order non-convex programming problem 9-order non- 2. Methods for improving (a) the prediction and modification of sub-methods (b) the new exploration direction and the theoretical basis

项目成果

M.Kojima: "Basic Lemmas in Polynomial-Time Infeasible-Interior-Point Methods for Linear Programs" Annals of Opearations REsearch. (掲載予定).

M.Kojima：“线性规划多项式时间不可行内点方法的基本引理”《运算研究年鉴》（待出版）。

S.Mizuno,M.Kojima and M.J.Todd: "Infeasible-Interior-Point Primal-Dual Potential-Reduction Alogorithms for Linear Programming" SIAM Jounal on Optimization. 5〔1〕. 13-51 (1995)

S. Mizuno、M. Kojima 和 M.J. Todd：“线性规划的不可行内点原始对偶势能约简算法”SIAM 优化杂志 13-51 (1995)。

小島,政和: "Semidefinite programmingと内点法" Proceedings of the 39th Annual Conference of the Institute of System,Control and Information Engineers. 33-40 (1995)

Masakazu Kojima：“半定规划和内点方法”第 39 届系统、控制和信息工程师协会年会论文集 33-40 (1995)。

古屋貴行,平林隆一,小島政和: "半正定値計画問題の組み合わせ最適化問題への応用" 最適化:モデリングとアルゴリズム7統計数理研究所共同研究リポート. 〔77〕. 95-104 (1995)

Takayuki Furuya，Ryuichi Hirabayashi，Masakazu Kojima：“半定规划问题在组合优化问题中的应用”优化：建模和算法7统计数学研究所联合研究报告[77]。

M.Shida,S.Shindoh and M.Kojima: "Centers of Monotone Semidefinite Complementarity Problems" 最適化:モデリングとアルゴリズム7統計数理研究所共同研究リポート. 〔77〕. 89-94 (1995)

M.Shida、S.Shindoh 和 M.Kojima：“单调半定互补问题的中心”优化：建模和算法 7 统计数学研究所联合研究报告 [77]。