対称行列空間における線形最適化問題に対する効率的な解法アルゴリズムに関する研究

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

対称行列空間における線形計画問題に対する内点法、特にアフィンスケーリング法の研究が主なテーマであったが、本研究ではこの方法がうまく働かないことを示すことができた。対称行列空間における線形計画問題は、凸計画問題の一種であり、さまざまな工学的応用があることと、線形計画問題に対する内点法が自然に拡張できることから、近年注目を浴びて活発に研究されている。特に主双対内点法とよばれる方法がよく研究され、一定条件下での多項式時間による収束が証明されると共に、現実の問題を解けるようになってきている。一方アフィンスケーリング法はもっとも基本的な内点法の一種であるが、対称行列空間への拡張の研究は最近に始まったばかりである。これに対し本研究では、具体的な問題を構成し、この問題に対し適当な場所からアフィンスケーリング法を始めると、最適解でない点へ収束することを証明した。すなわち、対称行列空間における線形計画問題に対するアフィンスケーリング法は、大域的収束性を持たないことを示した。当初の目的(大域的収束の証明)とは反対のネガティブな結果であるが、重要な結果である。なお、ここで提示した具体的な問題は非常にシンプルなものであり、主双対内点法を使えば簡単に解けるものである。従ってこの結果は、アフィンスケーリング法が対称空間の線形計画問題に対しては有力な方法ではないことを強く示唆するものである。