[動態規劃] 淺談 離散時間動態規劃 (1) - Bellman equation in Infinite Horizon

這次要介紹 無窮時間的 Bellman Equation，亦即我們的 Cost function 為 branch cost 加到無窮大的情況：
$$J(u) := \displaystyle \sum_{k=0}^{\infty} J(x(k), u(k)) + \Phi(x(N))$$
那麼現在問題變成 儘管我們手上有 有限時間的 Bellman Equation (請參考前篇文章)，但對於此類無窮時間的問題該如何處理??

亦即如果今天我們 cost function 的 $N \rightarrow \infty$ 該怎麼處理? 我們稱這一類問題叫做 Steady State Dynamic Programming 或稱 Dynamic Programming in Infinite Horizon。

無窮時間的動態規劃問題 (Dynamic Programming Problem in Infinite Horizon)：

考慮 Performance index (cost function)
$$J(u) := \displaystyle \sum_{k=0}^{\infty} J(x(k), u(k)) + \Phi(x(N))$$ 狀態方程( state equation)
$$x(k+1) = f(x(k), u(k)), \ x(0) \ \text{is given} \\ $$ 其中 $x(k)$ 為系統在第 $k$ 時刻的 狀態，$f:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^n$，
與控制力拘束條件
$$u(k) \in \Omega$$ 其中$\Omega$ 為拘束條件

此時對應的 Bellman Equation (or Dynamic Programming Equation) 寫為如下的 functional form
$$I(x) = \min_{u \in \Omega} \{ J(x,u) + I(f(x,u)) \}$$ 亦即與 $N$ 無關
上式稱為 Steady State Bellman Equation 或者 Bellman Equation in Infinite Horizon。


現在我們看個例子：

Example
考慮系統狀態方程表示如下：
$$x(k+1) = x(k) - u(k)$$ 且 cost function 為
$$J(u) = \displaystyle \sum_{k=0}^{\infty} (x(k+1)-u(k))^2 + x^2(k+1)$$ 試求 Optimal $u^*$ 與其對應的 optimal cost to go

Solution
首先我們寫下 Steady State Bellman Equation:
$$I(x) = \min_{u \in \Omega} \{J(x,u) + I(f(x,u)) \}$$ 現在我們要求解上式，故我們首先猜一個解 (事實上此問題在之前文章中我們解過有限時間的 Bellman equation，當時我們解出 Optimal cost to go 具有 $I(x) = \alpha x^2$ 的形式，有興趣的讀者可前往前篇文章檢驗)，故我們現在很合理的可以猜這 $I(x) = \alpha x^2$ 其中 $\alpha$ 為代定係數 $\alpha \geq 0$。
故我們將此解代入 Steady State Bellman Equation，可得
$$\begin{array}{l} I(x) = {\min _{u \in \Omega }}\{ J(x,u) + I(f(x,u))\} \\  \Rightarrow \alpha {x^2} = {\min _{u \in \Omega }}\{ {(x - u)^2} + {x^2} + \alpha {\left( {x - u} \right)^2}\} \\  \Rightarrow \alpha {x^2} = {\min _{u \in \Omega }}\{ {x^2} + \left( {1 + \alpha } \right){\left( {x - u} \right)^2}\} \end{array}$$ 由 FONC: $\frac{\partial }{{\partial u}} = 0$，我們可求解上式右方最佳控制力 $u^*$ ：
$$u^* = x$$ 故代回上式我們得到
$$\begin{array}{l} \alpha {x^2} = {x^2}\\  \Rightarrow \alpha  = 1 \end{array}$$ 故如果我們選 $\alpha =1$即可解得 Steady-State Bellman Equation。 $\square$

上述問題可以進一步拓展到 $\mathbb{R}^n$ 空間，這一類問題在控制理論中稱為無窮時間的線性二次調節器 (Linear Quadratic Regulator, LQR) 問題，有興趣的讀者請參考：
[最佳控制] 離散時間 穩態線性二次調節器 Discrete Time Linear Quadratic Regulator in Infinite Horizon via Dynamic Programming