18.3.5 贝尔曼泛函方程方法

18.3.5.1 最小费用的确定

基于泛函方程 (18.136),(18.137) 和 (18.138),从 $ϕ_{n + 1} ({\underset{―}{x}}_{n}) = 0$ 开始,每一个值 $ϕ_{j} ({\underset{―}{x}}_{j - 1}) ({\underset{―}{x}}_{j - 1} \in X_{j - 1})$ 按 $j$ 的递减顺序逐个确定. 它要求对于每一 ${\underset{―}{x}}_{j - 1} \in X_{j - 1}$ , 最优问题的解都在决策空间 $U_{j} ({\underset{―}{x}}_{j - 1})$ . 对于每个 ${\underset{―}{x}}_{j - 1}$ ,存在一极小点 ${\underset{―}{u}}_{j} \in U_{j}$ 作为从 ${\underset{―}{x}}_{j - 1}$ 开始的子过程 $P_{j}$ 的第 1 级的最优决策. 如果诸集合 $X_{j}$ 不是有限的或者它们太大,那么可以对于一组所选择的节点 ${\underset{―}{x}}_{j - 1} \in X_{j - 1}$ ,计算相应的 $ϕ_{j}$ 值. 其中间值可以通过某种插值方法进行计算. $ϕ_{1} ({\underset{―}{x}}_{0})$ 是过程 $P$ 的费用函数的最优值. 最优策略 $({\underset{―}{u}}_{1}^{*}, \dots, {\underset{―}{u}}_{n}^{*})$ 以及相应的状态 $({\underset{―}{x}}_{0}^{*}, \dots, {\underset{―}{x}}_{n}^{*})$ 可以采用如下两种方式之一来确定.

18.3.5.2 最优策略的确定

(1) 方式 1 在求解泛函方程中,每次计算 ${\underset{―}{x}}_{j - 1} \in X_{j - 1}$ 也要将计算值 ${\underset{―}{u}}_{j}$ 存储起来. 在计算 $ϕ_{1} ({\underset{―}{x}}_{0})$ 之后,如果从 ${\underset{―}{x}}_{0} = {\underset{―}{x}}_{0}^{*}$ 和所存储的 ${\underset{―}{u}}_{1} = {\underset{―}{u}}_{1}^{*}$ 确定 ${\underset{―}{x}}_{1}^{*} = g_{1} ({\underset{―}{x}}_{0}^{*}, {\underset{―}{u}}_{1}^{*})$ ,就得到最优策略. 从 ${\underset{―}{x}}_{1}^{*}$ 和存起来的 ${\underset{―}{u}}_{2}^{*}$ 得出 ${\underset{―}{x}}_{2}^{*}$ ,等等.

(2) 方式 2 对于每个 ${\underset{―}{x}}_{j - 1} \in X_{j - 1}$ ,仅存储 $ϕ_{j} ({\underset{―}{x}}_{j - 1})$ . 在每次 $ϕ_{j} ({\underset{―}{x}}_{j - 1})$ 知道后,就前向计算一次. 从 $j = 1$ 和 ${\underset{―}{x}}_{0} = {\underset{―}{x}}_{0}^{*}$ 开始,通过计算泛函方程

\begin{matrix} (18.141) & ϕ_{j} ({\underset{―}{x}}_{j - 1}^{*}) = min_{{\underset{―}{u}}_{j} \in U_{j} ({\underset{―}{x}}_{j - 1}^{*})} H_{j} (f_{j} ({\underset{―}{x}}_{j - 1}^{*}, {\underset{―}{u}}_{j}), ϕ_{j + 1} (g_{j} ({\underset{―}{x}}_{j - 1}^{*}, {\underset{―}{u}}_{j}))) \end{matrix}

按 $j$ 的递增顺序逐个确定 ${\underset{―}{u}}_{j}$ . 然后得到 ${\underset{―}{x}}_{j}^{*} = g_{j} ({\underset{―}{x}}_{j - 1}^{*}, {\underset{―}{u}}_{j}^{*})$ . 在前向计算中,每一级都必须求解一个优化问题.

(3) 两种方式的比较 由于是前向计算, 方式 1 计算的代价要小于方式 2 所要求的代价. 然而,由于每一状态 ${\underset{―}{x}}_{j - 1}$ 下都要存储决策 ${\underset{―}{u}}_{j}$ ,从而在高维决策空间 $U_{j} ({\underset{―}{x}}_{j - 1})$ 情形下,这可能需要非常大的存储量,而在方式 2 中,仅需存储 $ϕ_{j} ({\underset{―}{x}}_{j - 1})$ . 因此常常在计算机上使用方式 2.

18.3.5 贝尔曼泛函方程方法 ​

18.3.5.1 最小费用的确定 ​

18.3.5.2 最优策略的确定 ​

18.3.5 贝尔曼泛函方程方法

18.3.5.1 最小费用的确定

18.3.5.2 最优策略的确定