電気通信大学 村松研究室 Muramatsu Laboratory

悪条件錐線形計画問題の理論とアルゴリズム(科研費 基盤B) 

メンバー

  • 村松正和(電気通信大学)
  • 蛯原義雄(九州大学)
  • 山下真(東京工業大学)
  • 奥野貴之(理研AIP)

目的

錐線形計画は半正定値計画(SDP), 2次錐計画(SOCP)など様々なサブクラスが提案されており、また多項式最適化(POP)への応用など、近年研究の発展が目覚ましい。

その中で錐線形計画の実用化において大きな障害となっているのが「悪条件な問題」 の存在である。
悪条件の極限として退化がある。悪条件あるいは退化した錐線形計画問題 は実用において頻繁に出現するにもかかわらず、内点許容解の存在を仮定する従来のアルゴリズムは解くことができないどころか、我々をミスリードするような奇妙な結果を出力することがある。

本研究は、錐線形計画問題における悪条件に関してその理解を深め、またそのような問題に対応する新しい解法を開発することにより、錐線形計画の裾野を広げ、実用に足る段階へもっていくことを目的とする。

期間

2020–2023年度