平成 23 年度第 2 回 ＯＲ横断若手の会(KSMAP)

日時：6 月 4 日(土)
場  所：京都大学 工学部 8 号館 共同 5 講義室

（１）佐藤寛之氏（京都大学）
「グラスマン多様体上の最適化アルゴリズム」

[概要]
本講演では，実行可能領域が多様体であるような
最適化問題が研究成果の報告がなされた．
具体的には，まず，多様体の基礎的な概念の復習をし，
その後，グラスマン多様体上の最適化アルゴリズムの説明がなされた．
また，目的関数が応用上重要なレイリー商と呼ばれるものであるときに，
提案手法によって生成される点列の大域的収束性に関する議論がなされた．

（２） 北原知就氏（東京工業大学）
「単体法によって生成される基底解の数の上界とその初等的証明」

[概要]
本講演では，線形計画問題に対する著名な手法である
単体法に関して，実行可能基底解の上界を示すための証明法が紹介された．
具体的には，得られた上界が，問題の制約式の個数、変数の個数，および
すべての実行可能基底解の正の要素の最大値と最小値の比，
の多項式で表されるという，新しい結果が示された．
なお，証明に対しては，線形計画問題と単体法に対する基礎的知識を
用いたものであったので，学生にも分かりやすい内容であった．