2012年1月31日 星期二

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

考慮一組變數 $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)}\]

2012年1月30日 星期一

[數學分析] 函數的單調性質(0)-淺論

令 $f: \mathbb{R} \to \mathbb{R}$ 為函數,

Definition: 我們說 $f$ 為單調遞增 (Monotone increasing) 若下列條件成立:
若 $x_1 < x_2$ 則 $f(x_1) \le f(x_2)$
我們說 $f$ 為單調遞減 (Monotone decreasing) 若下列條件成立:
若 $x_1 > x_2$ 則 $f(x_1) \ge f(x_2)$

我們稱 $f$ 為 單調 (Monotone) 若 $f$ 為單調遞增 或 單調遞減。

以下我們看兩個經典的例子:

Example:
1. 令 $f: \mathbb{R} \to \mathbb{R}$ 滿足 $f(x) = c$ 且  $c \in \mathbb{R}$ 則此常數函數 既為單調遞增 亦為 單調遞減。
2. 令 $f: \mathbb{R} \to \mathbb{R}$ 滿足 $f(x) = |x|$ 則此絕對值函數 並非單調遞增或單調遞減。
但注意到若我們修正絕對值函數的定義域,比如說 令 $f: [0, \infty) \to \mathbb{R}$ 滿足 $f(x) = |x|$ 則此絕對值函數 成為 單調遞增 (讀者可自行證明此性質在此不贅述)。

以下我們給出幾個單調函數重要的結果:


===============
Fact:
1. 若 $f, g$ 為在區間 $I \subset \mathbb{R}$ 上的遞增函數,則 $f+g$ 亦為在 $I$上 遞增函數
2. 若 $f, g$ 為在區間 $I \subset \mathbb{R}$ 上的遞減函數,則 $f+g$ 亦為在 $I$上 遞減函數
===============

Proof: 
我們只證明 (1), (2) 留給讀者作為練習。

現在要證明  $f+g$ 在 $I$ 上遞增,故由定義出發,令 $x_1,x_2 \in I$ 且 $x_1 < x_2$,則由於 $f, g$ 在區間 $I$ 上遞增,故我們有
\[
f(x_1) \le f(x_2)
\]且
\[
g(x_1) \le g(x_2)
\]
現在我們觀察其和,可知
\[
f(x_1) + g(x_1) \le f(x_2) + g(x_2)
\]上述不等式表明 $f+g$ 在 $x_1$的取值 必定小於或等於 $f+g$ 在 $x_2$ 上的取值,也就是說
\[
(f+g)(x_1) \le (f+g)(x_2)\;\;\;\;\;\;\; \square
\]



===============
Theorem 1: 開區間遞增是否保證 加入端點之後仍為遞增?
令 $f$ 為在 $(a,b)$ 遞增 ,若 $f$ 在 $a$ 點連續,則 $f$ 在 $[a,b)$ 仍為遞增
同理,若 $f$ 在 $b$ 點連續,則 $f$ 在 $(a,b]$ 仍為遞增。
===============
Proof Sketch: 因為 $f$ 在 $a$ 點連續,其在該點極限值等於該點函數值 $f(a)$ 現在取 $x \in (a,b)$ 則 $x > a$ 其遞增性保證 $f(x) \ge f(a)$


===============
Theorem 2: 遞增函數保證左右極限存在
令 $f: \mathbb{R} \to \mathbb{R}$ 為單調函數,
1. 則 對任意 $t \in \mathbb{R}$ ,左極限 與 右極限 $f(t-)$ 與 $f(t+)$ 存在且有限,且 $f(\infty-)$ 與 $f(\infty+) $ 存在 。
2. 若 $f$ 為單調遞增,則 $f(t^-) \le f(t) \le f(t+)$
3. 若 $f$ 為單調遞減,則 $f(t^-) \ge f(t) \ge f(t^+)$
===============

Proof: omitted


Theorem 2:
考慮 $f: \mathbb{R} \to \mathbb{R}$ 為單調函數,現令集合 $E \neq \emptyset$ 為 $f$ 在 ${\bf \mathbb{R}}$ 上 所有 不連續的點 所形成的集合,亦即
\[
E \doteq \{x \in \mathbb{R}: f \text{ is discontinuous at $x$}\}
\]則集合 $E$ 只有以下兩種可能
1. $E$ 為有限(finite)
2. $E$ 為可數無窮 (countably infinite)

Comments:
1. 我們說一個集合為 有限 表示此 集合所含有的元素個素為有限多個。另外我們說一個集合 $E$ 為 可數無窮 表示 存在一個 一對一映射的函數 $g: E \to \mathbb{N}$。
2. 我們說一個函數 $f: \mathbb{R} \to \mathbb{R}$ 在 $t \in \mathbb{R}$ 點不連續若且唯若 其左右極限存在但與函數值不相等,亦即
\[
f(t^+) := \lim_{x \to t^+} f(x) \neq \lim_{x \to t^-} f(x) := f(t^-) \neq f(t)
\]

Proof:
注意到若 $f$ 為單調遞增,則 $-f$ 為單調遞減,但不連續的點個數相等,故我們可僅僅考慮 $f$ 為單調遞增的情形。


\[
E \doteq \{x \in \mathbb{R}: f \text{ is discontinuous at $x$}\} \neq \emptyset
\]我們要證明 (1) 與 (2) ,基本想法為由於 $f$ 取值為在實數軸 $\mathbb{R}$ 上,故由有理數在實數軸上的稠密性來試圖說明為何 (1) 與 (2) 成立。 亦即對任意 $x \in E $ 我們有 $f(x^-) < f(x^+)$且由於 $f$ 取值為在實數軸 $\mathbb{R}$ 上,故由稠密性可知 存在 $q_x \in \mathbb{Q}$ 使得
\[
f(x^-) < q_x < f(x^+)
\]
有了以上想法,我們現在利用 $f$ 單調遞增性質可知
\[
x_1 < x_2 \Rightarrow f(x_1^+) \le f(x_2^-)
\]故若 $x_1, x_2 \in E$ 且 $x_1 < x_2$ 則存在 $q_{x_1}, q_{x_2} \in \mathbb{Q}$ 使得
\[
q_{x_1} < q_{x_2}
\]用上述的構造 $q_{x_1}, q_{x_2}$ 我們得到以下結果:對任意 $x \in E$ 而言,存在彼此相異的有理數來表示 $x$ 且此表示為 1-1 對應。我們將所有對應的有理數收集起來建構以下集合
\[
\{q_x \in \mathbb{Q}: x \in E\}
\]則因為 $q_x \in \mathbb{Q}$ 為有理數 故此集合內元素的個素 必定為有限多 或者 可數無限多個。$\square$

2012年1月21日 星期六

[線性系統] 離散時間狀態空間模型 與其解

一般若需要將控制系統透過 電腦 實現控制力 或者 對連續時間系統進行取樣,則我們稱此類系統為 電腦控制系統 或稱 數位控制系統。這次我們要介紹如何從連續時間模型 將其 透過適當的數學操作,從而獲得其對應的離散化的模型。

現在考慮有限維 線性非時變 連續時間狀態空間模型如下:
\[\left\{ \begin{array}{l}
\dot x\left( t \right) = A_cx\left( t \right) + B_cu\left( t \right);\begin{array}{*{20}{c}}
{}&{}
\end{array}x\left( 0 \right) = {x_0}\\
y\left( t \right) = C_c x\left( t \right) + D_cu\left( t \right)
\end{array} \right. \ \ \ \ \ \ \ \ \ (\star)
\]注意到上述狀態空間模型含有微分項 $\dot x$,若我們想要透過電腦實現微分方程,則我們需將其進行 離散化(Discretization)
\[\dot x\left( t \right): = \mathop {\lim }\limits_{\Delta  \to 0} \frac{{x\left( {t + \Delta } \right) - x\left( t \right)}}{\Delta }\]則前述連續時間的狀態方程 $(\star)$ 可表為
\[\begin{array}{l}
\dot x\left( t \right) = {A_c}x\left( t \right) + {B_c}u\left( t \right)\\
 \Rightarrow x\left( {t + \Delta } \right) - x\left( t \right) = {A_c}x\left( t \right)\Delta  + {B_c}u\left( t \right)\Delta \\
 \Rightarrow x\left( {t + \Delta } \right) = x\left( t \right) + {A_c}x\left( t \right)\Delta  + {B_c}u\left( t \right)\Delta
\end{array}\]前述的 $\Delta$ 一般在實現上稱為取樣時間 (sampling time),且對 $k \in \mathbb{Z}$, $t := k \Delta$,我們可改寫
\[\begin{array}{l}
\left\{ {\begin{array}{*{20}{l}}
{x\left( {k\Delta  + \Delta } \right) = \left( {I + {A_c}\Delta } \right)x\left( {k\Delta } \right) + {B_c}u\left( {k\Delta } \right)\Delta }\\
{y\left( {k\Delta } \right) = {C_c}x\left( {k\Delta } \right) + {D_c}u\left( {k\Delta } \right)}
\end{array}} \right.\\
 \Rightarrow \left\{ {\begin{array}{*{20}{l}}
{x\left( {\left( {k + 1} \right)\Delta } \right) = \left( {I + {A_c}\Delta } \right)x\left( {k\Delta } \right) + {B_c}u\left( {k\Delta } \right)\Delta }\\
{y\left( {k\Delta } \right) = {C_c}x\left( {k\Delta } \right) + {D_c}u\left( {k\Delta } \right)}
\end{array}} \right.
\end{array}\]上式現在可以很容易地透過 MATLAB 實現。

更進一步,若考慮 $u(t)$ 也透過電腦計算而得,再透過數位類比轉換 (Digital-Analog converter ) 或 零階保持(Zero-Order Hold),則 $u(t)$ 將會是 piecewise constant 。也就是說對任意 $t$ 滿足 $k\Delta \le t < (k+1) \Delta$,我們的控制力可定義為
$$u(t) := u(k \Delta) := u(k) \;\;\; \forall k=0,1,2,...$$ 此時控制力 $u(k)$ 將只會在 取樣點 $k\Delta$ 上有變動,且在取樣點上,我們連續時間系統的解仍然成立,故對於 $t = k \Delta$ ,我們可定義狀態方程的解
\[\begin{array}{*{20}{l}}
{x\left( k \right): = x\left( {k\Delta } \right) = {{\left. {x\left( t \right)} \right|}_{t = k\Delta }}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {{\left. {\left( {{e^{{A_c}t}}{x_0} + \int_0^t {{e^{{A_c}\left( {t - \tau } \right)}}} Bu\left( \tau  \right)d\tau } \right)} \right|}_{t = k\Delta }}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {e^{{A_c}k\Delta }}{x_0} + \int_0^{k\Delta } {{e^{{A_c}\left( {k\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau }
\end{array}
\]且 對於 $t = (k+1) \Delta$ 而言,我們亦可定義
\[\small \begin{array}{*{20}{l}}
{x\left( {k + 1} \right): = x\left( {\left( {k + 1} \right)\Delta } \right) = {{\left. {x\left( t \right)} \right|}_{t = \left( {k + 1} \right)\Delta }}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {{\left. {\left( {{e^{{A_c}t}}{x_0} + \int_0^t {{e^{{A_c}\left( {t - \tau } \right)}}} Bu\left( \tau  \right)d\tau } \right)} \right|}_{t = \left( {k + 1} \right)\Delta }}}\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {e^{{A_c}\left( {k + 1} \right)\Delta }}{x_0} + \int_0^{\left( {k + 1} \right)\Delta } {{e^{{A_c}\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau }\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {e^{{A_c}\left( {k + 1} \right)\Delta }}{x_0} + \int_0^{k\Delta } {{e^{{A_c}\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau  + \int_{k\Delta }^{\left( {k + 1} \right)\Delta } {{e^{{A_c}\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau }\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {e^{{A_c}\Delta }}\underbrace {\left[ {{e^{{A_c}k\Delta }}{x_0} + \int_0^{k\Delta } {{e^{{A_c}\left( {k\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau } \right]}_{ = x\left( k \right)} + \int_{k\Delta }^{\left( {k + 1} \right)\Delta } {{e^{{A_c}\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau }\\
{\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {e^{{A_c}\Delta }}x\left( k \right) + \int_{k\Delta }^{\left( {k + 1} \right)\Delta } {{e^{{A_c}\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau \;\;\;\;\;(**)}
\end{array}\]現在若令新的變數 $\alpha : = \left( {k + 1} \right)\Delta  - \tau $ 則 $(**)$ 可被改寫為
\[ \begin{array}{l}
x\left( {k + 1} \right) = {e^{A\Delta }}x\left( k \right) + \int_{\left( k \right)\Delta }^{\left( {k + 1} \right)\Delta } {{e^{A\left( {\left( {k + 1} \right)\Delta  - \tau } \right)}}} Bu\left( \tau  \right)d\tau \\
 \Rightarrow x\left( {k + 1} \right) = {e^{A\Delta }}x\left( k \right) + \left( {\int_0^\Delta  {{e^{A\alpha }}} d\alpha } \right)Bu\left( k \right)
\end{array}\]注意到上式中第二行 $u(k)$ 被提到積分外面是因為 $u(t)$ 在 $k\Delta \le t < (k+1)\Delta$ 之間為 constant。

故總結上式,我們有
\[\left\{ \begin{array}{l}
x\left( {k + 1} \right) = \underbrace {{e^{{A_c}\Delta }}}_Ax\left( k \right) + \underbrace {\left( {\int_0^\Delta  {{e^{{A_c}\alpha }}} d\alpha } \right)B}_Bu\left( k \right)\\
y\left( k \right) = Cx\left( k \right) + Du\left( k \right)
\end{array} \right.\] 上式即稱為對應的 零階自保持的 有限維 線性非時變 離散時間狀態空間模型 。

若 $A_c$ 反矩陣存在,則上述的 $B$ 矩陣 可更進一步計算如下,
\[\begin{array}{l}
B = \left( {\int_0^\Delta  {{e^{{A_c}\alpha }}d\alpha } } \right)B\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \left( {\int_0^\Delta  {\left( {I + {A_c}\alpha  + \frac{{{{\left( {{A_c}\alpha } \right)}^2}}}{{2!}} + ...} \right)d\alpha } } \right)B\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \left( {\int_0^\Delta  {\left( I \right)d\alpha }  + \int_0^\Delta  {\left( {{A_c}\alpha } \right)d\alpha }  + \int_0^\Delta  {\left( {\frac{{{{\left( {{A_c}\alpha } \right)}^2}}}{{2!}}} \right)d\alpha }  + ...} \right)B\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \left( {I\Delta  + {A_c}\frac{{{\Delta ^2}}}{2} + {A_c}^2\frac{{{\Delta ^3}}}{{3!}} + ...} \right)B\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \left( {\sum\limits_{k = 1}^\infty  {{A_c}^{k - 1}\frac{{{\Delta ^k}}}{{k!}}} } \right)B\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = \left( {{A_c}^{ - 1}\sum\limits_{k = 1}^\infty  {\frac{{{{\left( {{A_c}\Delta } \right)}^k}}}{{k!}}} } \right)B = \left( {{A_c}^{ - 1}\left( {{e^{{A_c}\Delta }} - I} \right)} \right)B
\end{array}\]


現在我們可以開始求解離散化的狀態空間方程
\[\left\{ {\begin{array}{*{20}{l}}
{x\left( {k + 1} \right) = Ax\left( k \right) + Bu\left( k \right)}\\
{y\left( k \right) = Cx\left( k \right) + Du\left( k \right)}
\end{array}} \right.\]首先觀察
\[\left\{ \begin{array}{l}
x\left( 1 \right) = Ax\left( 0 \right) + Bu\left( 0 \right)\\
x\left( 2 \right) = Ax\left( 1 \right) + Bu\left( 1 \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^2}x\left( 0 \right) + ABu\left( 0 \right) + Bu\left( 1 \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^2}x\left( 0 \right) + \sum\limits_{j = 0}^1 {{A^{1 - j}}Bu\left( j \right)} \\
x\left( 3 \right) = Ax\left( 2 \right) + Bu\left( 2 \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^3}x\left( 0 \right) + {A^2}Bu\left( 0 \right) + ABu\left( 1 \right) + Bu\left( 2 \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array} = {A^3}x\left( 0 \right) + \sum\limits_{j = 0}^2 {{A^{2 - j}}Bu\left( j \right)} \\
 \vdots
\end{array} \right.\]故
\[x\left( k \right) = {A^k}x\left( 0 \right) + \sum\limits_{j = 0}^{k - 1} {{A^{k - 1 - j}}Bu\left( j \right)} \]