最適化問題を高速に解く内点法の開発

最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されている未知の定数を使う必要があり、実際的なアルゴリズムではなかった。本研究では、このタイプに属するが、そのような未知数を必要としない新しいアルゴリズムを提案し、その収束性を明らかにした。このアルゴリズムは、変数の大きさによる層分割を利用して探索方向を求めることにより、既知のアルゴリズムの高速化に成功している。また、内点法を研究する上で重要なセンターパスの解析を行い、アルゴリズムの計算複雑度に関する新しい解析を行った。内点法のアルゴリズムでは、大規模な線形方程式を解く必要がある。線形方程式を正確に解くことは理論的に可能であるが、問題が大規模な場合などには、実際には近似的な解を求めるだけの場合も数多くある。今までの内点法の収束性の解析では、この線形方程式の解が正確に求められるということを仮定していた。本研究では、線形方程式の解法に近似計算を使うアルゴリズムについて、理論的な解析を行った。そして、大域的に収束するアルゴリズムを開発し、さらに多項式オーダーの反復回数で収束するための条件を求めた。

最適化問題を解く内点法についての基礎的な研究を行った。とくに、アルゴリズムの理論的な収束性について研究した。線形計画問題を解く内点法には、多項式オーダーで収束するアルゴリズムが数多く提案されているが、その中でも係数行列のみに依存した数で反復回数がおさえられる新しいタイプのアルゴリズムが、VavasisとYeにより最近発表された。このアルゴリズムは、優れた収束性を備えているが、理論的に定義されている未知の定数を使う必要があり、実際的なアルゴリズムではなかった。本研究では、このタイプに属するが、そのような未知数を必要としない新しいアルゴリズムを提案し、その収束性を明らかにした。このアルゴリズムは、変数の大きさによる層分割を利用して探索方向を求めることにより、既知のアルゴリズムの高速化に成功している。また、内点法を研究する上で重要なセンターパスの解析を行い、アルゴリズムの計算複雑度に関する新しい解析を行った。内点法のアルゴリズムでは、大規模な線形方程式を解く必要がある。線形方程式を正確に解くことは理論的に可能であるが、問題が大規模な場合などには、実際には近似的な解を求めるだけの場合も数多くある。今までの内点法の収束性の解析では、この線形方程式の解が正確に求められるということを仮定していた。本研究では、線形方程式の解法に近似計算を使うアルゴリズムについて、理論的な解析を行った。そして、大域的に収束するアルゴリズムを開発し、さらに多項式オーダーの反復回数で収束するための条件を求めた。