2016年10月18日 星期二

[凸分析] 集合上的 廣義直徑

 Definition: 令 $S \subset \mathbb{R}^n$ 則 $S$ 的 廣義直徑(generalized diameter) ,符號記作 $diam S$ 定義為
\[
diam S := \sup \{||x-y||: x,y \in S\}
\]

Comments:
如果上述集合為空集,則 $diam S = -\infty$

===================
Theorem:
若 $S \subset \mathbb{R}^n$ 則
\[
diam S = diam \; conv S
\]===================

Proof:
令 $S \subset \mathbb{R}^n$,我們要證明 $diam S = diam conv S$。故我們先證明
\[
diam S \leq diam \; cont S\;\;\;\;\; (*)
\]因為 $conv S \supset S$ 故由 廣義直徑的定義可知,上述不等式自動成立。接著我們證明
\[
diam S \geq diam \; conv S
\]現在任取 $x,y \in conv S$ , 則由 convex hull 的性質可知 存在 $x_i, y_i \in S$ 與 $\mu_i, \lambda_i \geq 0$ 且 $\sum_i \mu_i = \sum_j \lambda_j = 1$ 使得
\[
x = \sum_i^n \mu_i x_i; \;\;\; y = \sum_i^k \lambda_i y_i
\]現在我們觀察
\begin{align*}
  \left\| {x - y} \right\| &= \left\| {\sum\limits_i^n {{\mu _i}} {x_i} - \sum\limits_i^k {{\lambda _i}} {y_i}} \right\| \hfill \\
   &= \left\| {\sum\limits_i^n {{\mu _i}} \left( {\sum\limits_i^k {{\lambda _i}} } \right){x_i} - \sum\limits_i^k {{\lambda _i}} \left( {\sum\limits_i^n {{\mu _i}} } \right){y_i}} \right\| \hfill \\
   &= \left\| {\sum\limits_i^n {{\mu _i}} \sum\limits_i^k {{\lambda _i}} \left( {{x_i} - {y_i}} \right)} \right\| \hfill \\
  & \leqslant \sum\limits_i^n {{\mu _i}} \sum\limits_i^k {{\lambda _i}} \left\| {{x_i} - {y_i}} \right\| \hfill \\
  & \leqslant \sum\limits_i^n {{\mu _i}} \left( {\sum\limits_i^k {{\lambda _i}} } \right)diamS = diamS \hfill \\
\end{align*}
由於 $x,y$ 為任取,我們得到 $diam S \geq diam \; conv S \;\;\;\; (**)$。合併 $(*)$ 與 $(**)$ 我們可得 \[
diam S = diam \; conv S
\]