大規模最適化問題に対する並列実行ソフトウェアの開発と実証実験

大规模优化问题并行执行软件开发与演示实验

• 批准号: 12780215
• 负责人: 藤澤 克樹
• 金额: $ 1.41万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780215/
• 关键词: 数理最適化; GRID技術; 非凸最適化問題; 半正定値計画問題; クラスタコンピューティング; 高性能並列計算; ソフトウェア; 非凸型最適化問題; 広域高性能計算; 主双対内点法; 逐次凸緩和法

本年度は超広域高性能計算技術(Ninf産業技術総合研究所において開発)を用いて最新の数理最適化問題アルゴリズムである半正定値計画問題(Semidefinite Programming : SDP)に対する主双対内点法ソフトウェアSDPAを、専用クラスタ計算機の広域連合によって分散並列化し、従来では統一的な方法で解くことができなかった様々な種類の非凸最適化問題を解くことに成功した。具体的には,最新の主双対内点法を拡張したSDPの高速解法アルゴリズムSDPA、および一般の非凸計画問題まで解くことのできる逐次凸緩和法(Successive Convex Relaxation Method,以下SCRMと略)アルゴリズムの並列化を行った。SCRMの並列ソフトウェアを大規模な非凸最適化問題に適用した。その場合128台程度の大規模PCクラスタ上でSCRMを実行し、1台の場合と比較して90倍以上も高速化することに成功している.SCRMでは、各ステップの緩和計算に複数のSDPAソルバをを並列に用いる。このため、複数のSDPA問題の生成、各計算ノードヘの並列割り当てと計算、並列部分解の収集、を繰り返すという概略になるよって、各並列計算の単位は比較的疎粒度となることが判明した。本年度は,特にインターネット上に広域に分散配置されている複数のPCクラスタを用いて数値実験を行い、SCRMのアルゴリズムが超広域高性能計算に向いていることを示し、結果を論文や国際会議等で発表した。また本研究で得られた知見は、多面体的ホモトピー法を用いて、多変数多項式方程式系の全ての孤立解(実根及び複素根)を求める研究にも応用することができた。

This year, Ninf High performance Computing Technology (HPCT) uses the latest mathematical optimization problems, mathematical optimization problems, positive semidefinite programming problems (Semidefinite Programming: SDP), principal double-point interior point method, SDPA, computer connection, computer, and computer. In order to solve the problem of non-convex optimization, we have successfully solved the problem of non-convex optimization. For specific information, the latest principal double interior point method, the SDP method, the high-speed solution, the SDPA, the general non-convex drawing problem, the successive convex sum method (Successive Convex Relaxation Method, the following SCRM summary), the parallel algorithm. SCRM also lists the usage of the non-convex optimization problem of large-scale modules. A total of 128sets of large-scale PC models are installed on the SCRM line, 1 set is more than 90 times higher, and the high-speed speed is more than 90 times higher. SCRM is used to calculate the number of copies, and the number of copies is calculated. SCRM is used. For example, the SDPA problem generation of complex numbers, the calculation data of each calculation and the list of the corresponding calculations, the parallel list of partial solution sets, the summary of the calculation data, and the determination of the granularity of each calculation bit ratio. This year, special attention has been paid to the distributed configuration of domains, the number of complex numbers, the number of PC data, the number of data lines, the number of SCRM data, the performance of domain high-performance calculations, and the results of the international conference. The purpose of this study is to find out the exact solutions (roots and complex roots) of the equations of polyhedron, polyhedron, polyhedron and polyhedron in this study.

项目成果

A.Takeda,K.Fujisawa,Y.Fukaya and M.Kojima: "A Parallel Successive Convex Relaxation Algorithm for Quadratic Optimization Problems"The Institute of Statistical Mathematics Cooporative Research Report. 135. 238-258 (2000)

A.Takeda、K.Fujisawa、Y.Fukaya 和 M.Kojima：“二次优化问题的并行连续凸松弛算法”统计数学研究所合作研究报告。

K.Nakata,K.Fujisawa,M.Fukuda,M.Kojima and K.Murota: "Matrix Completion and Semidefinite Programming"The Institute of Statistical Mathematics Cooporative Research Report. 135. 223-237 (2000)

K.Nakata、K.Fujisawa、M.Fukuda、M.Kojima 和 K.Murota：《矩阵补全与半定规划》统计数学研究所合作研究报告。

A.Takeda, M.Kojima, K.Fujisawa: "Enumeration of All Solutions of a Combinatorial Linear Inequality System Arisin from the Polyhedral Homotopy Continuation Method"Journal of the Operations Research Society of Japan. (掲載予定). (2002)

A.Takeda、M.Kojima、K.Fujisawa：“由多面体同伦连续法产生的组合线性不等式系统的所有解的枚举”日本运筹学会杂志（2002 年）。

A.Takeda, K.Fujisawa, Y.Fukaya, M.Kojima: "A Parallel Successive Convex Relaxation Algorithm for Quadratic Optimizatioi Problems"The Institute of Statistical Mathematics Cooporative Research Report. Vol.135. 238-258 (2000)

A.Takeda、K.Fujisawa、Y.Fukaya、M.Kojima：“用于二次优化问题的并行连续凸松弛算法”统计数学研究所合作研究报告。

A.Takeda, K.Fujisawa, Y.Fukaya, M.Kojima: "Parallel Implementation of Successive Convex Relaxation Methods for Quadrati Optimization Problems"J. of Global Optimization. (掲載予定). (2002)

A.Takeda、K.Fujisawa、Y.Fukaya、M.Kojima：“二次优化问题的连续凸松弛方法的并行实现”J. of Global Optimization（即将出版）。