トップページ

様々な数理計画問題を解くためのアルゴリズムの研究を行っています。例えば、大規模な半正定値計画問題を主双対内点法を用いて効率良く解く研究などです。以下では、その研究について説明します。

半正定値計画問題は数理計画の中の典型的な問題の１つです。英語では semidefinite programming となりますので、略して SDP と呼ばれることも多いです。よく知られている線形計画問題・凸2次計画問題・２次錐計画問題は、半正定値計画問題の特殊ケースとみなせます。それに加えて、行列の固有値情報からなる制約を記述できるため、構造最適化・システム制御・量子化学・統計・金融工学などの様々な分野で現れる最適化問題を解くことができます。つまり、半正定値計画問題は、非常に大きなクラスの数理計画問題であるといえます。

半正定値計画問題を解く手法として、主双対内点法が知られています。元々内点法は、1984年にN.Karmarkarが線形計画問題を解くアルゴリズムとして提案した方法です。この方法は多項式時間内で解けることが理論的に保証できたというだけでなく、実際に大規模問題が高速に解けたという画期的なものでした。所属会社のAT&Tがこのアルゴリズムで特許を取ろうとしたこともあり、当時は話題となりました。その辺りの話は、今野浩先生の「カーマーカー特許とソフトウェア」中公新書　に詳しく述べられています。
この線形計画問題を解くための内点法を拡張することにより、半正定値計画問題を解く内点法が構築できることが分かり、ここ10年近くさかん研究が行われてきました。現在、半正定値計画問題を安定的に効率良く解くアルゴリズムは内点法であるといわれています。アルゴリズムの詳細を知りたい方は、半正定値計画問題に対する主双対内点法を御覧下さい。

半正定値計画問題と線形計画問題には本質的な難しさの差があります。そのため、一般に半正定値計画問題を内点法で解くことは、線形計画問題を内点法で解くほど容易ではありません。実際、線形計画問題では線形制約や変数の個数が数百万以上の大規模な問題を実用的に解くことが可能であるのに対し、半正定値計画問題では線形制約や変数の個数がそれぞれ数千、数十万以上となる大規模問題を解くことは困難です。この問題点を解決するため、以下のような研究を行ってきたあるいは研究中です。