対称錐上の線形計画問題と大域的最適化

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

今年度も多項式計画(大域的最適化)に関する研究と,2次錐計画に対するピボットアルゴリズムという2本をテーマに研究を行なった。両方とも対称錐上の線形計画問題に密接に関係するテーマである。前年より続く東工大の小島教授,韓国Ewha Women's UniversityのKim教授,それに大学院生の脇氏らと共同研究をさらにすすめた。SDP緩和問題を作る際に,その疎性を利用して解くべき最適化問題のサイズを小さくするアイデアを論文にしたものはSIAM Journal on Optimizationに受理された。これにより,変数の数が多い大域的最適化問題(多項式計画問題)を解けるようになった。また,そのアイデアに基づくソフトウエアSparsePOPをMATLABで実装し,公開している。従来の多項式計画のソフトウェアが15変数程度の問題までしか解けないのに比べ、SparsePOPは条件によっては1000変数の問題まで解くことができるようになった。一方,対称錐計画問題の一種である2次錐計画に対しても,ピボットを用いたアルゴリズムの研究は続けている。理論的には,複数の2次錐を持つ場合の解析を行ない,ピボットアルゴリズムをすっきり記述できるようにした。この結果は現在投稿中である。また1つの錐の場合の実装を大学院生の栗田氏と共同で行ない、アルゴリズムの挙動を観察した。その結果,実装に関する様々な問題点が浮かび上がった。この結果は日本語の論文としてまとめ,統計数理に受理・掲載された。