内点法によるシステム最適化とその応用

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

半正定値計画問題の一般化である自己双対な錐の上の線形計画問題の内点法による解法の開発および応用について研究を進めた.この問題は(古典的)線形計画問題,2次錐計画問題,半正定値計画問題など重要な問題を含んでおり,これらを統一的に取り扱う理論および実装を発展させることにより,より柔軟なモデリングの道具を現場に提供することができる.そのために,特に問題をJordan代数の立場から理解し,主双対内点法の統一的理論を構築し,得られたアルゴリズムを実際問題に適用することを目標とした.その方向に向けて,2次錐計画問題や半正定値計画問題などの具体例の計算を通じてある程度の進展が得られたと考えている.具体的な成果は以下の通りである.1. Monteiro-Zhang探索方向族を用いた主双対内点法の解析を2次錐計画問題に対して行い,この族を用いたショートステップパス追跡法がO( n L)反復の多項式アルゴリズムであることを証明した.2. 半正定値計画問題に対するMonteiro-Tsuchiya族の部分族でスケーリング不変で自己双対なものを発見した.この族はNestcrov-ToddやHRVW/KSH/Mなどよく知られたスケーリング不変な探索方向族を含むものである.応用に関しては,半正定値計画問題の統計学のグラフィカルモデル推定への応用や2次錐計画問題の最適設計問題への応用などについて研究を現在進めている.これらの結果については今後論文にまとめていく予定である.