[凸分析] 凸集合 與 凸包

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$ 個 extreme point 用 convex combination 表示。