考慮線性非時變 (Linear Time-Invariant, LTI)系統利用狀態空間表示：
\[
{\bf \dot x} = A {\bf x} + B {\bf u}
\] 回憶在大學部自動控制課程中，我們知道 LTI 系統穩定 的 充分必要條件 為系統矩陣 $A$ 之特徵值具有負實部 （或者等價論述為 極點 pole 落在 複數平面的左半面）。現在我們想問若 系統為 線性時變 (Linear Time-Varying, LTV)系統是否此條件依然成立？
答案是否定的，以下為一個極為出色的反例：考慮線性時變系統 ${\bf \dot x} = A(t) {\bf x} $ 其中
\[A\left( t \right): = \left[ {\begin{array}{*{20}{c}}
{ - 1}&{{e^{2t}}}\\
0&{ - 1}
\end{array}} \right]
\] 且給定初始狀態為 $x_1(0) = x_2(0)=1$ 則由於此系統 $A(t)$ 矩陣為三角矩陣，其特徵值為對角線元素，亦即 $\lambda_{1,2} = -1$，具有負實部。然而，若我們求解此 LTV 系統，亦即觀察
\[{\bf{\dot x}}\left( t \right) = \left[ {\begin{array}{*{20}{c}}
{ - 1}&{{e^{2t}}}\\
0&{ - 1}
\end{array}} \right]\left[ \begin{array}{l}
{x_1}\left( t \right)\\
{x_2}\left( t \right)
\end{array} \right] = \left[ \begin{array}{l}
- {x_1}\left( t \right) + {e^{2t}}{x_2}\left( t \right)\\
- {x_2}\left( t \right)
\end{array} \right]\]故我們可首先解得
\[\begin{array}{*{20}{l}}
{{{\dot x}_2}\left( t \right) = - {x_2}\left( t \right)}\\
\begin{array}{l}
\Rightarrow {x_2}\left( t \right) = {e^{ - t}}{x_2}\left( 0 \right)\\
\Rightarrow {x_2}\left( t \right) = {e^{ - t}}
\end{array}
\end{array}
\]再將此 $x_2(t)$ 帶回 $\dot x_1(t)$ 式中，可求解 $x_1$ 如下
\[\begin{array}{*{20}{l}}
{{{\dot x}_1}\left( t \right) = - {x_1}\left( t \right) + {e^{2t}}{x_2}\left( t \right)}\\
{ \Rightarrow {{\dot x}_1}\left( t \right) = - {x_1}\left( t \right) + {e^{2t}}{e^{ - t}}}\\
{ \Rightarrow {x_1}\left( t \right) = {e^{ - t}}{x_1}\left( 0 \right) + \int_0^t {{e^{ - \left( {t - \tau } \right)}}{e^\tau }d\tau } }\\
{ \Rightarrow {x_1}\left( t \right) = {e^{ - t}} + {e^{ - \left( t \right)}}\int_0^t {{e^{2\tau }}d\tau } }\\
{ \Rightarrow {x_1}\left( t \right) = \frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}}
\end{array}\]故系統之解為
\[{{\bf{x}}\left( t \right) = \left[ \begin{array}{l}
{e^{ - t}}\\
\frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}
\end{array} \right]}\]但注意到若我們計算上述之狀態的 2-norm 且取極限 $t \to \infty$ 會發現
\[\begin{array}{l}
\mathop {\lim }\limits_{t \to \infty } \left\| {{\bf{x}}\left( t \right)} \right\| = \mathop {\lim }\limits_{t \to \infty } \left\| {\left[ \begin{array}{l}
{e^{ - t}}\\
\frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}
\end{array} \right]} \right\|\\
= \mathop {\lim }\limits_{t \to \infty } {\left( {\left[ {\begin{array}{*{20}{c}}
{{e^{ - t}}}&{\frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}}
\end{array}} \right]\left[ \begin{array}{l}
{e^{ - t}}\\
\frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}
\end{array} \right]} \right)^{1/2}}\\
= \mathop {\lim }\limits_{t \to \infty } {\left( {{e^{ - 2t}} + {{\left( {\frac{1}{2}{e^t} + \frac{1}{2}{e^{ - \left( t \right)}}} \right)}^2}} \right)^{1/2}} = \infty
\end{array}\]亦即系統狀態發散。
上述結果闡釋了對於 LTV 系統而言，負實部特徵值 (左半面極點) 不保證系統穩定。
2016年3月28日 星期一
2016年3月11日 星期五
[凸分析] 支撐函數
以下我們給出凸分析中 常用的函數，稱作 支撐函數 (Support Function)：
=====================
Definition: Support Function
令 $\mathcal{X}$ 為 $\mathbb{R}^n$ 中的任意緊緻集合 (compact set)，我們稱函數 $h_{\mathcal{X}}: \mathbb{R}^n \to \mathbb{R} \bigcup \{+\infty\}$ 為 support function of $\cal X$ 若下列條件成立：對任意 $ {\bf y} \in \mathbb{R}^n$
\[
h_{\cal X}( {\bf y }) := \sup_{ {\bf x} \in \mathcal{X}} {\bf y}^T {\bf x}
\]=====================
Comments:
1. $\mathbb{R}^n$ 空間中，緊緻集合(compact set) 等價 有界封閉集 (closed and bounded set)
以下我們有一個極為重要的結果：任意集合的支撐函數 與 該集合的凸包 (convex hull) 之支撐函數相等。令 $\cal X$ 為任意集合，以下我們令 $conv( {\mathcal{X}})$ 為該集合 $\cal X$ 的凸包。對凸包定義不熟悉的讀者可先行閱讀： [凸分析] 凸集合 與 凸包 。
======================
Claim:
令 $conv ({\mathcal {X}})$ 為緊緻集 $\cal X$ 的 convex hull 則
\[
h_{\cal X} ({\bf y}) = h_{conv({\mathcal{X} })} ({\bf y})
\]=====================
Proof:
給定任意 $\bf y$$\in \mathbb{R}^n$，我們需證明 $ h_{\cal X} ({\bf y}) \le h_{conv({\mathcal{X} })} ({\bf y}) $ 與 $ h_{\cal X} ({\bf y}) \ge h_{conv({\mathcal{X} })} ({\bf y}) $
故現在我們首先證明 $ h_{\cal X} ({\bf y}) \le h_{ conv({\mathcal{X} })} ({\bf y})$ ：注意到由於 $conv({\mathcal{X} }) \supset {\cal X}$ ，故
\[
\sup_{ {\bf x} \in \mathcal{X}} {\bf y}^T {\bf x} \le \sup_{ {\bf x} \in conv(\mathcal{X})} {\bf y}^T {\bf x} \;\;\;\;\;\; (*)
\]
接著我們證明 $h_{\cal X} ({\bf y}) \ge h_{ conv({\mathcal{X} })} ({\bf y}) $ ：我們從不等式右方出發，首先觀察凸包中的任意點 $\bf x$ $\in conv(\mathcal{X})$ 均可被有限個 ${\bf x}^i \in \mathcal{X}$ 且 $i=1,2,...,m$ 透過 convex combination 組合而得，亦即存在一組非負常數 $\lambda_{i} \ge 0$ 且 $\sum_{i=1 }^m \lambda_i =1 $，$i=1,2,...,m$ 使得
\[
{\bf x} = \sum_{i=1}^m \lambda_i {\bf x}^i
\]現在我們觀察內積 ${\bf y}^T {\bf x}$， 我們有
\[{{\bf{y}}^T}{\bf{x}} = {{\bf{y}}^T}\left( {\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{x}}^i}} \right) = \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i}
\]且我們知道必定存在 ${\bf x}^{i^*} \in \mathcal{X}$ 使得
\[\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\]由上述不等式可推得
\[\begin{array}{l}
\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\\
\Rightarrow \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\sum\limits_{i = 1}^m {{\lambda _i}} = {{\bf{y}}^T}{{\bf{x}}^{{i^*}}} \le \mathop {\sup }\limits_{{\bf{x}} \in X} {{\bf{y}}^T}{\bf{x}} \;\;\;\; (**)
\end{array}\]故由 $(*)$ 與 $(**)$ 我們得到
\[
h_{\cal X} ({\bf y}) = h_{conv({\mathcal{X} })} ({\bf y})
\]
=====================
Definition: Support Function
令 $\mathcal{X}$ 為 $\mathbb{R}^n$ 中的任意緊緻集合 (compact set)，我們稱函數 $h_{\mathcal{X}}: \mathbb{R}^n \to \mathbb{R} \bigcup \{+\infty\}$ 為 support function of $\cal X$ 若下列條件成立：對任意 $ {\bf y} \in \mathbb{R}^n$
\[
h_{\cal X}( {\bf y }) := \sup_{ {\bf x} \in \mathcal{X}} {\bf y}^T {\bf x}
\]=====================
Comments:
1. $\mathbb{R}^n$ 空間中，緊緻集合(compact set) 等價 有界封閉集 (closed and bounded set)
以下我們有一個極為重要的結果：任意集合的支撐函數 與 該集合的凸包 (convex hull) 之支撐函數相等。令 $\cal X$ 為任意集合，以下我們令 $conv( {\mathcal{X}})$ 為該集合 $\cal X$ 的凸包。對凸包定義不熟悉的讀者可先行閱讀： [凸分析] 凸集合 與 凸包 。
======================
Claim:
令 $conv ({\mathcal {X}})$ 為緊緻集 $\cal X$ 的 convex hull 則
\[
h_{\cal X} ({\bf y}) = h_{conv({\mathcal{X} })} ({\bf y})
\]=====================
給定任意 $\bf y$$\in \mathbb{R}^n$，我們需證明 $ h_{\cal X} ({\bf y}) \le h_{conv({\mathcal{X} })} ({\bf y}) $ 與 $ h_{\cal X} ({\bf y}) \ge h_{conv({\mathcal{X} })} ({\bf y}) $
故現在我們首先證明 $ h_{\cal X} ({\bf y}) \le h_{ conv({\mathcal{X} })} ({\bf y})$ ：注意到由於 $conv({\mathcal{X} }) \supset {\cal X}$ ，故
\[
\sup_{ {\bf x} \in \mathcal{X}} {\bf y}^T {\bf x} \le \sup_{ {\bf x} \in conv(\mathcal{X})} {\bf y}^T {\bf x} \;\;\;\;\;\; (*)
\]
接著我們證明 $h_{\cal X} ({\bf y}) \ge h_{ conv({\mathcal{X} })} ({\bf y}) $ ：我們從不等式右方出發，首先觀察凸包中的任意點 $\bf x$ $\in conv(\mathcal{X})$ 均可被有限個 ${\bf x}^i \in \mathcal{X}$ 且 $i=1,2,...,m$ 透過 convex combination 組合而得，亦即存在一組非負常數 $\lambda_{i} \ge 0$ 且 $\sum_{i=1 }^m \lambda_i =1 $，$i=1,2,...,m$ 使得
\[
{\bf x} = \sum_{i=1}^m \lambda_i {\bf x}^i
\]現在我們觀察內積 ${\bf y}^T {\bf x}$， 我們有
\[{{\bf{y}}^T}{\bf{x}} = {{\bf{y}}^T}\left( {\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{x}}^i}} \right) = \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i}
\]且我們知道必定存在 ${\bf x}^{i^*} \in \mathcal{X}$ 使得
\[\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\]由上述不等式可推得
\[\begin{array}{l}
\sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\\
\Rightarrow \sum\limits_{i = 1}^m {{\lambda _i}} {{\bf{y}}^T}{{\bf{x}}^i} \le {{\bf{y}}^T}{{\bf{x}}^{{i^*}}}\sum\limits_{i = 1}^m {{\lambda _i}} = {{\bf{y}}^T}{{\bf{x}}^{{i^*}}} \le \mathop {\sup }\limits_{{\bf{x}} \in X} {{\bf{y}}^T}{\bf{x}} \;\;\;\; (**)
\end{array}\]故由 $(*)$ 與 $(**)$ 我們得到
\[
h_{\cal X} ({\bf y}) = h_{conv({\mathcal{X} })} ({\bf y})
\]
2016年3月10日 星期四
[微分方程] 人口增長模型
考慮以下初始值問題
\[
\frac{dy}{dt} = ky - cy^2, \;\; y(0) = A \in \mathbb{R}
\]上述微分方程用以描述 具備外在競爭關係 $(-cy^2)$ 的 (人口)成長模型 $(ky)$。一般稱之為 Logistic Equation of Population Growth
Comments:
1. 上述 Logistic Equation 具備 $y' = f(y)$ 形式，其中 $f(y) := ky - cy^2$ ，亦即函數 $f$ 僅與 $y$ 有關而無直接與時間 $t$相關，我們稱此類微分方程為 autonomous equation。
現在我們開始求解 Logistic Equation
Solution:
令 $\phi(t) \neq 0$ 為上述 IVP 在某區間 $I$ 包含 $t=0$ 的解，則在此區間 $I$ 上，我們有
\[
\phi '\left( t \right) = k\phi \left( t \right) - c{\phi ^2}\left( t \right) \;\;\;\;\; (*)
\]注意到儘管上式為非線性，但其具備分離變數形式，故若
\[\begin{array}{l}
k\phi \left( t \right) - c{\phi ^2}\left( t \right) \ne 0\\
\Rightarrow \left( {k - c\phi \left( t \right)} \right)\phi \left( t \right) \ne 0
\end{array}
\]亦即 $\phi \left( t \right) \ne 0 $ 且 ${k - c\phi \left( t \right)} \neq 0$(或者等價 $\phi(t) \neq k/c$) 則我們可以將 $(*)$ 改寫為
\[\begin{array}{l}
\phi '\left( t \right) = k\phi \left( t \right) - c{\phi ^2}\left( t \right)\\
\Rightarrow \frac{{\phi '\left( t \right)}}{{k\phi \left( t \right) - c{\phi ^2}\left( t \right)}} = 1
\end{array}
\]對上式兩邊同積分從 $0$ 到 $t$ 可得
\[\int_0^t {\frac{{\phi '\left( s \right)}}{{k\phi \left( s \right) - c{\phi ^2}\left( s \right)}}ds} = \underbrace {\int_0^t 1 dt}_{ = t}
\]現在令變數變換 $u:= \phi(s)$ 且使用初始條件 $\phi(0) = A$ 我們可將上述積分改寫如下
\[\begin{array}{l}
\int_A^{\phi \left( t \right)} {\frac{1}{{ku - c{u^2}}}} du = t\\
\Rightarrow \int_A^{\phi \left( t \right)} {\frac{1}{{u\left( {k - cu} \right)}}} du = t \;\;\; (**)
\end{array}
\]注意到左式被積函數可透過部分分式展開如下
\[\frac{1}{{u\left( {k - cu} \right)}} = \frac{C}{u} + \frac{D}{{k - cu}}
\]其中 $C = 1/k$ 且 $D =c/k$ 故 $(**)$ 式子改寫為
\[\begin{array}{l}
\frac{1}{k}\int_A^{\phi \left( t \right)} {\frac{1}{u}} du + \frac{c}{k}\int_A^{\phi \left( t \right)} {\frac{1}{{k - cu}}} du = t\\
\Rightarrow \frac{1}{k}\left( {\ln \left| {\phi \left( t \right)} \right| - \ln |A|} \right) + \left( {\frac{1}{{ - k}}} \right)\left( {\ln \left| {k - c\phi \left( t \right)} \right| - \ln \left| {k - cA} \right|} \right) = t\\
\Rightarrow \frac{1}{k}\left( {\ln \left| {\frac{{\phi \left( t \right)}}{A}} \right|} \right) - \frac{1}{k}\left( {\ln \left| {\frac{{k - c\phi \left( t \right)}}{{k - cA}}} \right|} \right) = t\\
\Rightarrow \frac{1}{k}\ln \left| {\frac{{\phi \left( t \right)\left( {k - cA} \right)}}{{A\left( {k - c\phi \left( t \right)} \right)}}} \right| = t
\end{array}
\]由上述結果不難求解 $\phi(t)$ 如下
\[\begin{array}{l}
\phi \left( t \right) = \frac{{kA{e^{kt}}}}{{\left( {k - cA} \right) + cA{e^{kt}}}}\\
\Rightarrow \phi \left( t \right) = \frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}}
\end{array}\]自此我們求解完畢，讀者可自行驗證上述解 $\phi(t)$ 確實滿足 Logistic Equaiton 與初始條件。
Comments:
1. 若 $c = 0$，我們可得
\[{\left. {\phi \left( t \right)} \right|_{c = 0}} = {\left. {\frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}}} \right|_{c = 0}} = A{e^{kt}}\]亦即滿足 $y' = ky$ 之解。
2. 若 $c \neq 0$ 且 $A \neq 0$ 則我們可推得系統其中的一個穩態解
\[\mathop {\lim }\limits_{t \to \infty } \phi \left( t \right) = \mathop {\lim }\limits_{t \to \infty } \frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}} = \frac{k}{c}\]
3. 若 初始條件 $y(0) = A = 0$ 則 $\phi(t) = 0$ 為第二個穩態解
4. 一般我們稱邏輯函數 (Logistic Function) 為
\[L\left( t \right) = \frac{1}{{1 + {e^{ - t}}}}\]讀者可驗證其函數圖形具有 $S$ 形。現在注意到我們上述所求得的解 $\phi(t)$ 形式具備此邏輯函數的形式，故其 ODE
\[
\frac{dy}{dt} = ky - cy^2
\]我們稱其為 Logistic Equation (of Population Growth)
\[
\frac{dy}{dt} = ky - cy^2, \;\; y(0) = A \in \mathbb{R}
\]上述微分方程用以描述 具備外在競爭關係 $(-cy^2)$ 的 (人口)成長模型 $(ky)$。一般稱之為 Logistic Equation of Population Growth
Comments:
1. 上述 Logistic Equation 具備 $y' = f(y)$ 形式，其中 $f(y) := ky - cy^2$ ，亦即函數 $f$ 僅與 $y$ 有關而無直接與時間 $t$相關，我們稱此類微分方程為 autonomous equation。
現在我們開始求解 Logistic Equation
Solution:
令 $\phi(t) \neq 0$ 為上述 IVP 在某區間 $I$ 包含 $t=0$ 的解，則在此區間 $I$ 上，我們有
\[
\phi '\left( t \right) = k\phi \left( t \right) - c{\phi ^2}\left( t \right) \;\;\;\;\; (*)
\]注意到儘管上式為非線性，但其具備分離變數形式，故若
\[\begin{array}{l}
k\phi \left( t \right) - c{\phi ^2}\left( t \right) \ne 0\\
\Rightarrow \left( {k - c\phi \left( t \right)} \right)\phi \left( t \right) \ne 0
\end{array}
\]亦即 $\phi \left( t \right) \ne 0 $ 且 ${k - c\phi \left( t \right)} \neq 0$(或者等價 $\phi(t) \neq k/c$) 則我們可以將 $(*)$ 改寫為
\[\begin{array}{l}
\phi '\left( t \right) = k\phi \left( t \right) - c{\phi ^2}\left( t \right)\\
\Rightarrow \frac{{\phi '\left( t \right)}}{{k\phi \left( t \right) - c{\phi ^2}\left( t \right)}} = 1
\end{array}
\]對上式兩邊同積分從 $0$ 到 $t$ 可得
\[\int_0^t {\frac{{\phi '\left( s \right)}}{{k\phi \left( s \right) - c{\phi ^2}\left( s \right)}}ds} = \underbrace {\int_0^t 1 dt}_{ = t}
\]現在令變數變換 $u:= \phi(s)$ 且使用初始條件 $\phi(0) = A$ 我們可將上述積分改寫如下
\[\begin{array}{l}
\int_A^{\phi \left( t \right)} {\frac{1}{{ku - c{u^2}}}} du = t\\
\Rightarrow \int_A^{\phi \left( t \right)} {\frac{1}{{u\left( {k - cu} \right)}}} du = t \;\;\; (**)
\end{array}
\]注意到左式被積函數可透過部分分式展開如下
\[\frac{1}{{u\left( {k - cu} \right)}} = \frac{C}{u} + \frac{D}{{k - cu}}
\]其中 $C = 1/k$ 且 $D =c/k$ 故 $(**)$ 式子改寫為
\[\begin{array}{l}
\frac{1}{k}\int_A^{\phi \left( t \right)} {\frac{1}{u}} du + \frac{c}{k}\int_A^{\phi \left( t \right)} {\frac{1}{{k - cu}}} du = t\\
\Rightarrow \frac{1}{k}\left( {\ln \left| {\phi \left( t \right)} \right| - \ln |A|} \right) + \left( {\frac{1}{{ - k}}} \right)\left( {\ln \left| {k - c\phi \left( t \right)} \right| - \ln \left| {k - cA} \right|} \right) = t\\
\Rightarrow \frac{1}{k}\left( {\ln \left| {\frac{{\phi \left( t \right)}}{A}} \right|} \right) - \frac{1}{k}\left( {\ln \left| {\frac{{k - c\phi \left( t \right)}}{{k - cA}}} \right|} \right) = t\\
\Rightarrow \frac{1}{k}\ln \left| {\frac{{\phi \left( t \right)\left( {k - cA} \right)}}{{A\left( {k - c\phi \left( t \right)} \right)}}} \right| = t
\end{array}
\]由上述結果不難求解 $\phi(t)$ 如下
\[\begin{array}{l}
\phi \left( t \right) = \frac{{kA{e^{kt}}}}{{\left( {k - cA} \right) + cA{e^{kt}}}}\\
\Rightarrow \phi \left( t \right) = \frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}}
\end{array}\]自此我們求解完畢，讀者可自行驗證上述解 $\phi(t)$ 確實滿足 Logistic Equaiton 與初始條件。
Comments:
1. 若 $c = 0$，我們可得
\[{\left. {\phi \left( t \right)} \right|_{c = 0}} = {\left. {\frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}}} \right|_{c = 0}} = A{e^{kt}}\]亦即滿足 $y' = ky$ 之解。
2. 若 $c \neq 0$ 且 $A \neq 0$ 則我們可推得系統其中的一個穩態解
\[\mathop {\lim }\limits_{t \to \infty } \phi \left( t \right) = \mathop {\lim }\limits_{t \to \infty } \frac{{kA}}{{\left( {k - cA} \right){e^{ - kt}} + cA}} = \frac{k}{c}\]
3. 若 初始條件 $y(0) = A = 0$ 則 $\phi(t) = 0$ 為第二個穩態解
4. 一般我們稱邏輯函數 (Logistic Function) 為
\[L\left( t \right) = \frac{1}{{1 + {e^{ - t}}}}\]讀者可驗證其函數圖形具有 $S$ 形。現在注意到我們上述所求得的解 $\phi(t)$ 形式具備此邏輯函數的形式，故其 ODE
\[
\frac{dy}{dt} = ky - cy^2
\]我們稱其為 Logistic Equation (of Population Growth)
2016年3月8日 星期二
[凸分析] 凸集合 與 凸包
Definition: Convex Set
我們說一個集合 $C \subset \mathbb{R}^k$ 為 凸集合 ( convex set )若下列條件成立：
給定任意 $c^1, c^2 \in C$ 且 $\lambda \in [0,1]$ 則 $\lambda c^1 + (1-\lambda)c^2 \in C$
另外我們稱 $\lambda c^1 + (1-\lambda)c^2 $ 為 $c^1, c^2$ 所成的凸組合 ( convex combination )
Comments:
1. 事實上 凸組合 即為 線性組合(linear combination) 但係數必須為非負，且係數之合必須為 $1$
2. 上述集合 $C$ 可為向量空間。
3. 上述集合 $C$ 若為空集合，亦即 $C = \emptyset$ 則 $C$ 視為 convex set 。
4. 一般而言，凸組合可推廣至如下定義：我們稱 $c^1,...,c^m$ 的凸組合為
\[
\lambda_1 c^1 + ... + \lambda_m c^m
\]其中 $\lambda_1 + ... + \lambda_m = 1$。在應用數學中，我們可將 $\lambda_i$ 視為 機率 或者某向量 $c^i $ 佔整體的成分比率。
Example:
1. $\mathbb{R}^n$ 空間為 convex set
2. 過點 $x_0 \in \mathbb{R}^n$，延方向 $d \in \mathbb{R}^n$ 的直線
\[
l := \{x \in \mathbb{R}^n: x = x_0 + t d, \;\; t \in \mathbb{R}\}
\]
以下為 convex set 的一些基本但常用的性質
=================
Proposition: 令 $V$ 為向量空間，且 $K$ 與 $G$ 為 $V$ 上的兩 convex sets，則
1. 對任意 $\alpha \in \mathbb{R}$ ， $\alpha K := \{x: x=\alpha k, k\in K\}$ 為 convex set。
2. $K+G$ 為 convex set，其中
\[
K+G := \{k+g: k \in K, g\in G\}
\]=================
Proof: 1: 給定 $\alpha \in \mathbb{R}$，欲證 $\alpha K$ 為 convex，故令 $x_1, x_2 \in \alpha K$ 且 $\lambda \in [0,1]$，則存在 $k_1, k_2 \in K$ 我們有 $x_1 = \alpha k_1$ 與 $x_2 = \alpha k_2$，故我們僅需證明
\[
\lambda x_1 + (1-\lambda ) x_2 \in \alpha K
\] 現在觀察
\[\begin{array}{l}
\lambda {x_1} + (1 - \lambda ){x_2} = \lambda \alpha {k_1} + (1 - \lambda )\alpha {k_2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \alpha \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right)
\end{array}
\]由於 $k_1, k_2 \in K$ 且 $K$ 為 convex 故
\[\alpha \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) \in \alpha K
\]
Proof: 2: 令 $C:= K+G$，現在我們欲證 $C $ 為 convex，故令 $x_1, x_2 \in C$ 且 $\lambda \in [0,1]$，則存在 $k_1, k_2 \in K$ 與 $g_1, g_2 \in G$ 使得我們有 $x_1 =k_1+g_1$ 與 $x_2 = k_2 + g_2$，故我們僅需證明
\[
\lambda x_1 + (1-\lambda ) x_2 \in Z
\] 現在觀察
\[\begin{array}{l}
\lambda {x_1} + (1 - \lambda ){x_2} = \lambda \left( {{k_1} + {g_1}} \right) + (1 - \lambda )\left( {{k_2} + {g_2}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) + \left( {\lambda {g_1} + (1 - \lambda ){g_2}} \right)
\end{array}\]由於 $k_1, k_2 \in K$ 且 $g_1, g_2 \in G$ 且 $K,G$ 為 convex 故
\[\left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) + \left( {\lambda {g_1} + (1 - \lambda ){g_2}} \right) \in Z = G+K\;\;\;\; \square
\]
Proposition: 令 $\cal C$ 為任意 convex sets 所成的集合，則對其中任意的 convex sets 取任意交集 \[
\bigcap_{K \in \mathcal{C}} K
\]仍為 convex
Proof: 令 $C:= \bigcap_{K \in \mathcal{C} } K$。若 $C = \emptyset$ 則上述 Proposition 自動滿足。
若 $C \neq \emptyset$ 則我們要證明 $ C = \bigcap_{K \in \mathcal{C}} K $ 為 convex，故令 $x_1, x_2 \in C$ 且 $\lambda \in [0,1]$，則對任意 $K \in \mathcal{C}$，我們可知 $x_1, x_2 \in K$ 。且由於 $K$ 為 convex， 故對任意 $K \in \mathcal{C}$ 而言，我們有
\[
\lambda x_1 + (1- \lambda)x_2 \in K
\]由上述結果我們可立即推知 $\lambda x_1 + (1- \lambda)x_2 \in C$，也就是說 $C$ 為 convex。$\square$
Definition: Half-Spaces
給定任意非零向量 $b \in \mathbb{R}^n$ 且 任意常數 $\beta \in \mathbb{R}^1$，我們稱
\[
\{ x : x^T b \le \beta\};\;\;\;\; \{ x : x^T b \ge \beta\}
\]為 閉 半空間 (Closed Half-Spaces)。同理我們稱
\[
\{ x: x^T b <\beta \};\;\;\;\; \{ x: x^T b >\beta\}
\]為 開半空間 (Closed Half-Spaces)。
FACT: 半空間為 convex set。
Proof: omitted
Theorem:
令 $b_i \in \mathbb{R}^n$ 且 $\beta_i \in \mathbb{R}^1$ 對 $i \in I$ 其中 $I$ 為任意 index set。則
\[
C :=\{ x \in \mathbb{R}^n : x^T b_i \le \beta_i, \;\; \forall \; i \in I\}
\]為 convex
上述定理對所有不等式與等式 $\leq, \geq, >, <, =$皆成立，故我們可推論具有 $n$ 變數的 任意線性不等式所構成的集合皆為 convex set。
有了上述結果，我們可以進一步介紹所謂的凸包 (Convex Hull)：
=================
Definition: Convex Hull
給定集合 $C \subset \mathbb{R}^k$ ，則我們稱此集合的 凸包 (convex hull)，記作 $conv (C)$，為包含集合 $C$ 的最小 convex set ，亦即若 $\cal C^+$ 為所有包含 $C$ 的 convex set 所成的集合，則
\[
conv (C) := \bigcap_{C^+ \in \mathcal{C^+}} C^+
\]=================
Comments:
1. 若上述定義中給定的集合 $C$ 已經為 convex set 則 $conv C = C$
2. $conv (C) \supset C$
3. 給定有限點 $p^1,p^2,...,p^m$，則其所成的集合 $\{p^1,p^2,...,p^m\}$ 可用來產生凸包，寫作 $conv\{p^i\}$ 且 $\{p^1,p^2,...,p^m\}$ 稱為 set of generators
4. 上述 convex hull 可以透過給定 set of generators $\{p^1,p^2,...,p^m\}$，用 MATLAB 指令 convhull 來產生，以下我們引用 MATLAB 程式碼透過隨機產生一組 $\{p_1, ..., p_{20}\}$ 並利用此 20個點 來長出 convex hull
MATLAB CODE:
x = rand(20,1);
y = rand(20,1);
plot(x,y, 'o');
k = convhull(x,y)
hold on, plot(x(k), y(k), '-r')
執行之後結果如下圖
接著我們介紹 Polytopes 與 Polygons
Definition: Polytope
集合 $P \subset \mathbb{R}^k$ 稱為一個 polytope 若
1. $P$ 為 透過有限點 $\{p^1,p^2,...,p^m\}$ 所產生的 convex hull，亦即
\[
P := conv\{p^i\}
\]
下圖顯示了在 $\mathbb{R}^2$ 空間中的 Polytope 的例子
Comments:
1. 在 $\mathbb{R}^2$ 空間中的 polytope，在數學上另外給一個名字稱其為 (convex) polygon
2. 由 Polytope 定義可知， Polytope 與 Convex Polygon 皆為 convex set
極限點
令 $P = conv\{p^i\} $ 為 $\mathbb{R}^k$ 中的 polytope，則我們稱點 $p \in P$ 為 $P$中的一個極限點 (extreme point) 若下列條件成立：
如果 $p$ 無法被其他 $P$ 中相異的點用 convex combination 表示。
Comments:
1. 由上述極限點定義可知，對任意 polytope $P$而言，給定set of generators $\{p^i\}$ $i=1,2.,...,m$ 則 $P$ 極限點所成的集合必為 set of generators 的子集
2. 極限點所成的集合稱為 minimal generating set。
3. 在線性規劃問題中， Polytope 多半透過有限多組線性不等式 $A{\bf x} \le {\bf b}$ 表示。
給定 Polytope $P=conv\{p^1, p^2,...,p^m\}$ 則任意點 $p \in P$ 都可透過 $p^i$ 用 convex combination 表示，亦即存在實數 $\lambda_1,\lambda_2,...,\lambda_m \ge 0$ 使得 $\sum_{i=1}^m \lambda_i =1$ 與
\[
p = \sum_{i=1}^m \lambda_i p^i
\]
Definition: Unit Simplex
令
\[
\Lambda := \left \{\lambda \in {\mathbb{R}^m}:{\lambda _i} \ge 0,\;\; i = 1,2,...,m,\;\;\sum\limits_{i = 1}^m {{\lambda _i} = 1}\right \}\]
Theorem: Cartheodory's Theorem
令 $P$ 為 $\mathbb{R}^k$ 中的 polytope，則其中任意一點 $p \in P \subset \mathbb{R}^k$皆可透過最多 $k+1$ 個極限點用 convex combination 表示。
我們說一個集合 $C \subset \mathbb{R}^k$ 為 凸集合 ( convex set )若下列條件成立：
給定任意 $c^1, c^2 \in C$ 且 $\lambda \in [0,1]$ 則 $\lambda c^1 + (1-\lambda)c^2 \in C$
另外我們稱 $\lambda c^1 + (1-\lambda)c^2 $ 為 $c^1, c^2$ 所成的凸組合 ( convex combination )
Comments:
1. 事實上 凸組合 即為 線性組合(linear combination) 但係數必須為非負，且係數之合必須為 $1$
2. 上述集合 $C$ 可為向量空間。
3. 上述集合 $C$ 若為空集合，亦即 $C = \emptyset$ 則 $C$ 視為 convex set 。
4. 一般而言，凸組合可推廣至如下定義：我們稱 $c^1,...,c^m$ 的凸組合為
\[
\lambda_1 c^1 + ... + \lambda_m c^m
\]其中 $\lambda_1 + ... + \lambda_m = 1$。在應用數學中，我們可將 $\lambda_i$ 視為 機率 或者某向量 $c^i $ 佔整體的成分比率。
Example:
1. $\mathbb{R}^n$ 空間為 convex set
2. 過點 $x_0 \in \mathbb{R}^n$，延方向 $d \in \mathbb{R}^n$ 的直線
\[
l := \{x \in \mathbb{R}^n: x = x_0 + t d, \;\; t \in \mathbb{R}\}
\]
以下為 convex set 的一些基本但常用的性質
=================
Proposition: 令 $V$ 為向量空間，且 $K$ 與 $G$ 為 $V$ 上的兩 convex sets，則
1. 對任意 $\alpha \in \mathbb{R}$ ， $\alpha K := \{x: x=\alpha k, k\in K\}$ 為 convex set。
2. $K+G$ 為 convex set，其中
\[
K+G := \{k+g: k \in K, g\in G\}
\]=================
Proof: 1: 給定 $\alpha \in \mathbb{R}$，欲證 $\alpha K$ 為 convex，故令 $x_1, x_2 \in \alpha K$ 且 $\lambda \in [0,1]$，則存在 $k_1, k_2 \in K$ 我們有 $x_1 = \alpha k_1$ 與 $x_2 = \alpha k_2$，故我們僅需證明
\[
\lambda x_1 + (1-\lambda ) x_2 \in \alpha K
\] 現在觀察
\[\begin{array}{l}
\lambda {x_1} + (1 - \lambda ){x_2} = \lambda \alpha {k_1} + (1 - \lambda )\alpha {k_2}\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}
\end{array} = \alpha \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right)
\end{array}
\]由於 $k_1, k_2 \in K$ 且 $K$ 為 convex 故
\[\alpha \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) \in \alpha K
\]
Proof: 2: 令 $C:= K+G$，現在我們欲證 $C $ 為 convex，故令 $x_1, x_2 \in C$ 且 $\lambda \in [0,1]$，則存在 $k_1, k_2 \in K$ 與 $g_1, g_2 \in G$ 使得我們有 $x_1 =k_1+g_1$ 與 $x_2 = k_2 + g_2$，故我們僅需證明
\[
\lambda x_1 + (1-\lambda ) x_2 \in Z
\] 現在觀察
\[\begin{array}{l}
\lambda {x_1} + (1 - \lambda ){x_2} = \lambda \left( {{k_1} + {g_1}} \right) + (1 - \lambda )\left( {{k_2} + {g_2}} \right)\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}
\end{array} = \left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) + \left( {\lambda {g_1} + (1 - \lambda ){g_2}} \right)
\end{array}\]由於 $k_1, k_2 \in K$ 且 $g_1, g_2 \in G$ 且 $K,G$ 為 convex 故
\[\left( {\lambda {k_1} + (1 - \lambda ){k_2}} \right) + \left( {\lambda {g_1} + (1 - \lambda ){g_2}} \right) \in Z = G+K\;\;\;\; \square
\]
Proposition: 令 $\cal C$ 為任意 convex sets 所成的集合，則對其中任意的 convex sets 取任意交集 \[
\bigcap_{K \in \mathcal{C}} K
\]仍為 convex
Proof: 令 $C:= \bigcap_{K \in \mathcal{C} } K$。若 $C = \emptyset$ 則上述 Proposition 自動滿足。
若 $C \neq \emptyset$ 則我們要證明 $ C = \bigcap_{K \in \mathcal{C}} K $ 為 convex，故令 $x_1, x_2 \in C$ 且 $\lambda \in [0,1]$，則對任意 $K \in \mathcal{C}$，我們可知 $x_1, x_2 \in K$ 。且由於 $K$ 為 convex， 故對任意 $K \in \mathcal{C}$ 而言，我們有
\[
\lambda x_1 + (1- \lambda)x_2 \in K
\]由上述結果我們可立即推知 $\lambda x_1 + (1- \lambda)x_2 \in C$，也就是說 $C$ 為 convex。$\square$
Definition: Half-Spaces
給定任意非零向量 $b \in \mathbb{R}^n$ 且 任意常數 $\beta \in \mathbb{R}^1$，我們稱
\[
\{ x : x^T b \le \beta\};\;\;\;\; \{ x : x^T b \ge \beta\}
\]為 閉 半空間 (Closed Half-Spaces)。同理我們稱
\[
\{ x: x^T b <\beta \};\;\;\;\; \{ x: x^T b >\beta\}
\]為 開半空間 (Closed Half-Spaces)。
FACT: 半空間為 convex set。
Proof: omitted
Theorem:
令 $b_i \in \mathbb{R}^n$ 且 $\beta_i \in \mathbb{R}^1$ 對 $i \in I$ 其中 $I$ 為任意 index set。則
\[
C :=\{ x \in \mathbb{R}^n : x^T b_i \le \beta_i, \;\; \forall \; i \in I\}
\]為 convex
上述定理對所有不等式與等式 $\leq, \geq, >, <, =$皆成立，故我們可推論具有 $n$ 變數的 任意線性不等式所構成的集合皆為 convex set。
有了上述結果，我們可以進一步介紹所謂的凸包 (Convex Hull)：
=================
Definition: Convex Hull
給定集合 $C \subset \mathbb{R}^k$ ，則我們稱此集合的 凸包 (convex hull)，記作 $conv (C)$，為包含集合 $C$ 的最小 convex set ，亦即若 $\cal C^+$ 為所有包含 $C$ 的 convex set 所成的集合，則
\[
conv (C) := \bigcap_{C^+ \in \mathcal{C^+}} C^+
\]=================
Comments:
1. 若上述定義中給定的集合 $C$ 已經為 convex set 則 $conv C = C$
2. $conv (C) \supset C$
3. 給定有限點 $p^1,p^2,...,p^m$，則其所成的集合 $\{p^1,p^2,...,p^m\}$ 可用來產生凸包，寫作 $conv\{p^i\}$ 且 $\{p^1,p^2,...,p^m\}$ 稱為 set of generators
4. 上述 convex hull 可以透過給定 set of generators $\{p^1,p^2,...,p^m\}$，用 MATLAB 指令 convhull 來產生，以下我們引用 MATLAB 程式碼透過隨機產生一組 $\{p_1, ..., p_{20}\}$ 並利用此 20個點 來長出 convex hull
MATLAB CODE:
x = rand(20,1);
y = rand(20,1);
plot(x,y, 'o');
k = convhull(x,y)
hold on, plot(x(k), y(k), '-r')
執行之後結果如下圖
Convex Hull Example
Definition: Polytope
集合 $P \subset \mathbb{R}^k$ 稱為一個 polytope 若
1. $P$ 為 透過有限點 $\{p^1,p^2,...,p^m\}$ 所產生的 convex hull，亦即
\[
P := conv\{p^i\}
\]
下圖顯示了在 $\mathbb{R}^2$ 空間中的 Polytope 的例子
Comments:
1. 在 $\mathbb{R}^2$ 空間中的 polytope，在數學上另外給一個名字稱其為 (convex) polygon
2. 由 Polytope 定義可知， Polytope 與 Convex Polygon 皆為 convex set
極限點
令 $P = conv\{p^i\} $ 為 $\mathbb{R}^k$ 中的 polytope，則我們稱點 $p \in P$ 為 $P$中的一個極限點 (extreme point) 若下列條件成立：
如果 $p$ 無法被其他 $P$ 中相異的點用 convex combination 表示。
Comments:
1. 由上述極限點定義可知，對任意 polytope $P$而言，給定set of generators $\{p^i\}$ $i=1,2.,...,m$ 則 $P$ 極限點所成的集合必為 set of generators 的子集
2. 極限點所成的集合稱為 minimal generating set。
3. 在線性規劃問題中， Polytope 多半透過有限多組線性不等式 $A{\bf x} \le {\bf b}$ 表示。
給定 Polytope $P=conv\{p^1, p^2,...,p^m\}$ 則任意點 $p \in P$ 都可透過 $p^i$ 用 convex combination 表示，亦即存在實數 $\lambda_1,\lambda_2,...,\lambda_m \ge 0$ 使得 $\sum_{i=1}^m \lambda_i =1$ 與
\[
p = \sum_{i=1}^m \lambda_i p^i
\]
Definition: Unit Simplex
令
\[
\Lambda := \left \{\lambda \in {\mathbb{R}^m}:{\lambda _i} \ge 0,\;\; i = 1,2,...,m,\;\;\sum\limits_{i = 1}^m {{\lambda _i} = 1}\right \}\]
Theorem: Cartheodory's Theorem
令 $P$ 為 $\mathbb{R}^k$ 中的 polytope，則其中任意一點 $p \in P \subset \mathbb{R}^k$皆可透過最多 $k+1$ 個極限點用 convex combination 表示。
2016年3月4日 星期五
[隨筆] 關於朋友
今天走在路上特別想到的一個問題：人與人之間如何才會變成朋友？或許彼此之間有相同興趣，相同喜好，或者有某些共同人格特點。我認為過程大概是這樣的：在某個當下，有那麼一個人出現在某個特定情境，你們彼此共同經歷了一些事情，也許過程有苦有樂，然後最後很幸運的，他成為了你的朋友。
但是，有沒有可能 同樣 的一個人，我們讓他在不同時間與不同場景出現，也許 你 與 這個同一個人 就不再是朋友，甚至你們根本不可能是朋友。對嗎？ 因為人會變，一個人所經歷的人事物 會 漸漸改變 他看事情的角度，喜好，思想以及習慣。
如果在不同時間點相遇的你們已經沒有了共同興趣，或者共同喜好，那麼要變成彼此的朋友可能就變得困難。當我越這樣想的時候，越發現人與人之間能成為彼此朋友，或者能成為一生的朋友實在是一件非常奇妙的事情，因為這大概只能發生在對的時間與對的人才有可能。
願我們都能 好好珍惜彼此身邊的朋友。
但是，有沒有可能 同樣 的一個人，我們讓他在不同時間與不同場景出現，也許 你 與 這個同一個人 就不再是朋友，甚至你們根本不可能是朋友。對嗎？ 因為人會變，一個人所經歷的人事物 會 漸漸改變 他看事情的角度，喜好，思想以及習慣。
如果在不同時間點相遇的你們已經沒有了共同興趣，或者共同喜好，那麼要變成彼此的朋友可能就變得困難。當我越這樣想的時候，越發現人與人之間能成為彼此朋友，或者能成為一生的朋友實在是一件非常奇妙的事情，因為這大概只能發生在對的時間與對的人才有可能。
願我們都能 好好珍惜彼此身邊的朋友。
訂閱：
文章 (Atom)