平成１０年度９月　ＲＡＭＰの案内

• 日時：9月19日（土） 14:00 〜 17:00
• 場所：上智大学10号館3階322号室

• 発表１：水野眞治氏（統計数理研究所）

  『自己双対内点アルゴリズムについて』
  

  線形計画問題を実際に内点法で解く場合に重要な問題の一つに、 初期点をいかに求めるかといったことがある。これにはいくつかの アプローチがあり、大きな係数を使った人工問題を作る方法、初期点を まず求めて(Phae I)から問題を解く(Phase II)方法、勝手な正の初期点 を使うインフィージブル内点法などがあるが、ここでは自己双対線形計画 問題を使う方法を紹介する。この方法の特徴には、勝手な初期点を使える、 反復回数が多項式オーダでおさえられている、問題の実行不能性を判定 できる、といったことがある。 この発表では、二つの異なった自己双対内点アルゴリズムを紹介する。 ひとつは、Ye,Todd,Mizunoにより提案された方法であり、他方は 最近 Nesterov,Todd,Ye により提案された方法である。これらの方法は、 センターパスを逆方向に追跡するといったように、一見全く異なる ように見える。しかし、適当な変換のもとで、これらの方法が密接に 関連していることを示す。

• 発表２：竹内史比古氏 (東京大学情報科学専攻）

  『3角形分割にまつわる凸多面体』（仮題）
  

  与えられた点配置の3角形分割全体にともなう凸多面体はいくつか考えられる。 それらの間の関係、3角形分割の最適化との関係、3角形分割の代数的な側面な どについて考察する。