第１１回研究会（２００８年６月２８日（土） １４時 〜）講演概要
会場： 上智大学 四谷キャンパス １１号館２階 １１−２０９
講演者：
森山 園子 氏 （東京大学）
タイトル：
有向マトロイドの実現可能性問題における様々な展開
概要： 有向マトロイドとは，点・ベクトル配置，超平面配置，多面体等の幾何構造を抽象化した組合せ構造である． ある幾何構造に対してその組合せ構造である有向マトロイドが存在することは明らかであるが， 任意の有向マトロイドを組合せ構造とする幾何構造が常に存在するとは限らない． 有向マトロイドが幾何構造として実現されるとき，その有向マトロイドを実現可能であるといい，そうでない場合を実現不可能であるという．有向マトロイドが実現可能か否かを判定する問題は有向マトロイドの実現可能性問題と呼ばれ，古くから研究されてきた．本問題は1988年にNP-hardであることが示されたが，その一方で実現可能性および実現不可能性を多項式時間で判定できる有向マトロイドの部分クラスが数多く存在することも知られている． 本講演では，有向マトロイドの実現可能性問題に関する既存研究を振り返るとともに， 同問題を半正定値計画緩和することで実現不可能性を判定する最近の研究成果（宮田洋行氏，今井浩教授との共同研究）について紹介する．
講演者：
脇 隼人 氏 （電気通信大学）
タイトル：
半正定値計画緩和に対する多倍長計算の有効性について
概要： 本発表では, ある単純な多項式最適化問題から生じる半正定値計画緩和問題に対して, SeDuMiやSDPAなどの標準的な半正定値計画問題に対するソフトウェアと, 多倍長計算を行う, SDPA-GMPというソフトウェアとの間で生じる奇妙な現象について議論する. もう少し正確に述べると, その例題に対しては, SeDuMiやSDPAで解くと, 出力される最適値が多項式最適化問題の最適値と一致しているのに対して, SDPA-GMPでより正確に計算すると, 出力される最適値は多項式最適化問題の最適値とは全く異なる値になる.
つまり, SeDuMiやSDPAは, 半正定値計画問題の最適値ではない, 間違った値を返しているにもかかわらず, それは多項式最適化問題の最適値と一致しているのである.
本発表では, 例題から導かれる半正定値計画の詳細やなぜこのようなことが起こるのかということについて議論する.
なお, 本発表は電気通信大学の村松正和先生との共同研究である.
ホーム
Copyright, S@CO All rights reserved, 2006-2008.
