構造を持った多項式最適化問題に対する半正定値計画緩和と二乗和緩和の研究

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

2008年度から引き続き,半正定値計画問題に対するFacial Reduction Algorithmについて研究してきた.Facial Reduction Algorithmは,実行可能内点解を持たない半正定値計画問題に対して,実行可能内点解を持ち,実行可能集合が同じである半正定値計画問題を生成する.生成された半正定値計画問題に主双対内点法を適用することで,解を求めることができる.本研究では,これを凸錐上の線形計画問題に拡張した.さらに,線形計画問題や二次錐計画問題に対して,Facial Reduction Algorithmの挙動を明らかにした.また,ある種の多項式最適化問題から得られる半正定値計画問題に対して,Facial Reduction Algorithmの挙動を明らかにし,これが以前まとめた論文"Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization"で扱った手法と等価であることを明らかにした.電気通信大学の村松正和先生と論文にまとめ,投稿した.また,多項式最適化問題に対して,得られる半正定値計画問題を小さくする手法が提案されている.本研究で,この手法がFacial Reduction Algorithmと深い関係があることを明らかにした.これにより,この手法が数値的安定性にも貢献していることがわかった.