成果

数理情報第2研究室
(定兼 邦彦教授,平井 広志准教授)

離散凸解析:

ネットワークなどの離散構造の上に定義された関数の性質を,凸解析と組合せ論の両方の視点から考察するのが「離散凸解析」の主題です.標語的には

「離散凸解析 = マトロイド理論+凸解析」

です.離散凸解析においては,M凸性とL凸性が共役関係にあり,この共役性は

1.非線形抵抗から成る電気回路における電流と電位の関係,
2.ポテンシャル問題における微分作用素とGreen関数の関係,
3.数理経済学においては財と価格の関係

などを抽象化したものとなっています.詳しくは,拙著:

・室田一雄: 離散凸解析の考えかた,共立出版,2007,
・室田一雄: 離散凸解析,共立叢書 現代数学の潮流,共立出版,2001,
・Kazuo Murota: Discrete Convex Analysis, SIAM, 2003.

をご覧下さい.

群論的分岐理論の工学的応用:

自然界にはいろいろなパターンの形成が観察されますが,それらの多くは,非線形方程式系の解の分岐に伴う対称性の変化として数学的には理解されます.これが,いわゆる「群論的分岐理論」であり,その骨格は既に80年代に確立されています.

本研究では,土木工学や構造工学などの分野においても「群論的分岐理論」の視点が有用であることを明かにしました.例えば,材料の強度試験などの状況では,実験誤差(供試体の初期不整など)の下で分岐現象が生じますが,このことを念頭において,「群論的分岐理論」に確率統計的手法を加味して,理論的に健全で実際に即した実験データ解析法を提案しています.詳細は,拙著:

K. Ikeda and K. Murota: Imperfect Bifurcation in Structures and Materials: Engineering Use of Group-Theoretic Bifurcation Theory, Applied Mathematical Sciences 149, Springer-Verlag, 2002.

をご覧下さい.

列挙アルゴリズムの開発:

人工知能やデータマイニングなどの分野には様々な列挙問題が現れる.例えば,「秋刀魚を買う人は,大根も一緒に買う」.消費者ニーズをよく現している言葉だが,そこに「秋刀魚を安売りするときは,大根は通常の値段で売る」という情報が加わると,スーパーマーケットにとって 重要な経営情報になる.消費者の購買意欲をズバリ知りたいが,それは無理だから,「この商品とこの商品を一緒に並べておくと,買う人が多い」というような多くの組合せリストを用意しておき、その中から企業は,最大の利益を上げられる「解」を見いだそうとする.この可能な組合せを求めることを「列挙」という.

本研究では,列挙問題の理論とアルゴリズムの研究を行っている.例えば,

・T. Eiter, K. Makino, On Computing all Abductive Explanations, AAAI-2002, Edmonton (Canada), 62-67, 2002.
・T. Eiter, K. Makino, and G. Gottlob, Computational Aspects of Monotone Dualization: A Brief Survey, INFSYS RR-1843-06-01, Institut fur Informationssysteme, TU Wien, Austria, January 2006.

をご覧ください.