改良Chubanov法の対称錐計画問題への拡張

本研究の目的は、1.改良Chubanov法を対称錐計画問題へと拡張、2.提案手法の性能を数値実験により確認、3.他のアルゴリズムと組み合わせて活用、という3つの段階で提案手法の有用性を検討することである。初年度では、提案手法の理論の構築及び実装を行い、上記の1と2の目標を達成した。今年度は、上記の2と3の目標に向けての研究活動を行った。まず、提案手法と対称錐計画問題を解くことができる商用のソフトウェアとで数値実験を行い、それらの結果を比較した。実験結果から、提案手法は商用ソフトウェアよりも、計算機で上手く解けないとされてきた悪状態の問題に対して、実行時間では劣るものの、解の精度で勝ることを確認した。これらの実験結果を含めた内容の論文を現在投稿中である。次に、提案手法を他の手法と組み合わせを検討した。具体的には、計算機で解きにくい悪状態の錐線形計画問題を計算機で解きやすい問題へと等価に変換する面的縮小法との組み合わせ、そして内点法（多くのソフトウェアで実装されている解法）の後処理としての組み合わせを検討した。そして、予備的な数値実験により、提案手法を内点法の後処理として用いることで、効率的に精度の良い解を得られる可能性が高いことを確認した。最終年度では、提案手法を用いた対称錐計画問題に対する後処理アルゴリズムに関しての研究を進めていく方針である。提案手法を用いた後処理アルゴリズムの研究は、面的縮小法が抱える"面的縮小を行うのに必要なベクトルを計算機上で高精度に求めることが困難"という課題を解決する可能性があり、間接的に面的縮小法の課題にも貢献する内容となっている。

本研究の目的は、1.改良Chubanov法を対称錐計画問題へと拡張、2.提案手法の性能を数値実験により確認、3.他のアルゴリズムと組み合わせて活用、という3つの段階で提案手法の有用性を検討することである。初年度では、提案手法の理論の構築及び実装を行い、上記の1と2の目標を達成した。今年度は、上記の2と3の目標に向けての研究活動を行った。まず、提案手法と対称錐計画問題を解くことができる商用のソフトウェアとで数値実験を行い、それらの結果を比較した。実験結果から、提案手法は商用ソフトウェアよりも、計算機で上手く解けないとされてきた悪状態の問題に対して、実行時間では劣るものの、解の精度で勝ることを確認した。これらの実験結果を含めた内容の論文を現在投稿中である。次に、提案手法を他の手法と組み合わせを検討した。具体的には、計算機で解きにくい悪状態の錐線形計画問題を計算機で解きやすい問題へと等価に変換する面的縮小法との組み合わせ、そして内点法（多くのソフトウェアで実装されている解法）の後処理としての組み合わせを検討した。そして、予備的な数値実験により、提案手法を内点法の後処理として用いることで、効率的に精度の良い解を得られる可能性が高いことを確認した。最終年度では、提案手法を用いた対称錐計画問題に対する後処理アルゴリズムに関しての研究を進めていく方針である。提案手法を用いた後処理アルゴリズムの研究は、面的縮小法が抱える"面的縮小を行うのに必要なベクトルを計算機上で高精度に求めることが困難"という課題を解決する可能性があり、間接的に面的縮小法の課題にも貢献する内容となっている。