微分動的計画法による非線形計画問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
動的計画法は、大規模数理計画問題のもつ構造を利用した解法の1つであるが、従来の動的計画法では、制約条件式が3以上の問題を解くことはほぼ不可能であった。本論文では、可分問題等を含むかなり一般的な大規模数理計画問題にたいして、制約条件式の多少にかかわらず有効な微分動的計画法による了ルゴリズムを提案し、その収束性を証明するとともに、数値例によりその有効性を示す。取り扱かう問題伐制約条件式g^j(x_1、…、x_n)≦0(j=1、…、m)h^j_n(x_n)≦0(j=1、…、m_n、n=1、…、N)のもとで目的関数f(x_1、…、x_n)を最小にする問題である。ここで、x_nはk_n次元ベクトルである。まず、この非線形計画問題ぬ)が、fとg^jに関するかなり一般的な条件のもとで、動的計画法により1変数x_nにたいするN個の部分問題に分解されることが示される。次いで、各部分問題にたいするキューノン・タッカー条件および微分可能性が論じられ、連立非線形方程式を解く逐次手法を用いて微分動的計画法のアルゴリズムが構成される。本了ルゴリズムが、通常の逐次手法にたいして、少なくともR一線形収束し、特にニュートン法にたいしてR-2乗取東することが、差分方程式系の一様漸近安定性を用いて証明される。また、本アルゴリズムの計算時間が、Nに関して線形にしか増加しないことが示される。さらに、本了ルゴリズムを一部修正したアルゴリズムが収束率を低下させることなく、より広い収束域をもつことが示される。最後に数値例として、3変数1制約問題、4変数3制約問題(ローゼン・鈴木問題)、30変数3制約問題が解かれ、提案した微分動的計画法のアルゴリズムがかなり広い収束域をもち、大規模数理計画問題を短時問に解きうる手法であることが示される。
著者
関連論文
- 微分動的計画法による非線形計画問題の解法
- 有限の待ち合い室を有するGI/G/1待ち行列システムに対する拡散近似 : II-定常状態における挙動
- 有限の待ち合い室を有するGI/G/I待ち行列システムに対する拡散近似 : I-ファーストオーバーフロー・タイム
- 0Rの旗を掲げよう(これからのOR) : 座談会
- 特集に当って(確率システム)
- 割引のあるセミ・マルコフ決定過程における非最適政策の除去法を併用するアルゴリズムについて