平成11年度2月 最適化とアルゴリズム研究部会
- 日時:2月19日(土) 14:00 〜 17:30
- 場所:上智大学10号館3階第322号室
- 発表1:室田 一雄 氏(京都大学 数理解析研究所)
- 「経済均衡論における離散凸性」
-
最近5年間,離散最適化の分野では離散凸関数の理論が「離散凸解析」
の名の下に急速に進展した.これは,整数格子点の上で定義された関数
に対する凸性とは何かを研究する
分野であり,その中心概念は,M凸関数とL凸関数の概念である.
本セミナーにおいては,不可分財(indivisible goods)をもつ経済の均衡の
存在に関する Henry (1970), Quinzii (1984), Svensson (1984)
などの結果が,M#凹関数を効用関数,M#凸関数を生産費用関数とする枠組みで
統一的に説明できることを説明する(Danilov, Koshevoyとの共同研究結果).
さらに,その枠組みでは,均衡価格がL#凸集合を成す
(したがって,束構造をもつ)ことを新たに指摘する.
参考文献
室田一雄: 離散凸解析,「離散構造とアルゴリズムV」(藤重悟 編),
近代科学社, 第2章, pp. 51-100, 1998.
また,http://www.kurims.kyoto-u.ac.jp/~murota
の My Books のところをご覧下さい.
- 発表2:高畑 貴志 氏 (東京大学 広域科学専攻)
- 「不均衡な交換を考慮した劣モジュラ多面体の拡張」
-
マトロイド等の組合せ構造は, 劣モジュラ集合関数を通じて定義される
劣モジュラ多面体に拡張されてきた. 劣モジュラ多面体は, マトロイドに
由来する1対1交換可能性を持つため, 多面体上での線形関数の最大化が,
ある種の greedy アルゴリズムで達成されるという性質を持つ.
本研究では, 不均衡な交換可能性しか持たず, しかも「マトロイド的」
な多面体として, 非負ベクトル上の劣モジュラ関数を通じて定義される,
多面体のクラスを提案する. 多面体の持つ交換可能性および面構造の特徴
を紹介し, これらの性質を利用した, 最適化アルゴリズムを提示する.
拡張された多面体の適用例として, 増幅付きネットワーク流を取り挙げる.
(東京大学 柏原賢二氏との共同研究)
SOA Home Page へ.