4/03/2012

[隨機分析] Uniqueness and Existence theorem for S.D.E. (1)- Uniqueness

這次要介紹的是 隨機微分方程的存在與唯一性定理:
介紹定理之前我們先回憶一下隨機微分方程(Stochastic Differential Equation, SDE)長甚麼樣子

考慮 $t \in [0,T]$,SDE定義如下
\[
dX_t = \mu(t,X_t)dt + \sigma(t,X_t) dB_t, \ X(0)=x_0
\]
但注意到SDE實質上並無嚴格定義,只有定義在積分型式
\[
X_t = X_0 + \int_0^t \mu(s,X_s) ds + \int_0^t \sigma(s,X_s) dB_s
\]

但問題是如果給定一個SDE,我們想問甚麼時候有解? 該怎麼辦? 存在性與唯一性定理告訴我們在甚麼樣的條件之下,SDE存在有解,且此解為唯一。

在回答這個問題之前,我們需要一個積分不等式的 FACT。

========================
FACT: (Gronwall's inequality)
考慮 $t \in [0,T]$,且 $g \in L^1[0,T]$,若 $g(t) \leq C \cdot \int_{t_0}^{t} g(s) ds + B$ ,則
\[
g(t) \leq B \cdot e^{C (t-t_0)}
\]========================
Proof
設 $g(t) \leq C \cdot \int_{t_0}^{t} g(s) ds + B$ ,我們需要證明
\[
g(t) \leq B \cdot e^{C (t-t_0)}
\]已知
\[\begin{array}{l}
\frac{d}{{dt}}\left( {{e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds} } \right) =  - C{e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds}  + {e^{ - Ct}}g\left( t \right)\\
 \Rightarrow \frac{d}{{dt}}\left( {{e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds} } \right) = {e^{ - Ct}}\left[ {g\left( t \right) - C\int_{{t_0}}^t {g\left( s \right)ds} } \right]
\end{array}
\]由我們的假設  $g(t) \leq C \cdot \int_{t_0}^{t} g(s) ds + B$ 可知
\[\frac{d}{{dt}}\left( {{e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds} } \right) \le B \cdot {e^{ - Ct}}
\]兩邊同積分,可得
\[\begin{array}{l}
\int_{{t_0}}^t {\frac{d}{{dt}}\left( {{e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds} } \right)} ds \le B \cdot \int_{{t_0}}^t {{e^{ - Cs}}} ds\\
 \Rightarrow {e^{ - Ct}}\int_{{t_0}}^t {g\left( s \right)ds}  \le B \int_{{t_0}}^t {{e^{ - Cs}}} ds  = \frac{{  B \cdot }}{C}\left( {{e^{ - Ct}} - {e^{ - C{t_0}}}} \right)
\end{array}\]
亦即
\[ \Rightarrow \int_{{t_0}}^t {g\left( s \right)ds}  \le B{e^{Ct}}\frac{{{{\rm{e}}^{ - C{t_0}}} - {{\rm{e}}^{ - Ct}}}}{C} = \frac{B}{C}\left( {{e^{C\left( {t - {t_0}} \right)}} - 1} \right)
\]現在把上式帶回我們的假設
\[\begin{array}{l}
g(t) \le C \cdot \int_{{t_0}}^t g (s)ds + B \le C \cdot \left( {\frac{B}{C}\left( {{e^{C\left( {t - {t_0}} \right)}} - 1} \right)} \right) + B = B{e^{C\left( {t - {t_0}} \right)}}\\
 \Rightarrow g(t) \le B{e^{C\left( {t - {t_0}} \right)}}
\end{array}
\] 即為所求。$\square$


有了以上結果我們便可以開始討論存在性與唯一性定理。現在我們給出 SDE的存在性與唯一性定理:

=============================
Theorem (Existence and Uniqueness)
考慮 $t \in [0,T]$,SDE:
\[
dX_t = \mu(t,X_t)dt + \sigma(t,X_t) dB_t, \ X(0)=x_0 \ \ \ \ (*)
\]若其係數 $\mu, \sigma$滿足  Lipschitz condition
\[
|\mu(t,x) - \mu(t,y)|^2 + |\sigma(t,x) - \sigma(t,y)|^2 \leq K |x-y|^2
\]與 Growth condition
\[
|\mu(t,x)|^2 + |\sigma(t,x)|^2 \leq K(1 + |x|^2)
\]則 $(*)$ 存在一個 Continuous adapted 的解 $X_t$ 且 uniformly bounded in $L^2(dP)$;亦即
\[
\displaystyle \sup_{0 \leq t \leq T}E[X_t^2] < \infty
\]更進一步,若 $X_t$ 與 $Y_t$ 兩者都為式 $(*)$ 的 Continuous $L^2$ bounded 的解,則
\[
P(\{ X_t = Y_t, \forall \ t\in[0,T]\}) =1
\]=============================

Proof
先證明 Uniqueness
Idea: 兩個 Solution 的差 $X_t -Y_t =0$

故令 $X_t$ 與 $Y_t$ 皆滿足 SDE $(*)$並有相同的初始條件 $X_0 = Y_0$,亦即
\[
X_t = X_0 + \int_0^t \mu(s,X_s) ds + \int_0^t \sigma(s,X_s) dB_s \\
Y_t = Y_0 + \int_0^t \mu(s,Y_s) ds + \int_0^t \sigma(s,Y_s) dB_s
\]現在觀察此兩者的差
\[
X_t -Y_t =  \int_0^t ( \mu(s,X_s) - \mu(s,Y_s) )ds + \int_0^t ( \sigma(s,X_s) -\sigma(s,Y_s) )dB_s
\]
現在利用一個Trick:  $(u+v)^2 \leq 2 u^2 + 2v^2$;我們可推得上式為
\[{\left| {{X_t} - {Y_t}} \right|^2} \le 2{\left[ {\int_0^t {(\mu (} s,{X_s}) - \mu (s,{Y_s}))ds} \right]^2} \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \  + 2{\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}))d{B_s}} \right]^2} \ \ \ \ (\star)
\]
對於 $(\star)$ 不等式右邊的第一項,我們可透過 Cauchy-Schwarz inequality (TRICK 1): $\left (\int_0^t f \cdot g \right)^2 \leq \int_0^t f^2 \cdot \int_0^t g^2$,我們可進一步對上式做出估計
\[
2\left[ {\int_0^t {(\mu (s,{X_s}) - \mu (s,{Y_s})} {)^2}ds} \right]\left[ {\int_0^t {{1^2}} ds} \right] \\
\ \ \ \ \ \ \ \ \ \ \ = {\rm{ }}2t\left[ {\int_0^t {(\mu (s,{X_s}) - \mu (s,{Y_s})} {)^2}ds} \right]
\]又由 Lipschitz condition
\[
|\mu(t,x) - \mu(t,y)|^2 + |\sigma(t,x) - \sigma(t,y)|^2 \leq K |x-y|^2
\]我們知道
\[ {2t\left[ {\int_0^t {(\mu (s,{X_s}) - \mu (s,{Y_s})} {)^2}ds} \right]} \le 2t\left[ {\int_0^t {K{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right]
\]
現在我們觀察  $(\star)$  不等式右邊的第二項:
注意到如果我們對其取期望值,則由 Ito Isometry 可以得到
\[2 \cdot E{\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}))d{B_s}} \right]^2} = 2 \cdot E\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}){)^2}ds} \right]
\]又由 Lipschitz condition 我們知道
\[
2 \cdot E\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}){)^2}ds} \right] \le 2 \cdot E\left[ {\int_0^t {K{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right] \\
 \Rightarrow 2 \cdot E{\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}))d{B_s}} \right]^2} \le 2 \cdot E\left[ {\int_0^t {K{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right]
\]
上式Ito isometry make sense,因為 L^2 boundedness of $|X_t - Y_t|$。

故現在將已有的結果整理:
\[\begin{array}{l}
E\left[ {{{\left| {{X_t} - {Y_t}} \right|}^2}} \right] \le E\left\{ \begin{array}{l}
2{\left[ {\int_0^t {(\mu (} s,{X_s}) - \mu (s,{Y_s}))ds} \right]^2}\\
 + 2{\left[ {\int_0^t {(\sigma (} s,{X_s}) - \sigma (s,{Y_s}))d{B_s}} \right]^2}
\end{array} \right\}\\
 \Rightarrow E\left[ {{{\left| {{X_t} - {Y_t}} \right|}^2}} \right] \le 2t{\rm{E}}\left[ {\int_0^t {K{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right] + 2 E\left[ {\int_0^t {K{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right]\\
 \Rightarrow E\left[ {{{\left| {{X_t} - {Y_t}} \right|}^2}} \right] \le \left( {2t + 2} \right)K \cdot E\left[ {\int_0^t {{{\left| {{X_s} - {Y_s}} \right|}^2}} ds} \right] \\
 \Rightarrow E\left[ {{{\left| {{X_t} - {Y_t}} \right|}^2}} \right] \le \left( {2t + 2} \right)K \cdot \int_0^t {E\left[ {{{\left| {{X_s} - {Y_s}} \right|}^2}} \right]} ds
\end{array}
\]為簡潔起見,我們定義一個常數 $C \geq 2K \cdot (2t+2)$ 且令 $g(t) = E[|X_t - Y_t|^2]$;故得到
\[
E\left[ {{{\left| {{X_t} - {Y_t}} \right|}^2}} \right] \le C \cdot \int_0^t {E\left[ {{{\left| {{X_s} - {Y_s}} \right|}^2}} \right]} ds
\]也就是說
\[
{\rm{0}} \le g\left( t \right) \le C \cdot \int_0^t {E\left[ {{{\left| {{X_s} - {Y_s}} \right|}^2}} \right]} ds = C \cdot \int_0^t {g\left( s \right)} ds \ \ \ \ (**)
\]現在由 Gronwall's inequality,
----
FACT: (Gronwall's inequality)
考慮 $t \in [0,T]$,且 $g \in L^1[0,T]$,若 $g(t) \leq C \cdot \int_{t_0}^{t} g(s) ds + B$ ,則
\[
g(t) \leq B \cdot e^{C (t-t_0)}
\]----
可知我們的 $B =0, t_0 =0$,故 Gronwall's inequality告訴我們
\[
g(t) \leq 0
\] 又由 $(**)$ 我們知道 $ 0 \leq g(t)$;故我們得到對所有的 $t \in [0,T]$
\[
g(t)=0 \Rightarrow  g(t) = E[|X_t - Y_t|^2] =0
\]
亦即,如果我們對所有的有理數 $t \in [0,T]$,使用 $g(t)=0$,則有如下關係
\[
P(\{ X_t = Y_t, \forall \ \text{rational} \ t\in [0,T] \}) =1
\]
再者因為$X_t, Y_t$ 為連續,故由連續性可知
\[
P(\{ X_t = Y_t, \forall \ t\in[0,T]\}) =1 \ \ \ \ \square
\]

3/25/2012

[分享] 控制理論與人生

03.25.2012 板橋基督長老教會-青年團契職場分享 控制理論與人生
http://www.youtube.com/watch?v=ogk5WQVf9EI&feature=plcp
.
主題: 控制理論與人生
(內容因為涉及智慧財產權/研究發表,部分內容已經移除請見諒)

本專講是個人職涯分享,以及個人學習控制理論的少許經驗累積
與聖經內容對照,將心得與大家分享。.
願神的道光照每個人的心,更願人常常思想祂的道
感謝神,一切榮耀歸給神

==========================


主日禮拜時間:
《台語禮拜》週日上午09:30~11:00
《國語禮拜》週日上午11:05~12:30

教會地址:台北縣板橋市明德街1巷3號
連絡電話:02-29687749
駐堂牧者:洪英俊 牧師

2/11/2012

[微積分] 函數的單調性質(1)-一階導數判斷遞增?遞減?

這次要介紹利用微分來幫助我們判斷 可導函數在某區間 是否遞增/遞減。

Theorem:
1. 考慮函數 $f(x)$ 定義在區間 $(a,b)$上 且在此區間上可導,我們說此函數在 $(a,b)$ 上為 嚴格遞增函數(strictly increasing) 若下列條件成立:
\[
\forall x \in (a,b),\;\; f'(x) >0
\]2. 考慮函數 $f(x)$ 定義在區間 $(a,b)$上 且在此區間上可導,我們說此函數在 $(a,b)$ 上為 嚴格遞減函數(strictly decreasing) 若下列條件成立:
\[
\forall x \in (a,b),\;\; f'(x) <0
\]3. 考慮函數 $f(x)$ 定義在區間 $(a,b)$上 且在此區間上可導,我們說此函數在 $(a,b)$ 上為 常數函數 $c$ 若下列條件成立:
\[
\forall x \in (a,b),\;\; f'(x) =0
\]Proof: omitted.

Example 1:
考慮 $x \in \mathbb{R}$,且定義函數 $f(x) = x^2$,試判斷其遞增/遞減性質:

Solution
利用 前述 Theorem,對 $f(x)$ 求一階導數
\[
f'(x) = 2x
\]故可知當 $f'(x) = 2x >0$ 亦即 $x>0$ 時候 (或者說在區間 $(0,\infty)$) $f$ 為遞增
同理,可推知當 $f'(x) = 2x < 0$ 亦即 當 $x<0$ 時候 (或者說在區間 $(-\infty,0)$) $f$ 為遞減
同理,可推知當 $f'(x) = 2x = 0$ 亦即 當 $x=0$ 時候 (或者說在 $0$ 處) $f$ 為常數。


Example 2:
考慮 $x \in \mathbb{R}$,且定義函數 $f(x) = x^2 + 2x -5$,試判斷其遞增/遞減性質:

Solution
利用 前述 Theorem,對 $f(x)$ 求一階導數
\[
f'(x) = 2x +2
\]故可知當 $f'(x) =  2x +2 >0$ 亦即 $ x>-1$ 時候 (或者說在區間 $(-1,\infty)$) $f$ 為遞增
同理,可推知當 $f'(x) = 2x+2 < 0$ 亦即當 $x<-1$時候 (或者說在區間 $(-\infty,-1)$) $f$ 為遞減
同理,可推知當 $f'(x) = 2x +2 = 0$ 亦即當 $x=-1$時候 (或者說在 $-1$ 處) $f$ 為常數。

Comment:
上述例子讀者也許可能猜想當 出現一階導數為 $0$ 的時候,其函數的遞增/遞減會發生變化,但!! 此猜想並不為真! 下面我們看個例子:


Example 3: 
考慮  $x \in \mathbb{R}$,且定義函數 $f(x) = x^3$,試判斷其遞增/遞減性質:

Solution
利用 前述 Theorem,對 $f(x)$ 求一階導數
\[
f'(x) = 3x^2
\]故可知當 $f'(x) =  3x^2 >0$ 亦即 $ x \in \mathbb{R}$ 時候 $f$ 為遞增 且 永不遞減!!
但是當 $f'(x) = 3x^2 = 0$ 亦即當 $x=0$時候 $f$ 為常數。

此例說明了儘管出現 $x=0$的時候 $f(x)$ 的導數為常數,但此時函數函數的遞增性質並不改變。


Example 4*:
令 $f: [-1,1] \to \mathbb{R}$ 且 $ f(x) = \sqrt{1=x^2}$ 試判斷區間的遞增遞減性質。

Solution
先對該函數求導,可得
\[f'\left( x \right) = \frac{{ - x}}{{\sqrt {1 - {x^2}} }}\]現在觀察上述函數可知 $f'>0$ 當 $x \in (-1,0)$ 且 $f' <0$ 當 $x \in (0, 1)$ 亦即 $(-1,0)$ 此函數遞增,且 $(0,1)$ 此函數遞減。

剩下還有三點 $-1,0,1$ 為判斷遞增遞減性質,此三點的判定可透過前一篇文章我們曾討論過的拓展到端點的定理也就是說如果原函數在關心的端點上連續,則遞增/減性質可被直接拓展到該端點上,現在回到我們的問題可發現,原函數 $f$ 在 $-1$ 與 $0$ 與 $1$ 皆連續,故我們可拓展遞增遞減性質,也就是說 $f$ 在 $[-1,0]$ 遞增,$f$ 在 $[0,1]$ 遞減。


2/10/2012

[微積分] 反函數

想法:給定任意函數 $f(x) = y$ 我們想問 是否可以將其改寫成 $x = g(y)$? 如果可以則稱 $g$ 為 $f$ 的反函數(inverse function)

在介紹反函數之前,我們需要一些定義來幫助我們:

=========================
Definition: one-to-one function
一個函數 $f: X \to Y$ 稱作 one-to-one function 若下列條件成立:
對任意 $x,y \in X$ 我們有\[
f(x) = f(y) \Rightarrow x = y
\]=========================

Comment:
一般而言,one-to-one function 又稱作 injective function 中文譯作 單射函數 或者 一對一函數。


現在看幾個例子試試:

Example
試問 $f(x) = x^3$,$x \in \mathbb{R}$ 是否為 one-to-one?

Solution
給定任意 $x,y \in \mathbb{R}$ ,且假設 $f(x) = f(y)$ 成立 我們要證明 $x=y$,故現在觀察
\[\begin{array}{l}
f(x) = f(y) \Rightarrow {x^3} = {y^3}
\end{array}\]對兩邊取三次方根,可得
\[
x = y. \,\,\,\, \square
\]

Example 
試證函數 $f(x) = x^2$,$x \in \mathbb{R}$ 並非 one-to-one function。

Solution
要證明不是 one-to-one,故對定義取非,要證明 存在一組 $x,y \in \mathbb{R}$ 使得 \[
f(x) = f(y) \; \text{ but} \;\; x \neq y
\]觀察
\[\begin{array}{l}
f(x) = f(y) \Rightarrow {x^2} = {y^2}\\
 \Rightarrow {x^2} - {y^2} = 0\\
 \Rightarrow \left( {x - y} \right)\left( {x + y} \right) = 0
\end{array}\]
故現在選 $x=a$,$y=-a$ ($a>0$為任意常數) ,比如說選 $x = 1$ 且 $y=-1$ 則可得 $f(x) = f(y)$ 但 $x \neq y$ 。$\square$


有了 one-to-one 函數之後我們現在可以介紹 反函數:

================
Definition: Inverse Function
令 $f : X \to Y$ 為 one-to-one 函數。則其反函數 $f^{-1} : B \to A$ 定義為:對任意 $y \in B$,
\[
f^{-1}(y) = x \Leftrightarrow f(x) = y
\]================

================
FACT: 令函數 $f : X \to Y$ 且其反函數 $f^{-1}:Y \to X$ 存在則
\[\begin{array}{l}
{f^{ - 1}}\left( {f\left( x \right)} \right) = x,\begin{array}{*{20}{c}}
{}&{}
\end{array}\forall x \in X\\
f\left( {{f^{ - 1}}\left( x \right)} \right) = x,\begin{array}{*{20}{c}}
{}&{}
\end{array}\forall x \in Y
\end{array}\]================



Example 3:
考慮某函數 $f$ 具有如下性質
\[\left\{ \begin{array}{l}
f\left( 1 \right) = 5\\
f\left( 3 \right) = 7\\
f\left( 8 \right) =  - 1
\end{array} \right.\]試問 $f^{-1}(5), f^{-1}(7), f^{-1}(-1)$ 為何?

Proof:
由前述反函數定義可知
\[\left\{ \begin{array}{l}
f\left( 1 \right) = 5\\
f\left( 3 \right) = 7\\
f\left( 8 \right) =  - 1
\end{array} \right. \Rightarrow \left\{ \begin{array}{l}
{f^{ - 1}}\left( 5 \right) = 1\\
{f^{ - 1}}\left( 7 \right) = 3\\
{f^{ - 1}}\left( { - 1} \right) = 8
\end{array} \right.\]

Example 4:
考慮 $x \in \mathbb{R}$,試問 $f(x) = x^3 + 2$ 的反函數 $f^{-1}$ ?

Proof:
令 $y:= f(x)$,目標是要寫出反函數
\[\begin{array}{l}
f(x) = {x^3} + 2\\
 \Rightarrow x = \sqrt[3]{{y - 2}}
\end{array}\]故反函數 $f^{-1}$ 為
\[\begin{array}{l}
{f^{ - 1}}\left( {{x^3} + 2} \right) = x\\
 \Rightarrow {f^{ - 1}}\left( y \right) = \sqrt[3]{{y - 2}}
\end{array}\]上式中 $y$ 為 dummy variable



Theorem: 令 $f:X \to Y$ 為 嚴格單調遞增函數,則 $f$ 為 one-to-one

Proof: 給定 $f:X \to Y$ 為 嚴格單調遞增 (亦即 $f(x_1) < f(x_2), \; \forall x_1<x_2$),我們要證明 $f$ 為 one-to-one,故取 $x_1,x_2 \in X$ 且設 $f(x_1) = f(x_2)$ 我們要證明 $x_1 = x_2$。利用反證法,假設 $x_1 \neq x_2$,則不失一般性情況我們設 $x_1 > x_2$,則由嚴格單調性可知 \[
f(x_1) > f(x_2)
\]此條件違反我們前提 $f(x_1) = f(x_2)$,故得到矛盾。$\square$


Theorem (Corollary): $f: X \to Y$ 為單調遞增,則 $f$ 具有反函數。
Proof:  使用前述的定理與 FACT 即可證得。$\square$

1/31/2012

[最佳控制] 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)}\]

1/30/2012

[數學分析] 函數的單調性質(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$

1/21/2012

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

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

現在考慮有限維 線性非時變 連續時間狀態空間模型如下:
\[\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)} \]


[測度論] 期望值下確界與函數值下確界之恆等式

  Claim: 令 $(X, \mathcal{F})$ 為可測空間。令 $g: X \to \mathbb{R}$ 為可測函數,則 $$\inf_{\mathbb{P} \in \mathcal{P}(X)} \int_X g(x) d\mathbb{P}(x) = \in...