2011年度第1回 SCOPE講演会

2011年度第1回 SCOPE 研究会を以下の日程で開催することになりました。講演会の後は懇親会も予定しています。

○2011年度 第1回 SCOPE 講演会

日　時 ： 2011年7月9日（土）14:00～17:00
会　場 ： 中央大学 後楽園キャンパス 6号館 4階 6410室

講演1
講演者 ： 北原知就氏 (東京工業大学 大学院社会理工学研究科 経営工学専攻)
題目 ： 単体法によって生成される実行可能基底解の個数の上界について
概要 ： 単体法は線形計画問題に対する最初の解法で，実用上は非常に効率的であることが知られている。しかし，一般的な線形計画問題に対する単体法の反復回数の評価はほとんど知られていない．その大きな障害となっているのが，Klee-Mintyによって発表された単体法が指数回の反復回数を必要とし得るという事実である．北原-水野(2010年)はマルコフ決定問題に対するYeの解析(2010年)を応用し，単体法が生成する実行可能基底解の上界を示した。得られた上界は問題の制約式の個数、変数の個数，およびすべての実行可能基底解の正の要素の最大値と最小値の比，の多項式で表される．そして問題が非退化のとき，この上界は反復回数の上界となる。本講演では、上界を得るための解析について詳しく説明する。また，新たに開発した簡易版Klee-Minty問題を使い，良い上界が得られていることを示す．

講演2
講演者 ： 後藤和茂氏 (米 Microsoft Corporation)
題目 ： 最適化における性能測定　
概要 ： 本講演では構成を大きく２つに分ける。前半では講演者の経験をもとにアメリカの文化及び労働環境について具体例を交えて紹介する。後半では講演者の専門である最適化に関して、特に最適化の評価をするための性能測定（いわゆるベンチマーク）についての解説を行う。プログラムの作成においては単に正しい結果が必要なだけではなく多くの場合同時に性能を必要とする場合が多いが、その性能を評価する手法に関してはあまり知られていない。そこで本講演では性能を正確に測定する手法を紹介するとともに、対象となるシステムから得られる特性から性能を予測することにより得られた性能の妥当性を検証する手法を紹介する。