2016年3月28日 星期一

[控制理論] 具有負實部特徵值之 LTV系統 並不保證系統穩定

考慮線性非時變 (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月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})
\]

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)

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')

執行之後結果如下圖
Convex Hull Example


接著我們介紹 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 表示。