[動態規劃] 淺談 離散時間動態規劃 (0) - Principle of Optimality & Bellman equation in Finite Horzion

這次要跟大家介紹離散時間的動態規劃 (Dynamic Programming, D.P.) 問題：
此為最佳化理論中的一種方法，由 Professor Bellman 的 Principle of Optimality 所奠基。

基本想法如下： 從最佳解往回推 (backward)，逐步求解最佳值。再從初始位置沿著以求得的最佳路徑前進到最佳解。

我們現在把動態規劃問題寫下：

(有限時間) 動態規劃問題 (Dynamic Programming Problem in Finite Horizon)：

考慮 Performance index (cost function)
\[
J(u) := \displaystyle \sum_{k=0}^{N-1} 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) \in \mathbb{R}^n$ 為系統在第 $k$ 時刻的 狀態，$u(k) \in \mathbb{R}^m$ 為控制力，函數 $f:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^n$，

另外我們仍需考慮控制力拘束條件
\[
u(k) \in \Omega_k(x(k))
\]其中 $\Omega_k$ 為第 $k$ 時刻的拘束條件

Comment:
1. 關於狀態方程：上式中的 $f(x(k),u(k))$ 稱作 autonomous state equation
但事實上DP問題亦可直接考慮 Non-autonomous state equation，(亦即函數中考慮時間 $k$)
\[
f((x(k), u(k), k))
\] Example: Autonomous and Non-autonomous system
Autonomous state equation:  $x(k+1) = x(k) + u(k)$
Non-autonomous state equation: $x(k+1) = k \cdot x(k)$

2. 關於 Performance Index
\[
J(u) := \displaystyle \sum_{k=0}^{N-1} J(x(k), u(k)) + \Psi (x(N))
\] 其中 $J(x(k), u(k))$ 稱為 Branch cost。 $\Psi (x(N))$ 稱為 Terminal cost。


現在我們介紹 Bellman's Principle of Optimality

==========================
Principle of Optimality
假設我們有一組 optimal sequence
\[
u^*(0), u^*(1), ..., u^*(N-1)
\]令 $x^*(0), x^*(1), ..., x^*(N)$ 為 induced states，亦即對 $k=0,1,...,N-1$
\[
u(k) \in \Omega_k(x^*(k))
\]且 $x^*(k+1) = f(x^*(k),u^*(k))$  (也就是說上述的 optimal sequence 最佳化整個問題。)
那麼現在考慮一個 子問題 (subproblem)：
考慮 $k = l$ (現在考慮由 時刻 $l$ 開始 (不是從 $0$ 開始) )，初始狀態現在為 $x(l)=x^*(l)$ (亦即此時的初始狀態 $x(l)$ 落在最佳解上 $x^*(l)$)，此時對應的 Cost function 為
\[
J_l(u) := \displaystyle \sum_{k=l}^{N-1} J(x(k), u(k)) + \Psi (x(N))
\]則 Principle of Optimality 告訴我們
\[
u^*(l), u^*(l+1), ..., u^*(N-1)
\]為對此 subproblem 的 optimal sequence.
==========================
Comment:
上述的 Principle of Optimality 其實表達的想法很簡單，就是如果已有一組最佳解序列在手，那麼從任意時刻開始的解也必須是最佳解。比如說我有一組最佳控制力序列
$u^*(0), u^*(1), ..., u^*(10)$ 那麼考慮從 $k=5, 6,...10$ 的子問題，則對應的控制力序列
\[
u^*(5), u^*(6),...u^*(10)
\]亦為此子問題的最佳解。

或者更淺白的說，假設今天要坐飛機到美國，最佳航程為

台灣 => 香港 =>美國

如果今天如果不從台灣開始，而是從香港開始(且香港已經在最佳路徑上)，則到美國的這條路徑仍維持最佳解。(香港=>美國)


Proof: Bellman's Principle of Optimality

用矛盾證法 (Proof by contradiciton)，
考慮一 子問題(subproblem) 為 從狀態 $x^*(l)$ 開始，且此狀態落在最佳解上，但 $u^*(k), \ k=l,l+1,...,N-1$ 並非 Optimal sequence。

既然上述不是 subproblem 的 Optimal sequence，則必定有其他人比此 $u^*$ 這組 sequence 可以得到更低的 cost，也就是說存在一組
\[
\hat{u}(l), \hat{u}(l+1),... \hat{u}(N-1)
\]使得 $J_l(\hat{u}) < J_l (u^*)$

現在我們定義 Optimal sequence: $\tilde{u}(k)$
\[\tilde u(k): = \left\{ \begin{array}{l}
{u^*}\left( k \right),\begin{array}{*{20}{c}}
{}
\end{array}k < l\\
\hat u\left( k \right),\begin{array}{*{20}{c}}
{}
\end{array}l \le k \le N - 1
\end{array} \right.
\] 那麼我們現在觀察 整個最佳化問題 (非子問題 ) 的 cost；亦即對 $k=0$ 開始 (而非 $k=l$)，則我們有
\[\begin{array}{l}
J\left( {\tilde u} \right) = \sum\limits_{k = 0}^{N - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)}  + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) = \underbrace {\sum\limits_{k = 0}^{l - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)} }_{{J_0}\left( {{u^*}} \right)} + \underbrace {\sum\limits_{k = l}^{N - 1} {J\left( {x\left( k \right),u\left( k \right)} \right)} }_{{J_l}\left( {\hat u} \right)} + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) < {J_0}\left( {{u^*}} \right) + {J_l}\left( {{u^*}} \right) + \Psi \left( {x\left( N \right)} \right)\\
 \Rightarrow J\left( {\tilde u} \right) < J\left( {{u^*}} \right)
\end{array}
\] 上述結果說明 $\tilde{u}$ 的序列為 Optimal sequence，但此結果與 Principle of Optimality 中原本假設的 最佳序列 $u^*(0), u^*(1),..., u^*(N-1)$ 矛盾。故得證。 $\square$

有了上述的 Principle of Optimality，我們便可以建構 Dynamic Programming Equaiton (DPE) (DPE 又稱為 Bellman equation)


Bellman Equation
首先考慮我們的 Subproblem：
由初始狀態 $x(l)$，定義 Optimal cost-to-go 記作 $I(x(l), N-l)$ (亦即考慮 Subproblem 由 $x(l)$ 開始 到 $x(N)$ 的 optimal cost )
\[I(x(l),N - l): = \mathop {\min }\limits_{\scriptstyle u(k) \in {\Omega _k},\atop
\scriptstyle k \ge l} {J_l}\left( u \right)
\]由 $J_l(u)$ 定義可知，${J_l}(u): = \sum\limits_{k = l}^{N - 1} J (x(k),u(k)) + \Psi (x(N))$，故
\[
\begin{array}{l}
I(x(l),N - l): = \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k \ge l}
\end{array}} \left[ {\sum\limits_{k = l}^{N - 1} J (x(k),u(k)) + \Psi (x(N))} \right]\\
 \Rightarrow I(x(l),N - l) = \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k \ge l}
\end{array}} \left[ \begin{array}{l}
J(x(l),u(l))\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \sum\limits_{k = l + 1}^{N - 1} {J(x(k),u(k))}  + \Psi (x(N))
\end{array} \right]
\end{array}
\]由 Principle of Optimality 可知，上式可改寫為
\[
\small{\begin{array}{l}
 \Rightarrow I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ \begin{array}{l}
J(x(l),u(l))\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \mathop {\min }\limits_{\begin{array}{*{20}{c}}
{u(k) \in {\Omega _k},}\\
{k > l}
\end{array}} \left\{ {\sum\limits_{k = l + 1}^{N - 1} {J(x(k),u(k))}  + \Psi (x(N))} \right\}
\end{array} \right]\\
 \Rightarrow I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]
\end{array}}
\]
上式稱為 Bellman Equation 或稱 Dynamic Programming Equation
\[
I(x(l), N-l) = \min_{u(l) \in \Omega_l} \{J(x(l), u(l)) + I(x(l+1), N-(l+1)) \}
\]

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

Solution
為簡便起見，這邊只求 $u(N-1)$ 與其對應的 optimal cost to go。

故首先由 $x(N-1)$ 開始，亦即 $l= N-1$，由 DPE 可知
\[\begin{array}{l}
I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(N - 1),u(N - 1)) + I\left( {x(N),0} \right)} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {{{\left[ {x(N) - u(N - 1)} \right]}^2} + {x^2}\left( N \right) + {\rm{0}}} \right]\\
 \Rightarrow I(x(N - 1),1) = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {{{\left[ {x(N) - u(N - 1)} \right]}^2} + {x^2}\left( N \right)} \right]
\end{array}
\]現在再由系統狀態方程 $x\left( N \right) = x(N - 1) - u(N - 1) $ 代入上式可得
\[I(x(N - 1),1) = \mathop {\min }\limits_{u(N - 1)} \left[ {{{\left[ {x(N - 1) - 2u(N - 1)} \right]}^2} + {{\left[ {x(N - 1) - u(N - 1)} \right]}^2}} \right]
\] 由 FONC 求最佳解：
\[\begin{array}{l}
\frac{{\partial I(x(N - 1),1)}}{{\partial u(N - 1)}} = 0 \\
 \Rightarrow {u^*}(N - 1) = \frac{3}{5}x(N - 1)
\end{array}
\]其對應的Optimal cost-to-go
\[\begin{array}{l}
 \Rightarrow {\left. {I(x(N - 1),1)} \right|_{{u^*}}} = {\left[ {x(N - 1) - 2\frac{3}{5}x(N - 1)} \right]^2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} + {\left[ {x(N - 1) - \frac{3}{5}x(N - 1)} \right]^2}\\
 \Rightarrow {\left. {I(x(N - 1),1)} \right|_{{u^*}}} = \underbrace {\frac{1}{5}}_{{K_{N - 1}}}{x^2}(N - 1)
\end{array}
\] 上式子中的 $K_{N-1}$ 被稱作 feedback-gain at $N-1$ stage。

接著我們計算 $x(N-2)$ 亦即 $l=N-2$ 的 Optimal cost-to-go:
\[\begin{array}{*{20}{l}}
{I(x(l),N - l): = \mathop {\min }\limits_{u(k) \in {\Omega _k}} \left[ {J(x(l),u(l)) + I\left( {x(l + 1),N - \left( {l + 1} \right)} \right)} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2) \in {\Omega _{N - 2}}} \left[ {J(x(N - 2),u(N - 2)) + I\left( {x(N - 1),1} \right)} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2)} \left[ \begin{array}{l}
{\left( {x\left( {N - 1} \right) - u\left( {N - 2} \right)} \right)^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + {x^2}\left( {N - 1} \right) + \frac{1}{5}{x^2}\left( {N - 1} \right)
\end{array} \right]}\\
{ \Rightarrow I(x(N - 2),2) = \mathop {\min }\limits_{u(N - 2)} \left[ \begin{array}{l}
{\left( {x\left( {N - 2} \right) - 2u\left( {N - 2} \right)} \right)^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + {\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]^2}\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \frac{1}{5}{\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]^2}
\end{array} \right]}
\end{array}
\] 由FONC: $\frac{\partial }{{\partial u(N - 2)}} = 0$，可知
\[\begin{array}{l}
\left\{ \begin{array}{l}
 - 4\left( {x\left( {N - 2} \right) - 2u\left( {N - 2} \right)} \right)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} - 2\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right] - \frac{2}{5}\left[ {x\left( {N - 2} \right) - u\left( {N - 2} \right)} \right]
\end{array} \right\} = 0\\
 \Rightarrow {u^*}\left( {N - 2} \right) = \frac{8}{{13}}x\left( {N - 2} \right)
\end{array}
\] 將上式代回 $I(x(N-2),2)$ 可得對應的 Optimal Cost to go 為
\[\begin{array}{l}
I(x(N - 2),2) = \left[ {\frac{9}{{{{13}^2}}}{x^2}\left( {N - 2} \right) + \frac{{25}}{{{{13}^2}}}{x^2}\left( {N - 2} \right) + \frac{5}{{{{13}^2}}}{x^2}\left( {N - 2} \right)} \right]\\
 \Rightarrow I(x(N - 2),2) = \frac{{39}}{{{{13}^2}}}{x^2}\left( {N - 2} \right)
\end{array}
\] $\square$

延伸閱讀：
[動態規劃] 淺談 離散時間動態規劃 (1) - Bellman equation in Infinite Horzion