半正定値計画法を使った大域的最適化問題に対する新解法の研究

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

本研究は,大規模な非凸2次計画問題に対する大域的最適化アルゴリズムの構築を目標とした.この際,半正定値計画問題を解くことで,最適解の近似が行えるという性質を用いた.また,本研究では,半正定値計画問題に,ある種の不等式(切除平面)群を追加し最適化を行うこと,すなわち切除平面法を応用することで,より計算効率の高いアルゴリズムの構築を目指した.そのために,半正定値計画問題を緩和問題として使い,線型制約上で非凸2次関数を最小化するアルゴリズムを,計算機上に実装した.計算効率の向上に寄与する度合いの大きな不等式の生成,選択,追加等に関する戦略の検討を数値実験を通じて行った.その結果,低ランク(ランク2あるいはランク3)不等式(切除平面)を提案した.問題の目的関数が粗な行列の場合や,非常に凸性や凹性の強い場合では,ランク1の不等式を使うだけで,十分によい解を短時間に生成できることが確認できた.たま,一方で,行列が密で,正の固有値数と負の固有値数がほぼ同数といった問題に対しては,ランク1の不等式だけでは不十分であり,一般的な低ランク不等式を追加することで,解が改善されることを確認した.また,粗な問題に対しても,ここで提案した低ランク不等式使った場合の方が,より少ない本数の不等式で制度のよい解を算出できることを示した.さらに,その現実問題への応用性を確かめるために,ディスタンスジオメトリー問題と呼ばれる,空間に点を配置する問題へ,本手法の適用を行った.この問題は,適当な変形を施せば,凹2次計画問題へと定式化が可能であり,その近似的な最適解を半正定値計画問題を解くことで得ることが可能である.数値的な実験の結果,従来の近似手法と比べ,はるかに精度の良い解を算出できることが確認された.