[凸分析] 支撐函數

以下我們給出凸分析中 常用的函數，稱作 支撐函數 (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})
\]