18.3.3 贝尔曼泛函方程

18.3.3.1 费用函数的性质

为了叙述贝尔曼泛函方程, 费用函数必须满足两个性质.

1. 可分性

函数 $f (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))$ 称作可分的,是指它可以由双参函数 $H_{1}, \dots, H_{n - 1}$ 以及函数 $F_{1}, \dots, F_{n}$ 按如下方式给出:

f (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))

= F_{1} (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n})),

F_{1} (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))

= H_{1} (f_{1} ({\underset{―}{x}}_{0}, {\underset{―}{u}}_{1}), F_{2} (f_{2} ({\underset{―}{x}}_{1}, {\underset{―}{u}}_{2}) \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))),

......

F_{n - 1} (f_{n - 1} ({\underset{―}{x}}_{n - 2}, {\underset{―}{u}}_{n - 1}), f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))

= H_{n - 1} (f_{n - 1} ({\underset{―}{x}}_{n - 2}, {\underset{―}{u}}_{n - 1}), F_{n} (f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))),

\begin{matrix} (18.130) & F_{n} (f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n})) = f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}) . \end{matrix}

2. 极小可交换性

函数 $H (\tilde{f} (\underset{―}{a}), \tilde{F} (\underset{―}{b}))$ 称作极小可交换的,是指它满足

\begin{matrix} (18.131) & min_{(\underset{―}{a}, \underset{―}{b}) \in A \times B} H (\tilde{f} (\underset{―}{a}), \tilde{F} (\underset{―}{b})) = min_{\underset{―}{a} \in A} H (\tilde{f} (\underset{―}{a}), min_{\underset{―}{b} \in B} \tilde{F} (\underset{―}{b})) . \end{matrix}

例如,如果 $H$ 对于每个 $\underset{―}{a} \in A$ 相对于第二变元是单调递增的,即若对于每个 $\underset{―}{a} \in A$ ,

\begin{matrix} (18.132) & H (\tilde{f} (\underset{―}{a}), \tilde{F} ({\underset{―}{b}}_{1})) \leq H (\tilde{f} (\underset{―}{a}), \tilde{F} ({\underset{―}{b}}_{2})), 若 \tilde{F} ({\underset{―}{b}}_{1}) \leq \tilde{F} ({\underset{―}{b}}_{2}), \end{matrix}

则上述可交换性就满足. 现在对于动态规划问题的费用函数,则要求满足 $f$ 的可分性以及所有函数 $H_{j}, j = 1 (1) n - 1$ 的极小可交换性. 以下经常出现的费用函数类型就满足这两种要求:

\begin{matrix} (18.133) & f^{sum} = \sum_{j = 1}^{n} f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}),或者 f^{max} = max_{j = 1 (1) n} f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}), \end{matrix}

而函数 $H_{j}$ 分别是

\begin{matrix} (18.134) & H_{j}^{sum} = f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}) + \sum_{k = j + 1}^{n} f_{k} ({\underset{―}{x}}_{k - 1}, {\underset{―}{u}}_{k}), \end{matrix}

以及

\begin{matrix} (18.135) & H_{j}^{max} = max {f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}), max_{k = j + 1 (1) n} f_{k} ({\underset{―}{x}}_{k - 1}, {\underset{―}{u}}_{k})} . \end{matrix}

18.3.3.2 列出泛函方程

首先定义如下函数:

ϕ_{j} ({\underset{―}{x}}_{j - 1}) = min_{\begin{matrix} {\underset{―}{u}}_{k} \in U_{k} ({\underset{―}{x}}_{k - 1}) \\ k = j (1) n \end{matrix}} F_{j} (f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}),

\begin{matrix} (18.136) & \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n})), j = 1 (1) n, \end{matrix}

\begin{matrix} (18.137) & ϕ_{n + 1} ({\underset{―}{x}}_{n}) = 0. \end{matrix}

如果没有策略 $({\underset{―}{u}}_{1}, \dots, {\underset{―}{u}}_{n})$ 能驱动状态 ${\underset{―}{x}}_{j - 1}$ 到末状态 ${\underset{―}{x}}_{e} \in X_{e}$ ,则我们置 $ϕ_{j} ({\underset{―}{x}}_{j - 1}) = \infty$ . 使用可分性以及对于 $j = 1 (1) n$ 的极小可交换性和动态约束条件, 我们得到

ϕ_{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}),

min_{\begin{matrix} {\underset{―}{u}}_{k} \in U_{k} ({\underset{―}{x}}_{k - 1}) \\ k = j + 1 (1) n \end{matrix}} F_{j + 1} (f_{j + 1} ({\underset{―}{x}}_{j}, {\underset{―}{u}}_{j + 1}), \dots, f_{n} ({\underset{―}{x}}_{n - 1}, {\underset{―}{u}}_{n}))),

= min_{{\underset{―}{u}}_{j} \in U_{j} ({\underset{―}{x}}_{j - 1})} H_{j} (f_{j} ({\underset{―}{x}}_{j - 1}, {\underset{―}{u}}_{j}), ϕ_{j + 1} ({\underset{―}{x}}_{j})),

\begin{matrix} (18.138) & ϕ_{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}

方程 (18.138),(18.136) 和 (18.137) 称作贝尔曼泛函方程. $ϕ_{1} ({\underset{―}{x}}_{0})$ 是费用函数的最优值.

18.3.3 贝尔曼泛函方程 ​

18.3.3.1 费用函数的性质 ​

1. 可分性 ​

2. 极小可交换性 ​

18.3.3.2 列出泛函方程 ​

18.3.3 贝尔曼泛函方程

18.3.3.1 费用函数的性质

1. 可分性

2. 极小可交换性

18.3.3.2 列出泛函方程