1957 - Bellman 動態規劃#
案件摘要#
1957 年，Richard Bellman（貝爾曼）在 RAND 公司出版《Dynamic Programming》 （動態規劃），提出最佳性原理（principle of optimality）與Bellman 方程： 多階段決策問題可以拆解成一系列單階段問題—— 「最佳路徑的任何子路徑也是最佳的」。最佳控制問題從「解一條最佳軌跡」 變成「解一個回溯函數」（值函數 \(V(x, t)\) ）——與 Pontryagin 最大值原理 （見 1956-Pontryagin最大值原理.md）互補的第二條最佳化路線誕生。
前因#
- RAND 公司的冷戰任務：軍事後勤、飛彈排程、多階段決策——「如何在資源有限下排程」是國防級問題。
- 多階段決策的組合爆炸： \(n\) 階段、每階段 \(m\) 個選擇，暴力枚舉是 \(m^n\) ——指數爆炸，計算機算不動。
- Pontryagin 最大值原理（1956）：變分法路線（必要條件），但不提供全域解與數值算法。
- Bellman 的職業病：他在 RAND 處理的是離散的多階段問題——不適合變分法（連續工具），需要新的數學。
線索與推理#
第 1 步：最佳性原理#
Bellman 的偵探手法：從「最佳路徑的性質」反推。最佳性原理：
最佳路徑的任何後段子路徑，也是（從該子起點出發的）最佳路徑。
直觀：如果從 A 到 C 的最佳路徑經過 B，那它的 B→C 段就是「從 B 到 C 的最佳路徑」—— 否則換一條更短的 B→C，原路徑就不是最佳了。矛盾。所以子路徑必最佳。
第 2 步：Bellman 方程#
定義值函數 \(V(x, t)\) ：從狀態 \(x\) 、時間 \(t\) 出發，到終點的最佳代價。最佳性原理給出回溯關係：
連續時間極限（Taylor 展開 \(V(x + f\Delta t, t + \Delta t) \approx V + V_t \Delta t + V_x f \Delta t\) ）：
右邊正是 Hamiltonian 的最小值： \(\min_u \mathcal{H}(x, V_x, u, t)\) 。所以：
這是Hamilton–Jacobi–Bellman（HJB）方程——與哈密頓物理學的 HJ 方程 （見 1837-HamiltonJacobi方程.md、 哈密頓物理學教材 04.2-正則變換與HamiltonJacobi方程.md） 完全同構：值函數 \(V\) 對應作用量 \(S\) 、 \(V_x\) 對應動量 \(p\) ！
第 3 步：組合爆炸的解法#
動態規劃把指數複雜度降到多項式：
| 方法 | 複雜度 | 原理 |
|---|---|---|
| 暴力枚舉 | \(O(m^n)\) | 枚舉所有路徑 |
| 動態規劃 | $O(n \cdot m \cdot | X |
關鍵：值函數的「存表重用」（memoization）——子問題只解一次。 這是「用空間換時間」的演算法思想，與程式設計的動態規劃是同一套數學。
第 4 步：與最大值原理的對比#
| 面向 | Pontryagin 最大值原理 | Bellman 動態規劃 |
|---|---|---|
| 性質 | 必要條件 | 充分條件（若 \(V\) 可解） |
| 形式 | 局部（沿軌跡的 ODE） | 全域（值函數的 PDE） |
| 控制約束 | 直接處理（邊界也成立） | 直接處理（ \(\min_u\) 內建） |
| 數值求解 | 打靶法、間接法 | 網格法、值迭代 |
| 維度災難 | 無（ODE） | 有（PDE，維度指數增長） |
| 隨機推廣 | 困難 | 自然（隨機 HJB、馬爾可夫決策過程） |
互補性：確定性低維問題用最大值原理；隨機或離散問題用動態規劃。 維度災難（curse of dimensionality，Bellman 自己命名）是動態規劃的致命傷—— 這也是五十年後強化學習（用函數逼近代替查表）誕生的伏筆 （見 2015-強化學習控制.md）。
後果#
- 最佳控制理論的兩大支柱成形：最大值原理 + 動態規劃。
- LQR（線性二次調節器）：Kalman 用動態規劃解出 LQR 的 Riccati 方程（見 1960-Kalman狀態空間與濾波.md）。
- 馬爾可夫決策過程（MDP）：動態規劃的隨機版，成為強化學習的數學基礎。
- 「維度災難」的命名提醒了後世：值函數查表不可擴展——函數逼近（神經網路）是出路。
結案陳詞#
Bellman 的偵探手法是「拆解時間」：多階段決策的指數爆炸，被最佳性原理 拆成一系列可重用的子問題。HJB 方程與哈密頓–雅可比方程的同構—— 作用量 \(S\) 回來了，最佳控制是變分法的離散版。值函數、維度災難、 馬爾可夫決策過程——動態規劃的遺產貫穿到今日的強化學習。