ベルマン方程式

ウィキペディア

ベルマン方程式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 02:36 UTC 版)

ベルマン方程式のフローチャート

ベルマン方程式（ベルマンほうていしき、英: Bellman equation）は、動的計画法（dynamic programming）として知られる数学的最適化において、最適性の必要条件を表す方程式であり、発見者のリチャード・ベルマンにちなんで命名された。動的計画方程式（dynamic programming equation）とも呼ばれる。ベルマン方程式は、決定問題（decision problem）において、ある時刻の初期選択と、それ以降の決定問題の価値との関係を記述する。これにより、動的な最適化問題を、ベルマンの最適性の原理が示す指針にしたがって、より単純な部分問題（subproblems）に分解するのである。

ベルマン方程式は最初、制御工学や他の応用数学上の問題に適用され、その後、経済理論（economic theory）における重要なツールとなった。しかしながら、動的計画法の基本概念はもともとジョン・フォン・ノイマンとオスカー・モルゲンシュテルンのゲーム理論と経済活動やエイブラハム・ウォールドの 時系列解析（sequential analysis) の研究の中で次第に形作られてきたものである。

最適制御理論で解かれるほとんどの問題は、適切なベルマン方程式を用いて解くことができる。ただし、一般に「ベルマン方程式」という用語は離散時間の最適化問題を解く際に用いられる動的計画法の方程式を指す。 連続時間の最適化問題を解く場合には、ベルマン方程式の連続時間形式である偏微分方程式を用い、これをハミルトン-ヤコビ-ベルマン方程式と呼ぶ。

動的計画法の考え方

ベルマン方程式を理解するには、いくつかの背景となる概念を理解しなくてはならない。第一に、最適化問題は何らかの目標を持つ。具体例を挙げれば、移動時間を最短にする、コストを最小に抑える、利益を最大化する、効用を最大化する、などである。これらの目標を数学の関数で表現したものを目的関数（objective function）と呼ぶ。

動的計画法は複数段階にわたる計画問題を、各時点の簡単な手順へと分解する。そのため、ある時点でなされた決定がそれ以降どのように影響を及ぼすか正しく記述しなくてはならない。正しい判断を下すために必要な現在の状況を示す情報を状態（state）と呼ぶ。例えば、人がある時点で何をどれだけ消費するか決めるには、（何よりもまず）現在の富（資産額）を知らなくてはならない。 そのゆえ、富は、経済活動を行う人が持つ状態変数の一つと考えられる。言うまでもなく、このような状態変数は他にも存在する。

任意の時点で選ぶことのできる変数を通常制御変数（control variables）と呼ぶ。例えば、人々は与えられた富のもとで、どれだけ消費すべきか判断する。制御変数を選ぶことは、次の状態を選択することでもある。ただし、一般に次の状態は制御変数だけではなく他の要因によっても影響を受ける。具体例で示そう。最も単純には、今日の富（状態）と消費（制御変数）によって明日の富（次の状態）が決まる。だが、多くの場合、明日の富には別の要因（例：予期せぬボーナス、天災など）も影響するであろう。

動的計画法は、与えられたどんな状態に対しても、適切な制御の指針を与えるような最適な計画を記述する。一例として、消費 $c$