離散凸解析の応用開拓の研究
【研究分野】工学基礎
【研究キーワード】
凸解析 / 凸関数 / 凸集合 / マトロイド / 離散最適化 / 数理計画 / 非線形計画 / ネットワークフロー / 離散凸解析 / 数理経済学 / 不可分財市場 / 競争均衡 / M凸関数最小化 / アルゴリズム
【研究成果の概要】
本研究課題の主題,研究代表者が1990年代の中頃から提唱している離散凸解析の応用開拓である.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
(1)数理経済学において,離散凸解析の応用研究として3つの成果を上げた.第1の成果は,複数の不可分財と貨幣からなる市場において競争均衡が存在するための十分条件を与えるなど,理論構築を行なった.第2の成果は,離散凸解析のおいて中心的役割をなすM凸関数の新しい特徴付けを与えた.この特徴付けは,数理経済学では良く知られた粗代替性や単改良性を用いたものである.第3の成果は,先に述べた不可分財と貨幣からなる市場において,競争均衡を求めるアルゴリズムの開発である.このアルゴリズムは,離散凸解析における最適化問題の一つであるM凸劣モジュラ流問題を利用したもので,多項式時間で均衡の存在判定を行ない,均衡が存在する場合はその一つを求める.
(2)離散凸解析において中心的な役割を果たすM凸関数の最小化問題に対する近接定理を示すとともに,高速なアルゴリズムを開発した.
(3)工学システムのもつ組合せ構造を離散凸解析の立場から論じた.特に,電気回路や制御システムの取扱いを目的として,混合多項式行列を考察し,効率的な組合せ緩和アルゴリズムを提案した.
(4)オペレーションズ・リサーチの諸問題に対し,離散凸解析の結果を利用した解法が適用可能か否かを検証した.その結果を踏まえて,ネットワークデザインや最大カット問題に対して効率的な解法を提案した.
【研究代表者】