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

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

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