第8回研究会(2007年10月20日(土) 14時 〜)講演概要

会場: 上智大学 四谷キャンパス 11号館3階 11−305

講演者: 小市 俊悟 氏(東京大学)
タイトル: 有限距離空間の多面体的実現と有向多品種流問題
概要: 木距離が枝に非負長の付随した木で表現できることの拡張として 有限距離空間を多面体の集合として実現する手法を提案する.ただし, ここでいう距離は対称性と三角不等式を必ずしも満たさない.そのよ うな 多面体的実現の応用として,多品種流問題の双対問題の最適解に関する 分数性が多面体的実現の次元によって特徴付けられることを紹介する. この研究は,京都大学数理解析研究所の平井氏との共同研究である.

講演者: 土谷 隆 氏(統計数理研究所)
タイトル: 情報幾何と内点法
概要: 本講演では、凸錐上の線形計画問題の情報幾何と内点法について 論ずる. 凸錐上に Self-concordant 障壁関数による情 報幾何的構造 を導入する. そして、多項式時間パス追跡法の反復回数が中心 曲線の 情報幾何学的な意味での曲率積分により厳密に表現できることを示す. さらに、Vavasis-Ye や Monteiro-Tsuchiya において 研究されてきた、 LPの中心曲線の幾何学的性質に関する諸結果を用い、LP の中 心曲線 の全曲率を評価する. その解析を通じ、「LP の場合、 主内点法の 反復回数は、主双対内点法の反復回数よりも少なくなる」ことを、 幾何学的議論より示す. 最後にこれらの結果の情報幾何的意味付けについて議論する. 本研究は小原敦美氏(大阪大)との共同研究である.

ホーム

Copyright, S@CO All rights reserved, 2006-2007.