[最佳控制] Optimizing Multistage Functions - Forward/Backward Dynamic Programming

Life can only be understood going backwards, but it must be lived going forwards. --- Kierkegaard.

考慮一組變數 $w,x,y,z$ 且我們希望最佳化下列的成本函數
\[
f(w,x) + g(x,y) + h(y,z)
\]讀者可已注意到上述的成本函數中有特殊的結構，亦即每一項只有兩個變數。

Backward Dynamic Programming
若我們考慮 $w$ 固定，則上述最佳化問題
\[
\min_{x,y,z} f(w,x) + g(x,y) + h(y,z)
\]可以改寫為 分別最佳化的子問題
\[\mathop {\min }\limits_x \left[ {f(w,x) + \mathop {\min }\limits_y \left[ {g(x,y) + \mathop {\min }\limits_z h(y,z)} \right]} \right]\]故我們可以先解最內部的最佳化問題並得到對應的最佳解 $z^*$ 與 最佳解對應的成本值 $h^*$
\[\left\{ \begin{array}{l}
\mathop {\min }\limits_z h(y,z): = {h^*}\left( y \right)\\
\arg \mathop {\min }\limits_z h(y,z): = {z^*}\left( y \right)
\end{array} \right.\]接著我們求解第二部分的 最佳化的子問題
\[\mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]\]其對應的解
\[\left\{ \begin{array}{l}
\mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]: = {g^*}\left( x \right)\\
\arg \mathop {\min }\limits_y \left[ {g(x,y) + {h^*}\left( y \right)} \right]: = {y^*}\left( x \right)
\end{array} \right.\]最後我們求解 最後一部分的 最佳化子問題
\[\mathop {\min }\limits_x \left[ {f(w,x) + {g^*}\left( x \right)} \right]\]其對應的最佳解
\[\left\{ \begin{array}{l}
\mathop {\min }\limits_x \left[ {f(w,x) + {g^*}\left( x \right)} \right]: = {f^*}\left( w \right)\\
\mathop {\arg \min }\limits_x \left[ {f(w,x) + {g^*}\left( x \right)} \right]: = {x^*}\left( w \right)
\end{array} \right.\]

Forward Dynamic Programming
若我們改考慮 $z$ 固定，則上述最佳化問題
\[
\min_{x,y,z} f(w,x) + g(x,y) + h(y,z)
\]可以改寫為 分別最佳化的子問題，下列形式稱為 Forward Dynamic Programming
\[\mathop {\min }\limits_y \left[ {h(y,z) + \mathop {\min }\limits_x \left[ {g\left( {x,y} \right) + \mathop {\min }\limits_w f\left( {w,x} \right)} \right]} \right]\]故可得
\[\underbrace {\mathop {\min }\limits_y \left[ {h(y,z) + \underbrace {\mathop {\min }\limits_x \left[ {g\left( {x,y} \right) + \underbrace {\mathop {\min }\limits_w f\left( {w,x} \right)}_{{f^*}\left( x \right),\begin{array}{*{20}{c}}
{}
\end{array}{w^*}\left( x \right)}} \right]}_{{g^*}\left( {x,y} \right),\begin{array}{*{20}{c}}
{}
\end{array}{x^*}\left( y \right)}} \right]}_{{h^*}(y,z),\begin{array}{*{20}{c}}
{}
\end{array}{y^*}\left( z \right)}\]