多項式計画問題に対する大域的最適解法とその並列計算

点击翻译按钮获取中文摘要

本研究の目的は「研究代表者小島等が提案した凸緩和法の枠組みを凸錐上での多項式計画問題に拡充、強化し、実社会かち生ずる複雑で規模の大きい最適化問題に対する数値解法を構築する」ことにあった。この目的に沿って研究を行い、以下のような成果を得た。(1)大規模な多項式計画問題に対する凸緩和において、データの疎性を有効利用する技法を考案した。(2)より一般的な最適化問題である多項式半正定値最適化問題に対して凸緩和法の枠組みを拡張した。(3)半正定値計画問題を解くソフトウエアSDPAを改良し、高速化、数値安定化した。(4)SDPAの並列版SDPARAを開発し、その有効性を計算実験により検証した。SDPARAをPCクラスタ上で実行することによって、量子化学から生ずる線形制約条件の個数が数万の大規模な半正定値計画問題を解くことに成功した。(5)逐次凸緩和を組み込んだ非凸型2次計画問題に対する並列分枝限定法をPCクラスタ上に実装し、計算実験によりその有効性を検証した。(6)変数多項式方程式系の全ての孤立解を求めるソフトウエアPHoMを改良し、その数値的な安定性を向上させた。PHoMのいくつかのフェイズを並列化し、それらについて計算実験を行ってその有効性を検証した。以上により、当初計画した研究課題に関してほぼ満足出来る研究成果が得られ、来年度以降の研究への知見も十分に得られた。