非決定性動的計画法の研究とその制御差分方程式への応用

点击翻译按钮获取中文摘要

本平成17年度は全3年計画の最終年度に当たり、本研究のまとめと総括の年度である。本研究では確定的・確率的動的計画法(deterministic and stochastic dynamic programming)にとって代わり得る新たな動的計画法として非決定性動的計画法(non-deterministic dynamic programming)を導入しようとしている。この目的は概ね達成され、非決定性動的計画法の位置づけが明らかになり、さらに確定的動的計画法および確率的動的計画法に見られない新しい動的最適化問題群が明瞭に浮き彫りにされた。具体的にはコンピュータサイエンス分野での人工知能の設計において極めてよく用いられていることが判明した。また、離散的な数理パズルや数学的なゲームにおいてもいくつか興味ある問題が非決定性動的計画法で解かれることも分かった。その他に、確率論とその応用でよく用いられている停止時刻(stopping time)の概念を離散グラフや木の上に導入して、具体的な動的最適化問題に対して非決定性動的計画法で最適時刻(パターン)を構成した。これは数理ファイナンスにおけるアメリカンオプションをはじめとする満期日変動型オプションの再帰的価格付けを可能にした。この過程で有限段の最適停止問題において停止規則の総数の列挙も再帰的に示せ、その全体をグラフなどで具体的に分かり易く表示した。これにより、ややもするすると陥りがちな解の存在などの数学的な議論から抜け出して、最適停止問題の広域化、簡便化、親しみやすさへと繋がって行った。この研究によって停止時刻、情報集合など確率論特有の概念が非決定性システム上で構築でき、確率(probability)に替わって広く加重(weight)を用いた最適化が可能になった.また、いわゆる差分方程式の概念に最大化演算をもちいて複数個の差分方程式を制御するシステムを導入した。これによって制御差分方程式が具体的な形で表され、最適化を含まない(評価型)動的計画法によって解かれることが判明した。非決定性動的計画法と制御差分方程式に関するこれらの成果は国内は勿論、2003年EURO/INFORMS、ISMP18,2004年KES, ICOTA6,IWIF1および2005年IFORS17などの国際会議で発表し、日本発のオリジナルな研究であることが認知されるようになった。