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

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

• 批准号: 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, we used ultra-wide-area high-performance computing technology (developed at the Ninf National Institute of Advanced Industrial Science and Technology) to dispersely parallelize the main dual-in-point software SDPA for the latest mathematical optimization problem algorithm, Semidefinite Programming (SDP), by using a wide-area association of dedicated cluster computers, and successfully solved various types of non-convex optimization problems过去无法使用统一方法来解决。具体而言，我们将SDPA算法平行于SDP的快速解，该算法扩展了最新的主双内点方法，以及连续的非convex编程问题的顺序凸出弛豫方法（SCRM）算法。 SCRM并行软件应用于大规模的非凸优化问题。在这种情况下，SCRM是在大约128个单元的大型PC群集上执行的，并且成功地使其比一个单元快于90倍的速度更快。因此，已经发现，每个平行计算的单元具有相对稀疏的粒度，因为它们通过生成多个SDPA问题，对每个计算节点的平行分配和计算以及平行部分解决方案的收集来大致重复。今年，我们特别使用在互联网上分布的多个PC群集进行了数值实验，这表明SCRM算法适用于超宽范围的高性能计算，结果在论文和国际会议上呈现。在这项研究中获得的发现也可以应用于使用多面体同型方法的多变量多项式方程系统的所有分离溶液（实际根和复杂根）的研究。

项目成果

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, 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, 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: "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（即将出版）。