『機械学習のための連続最適化』 補題2.10の証明

$\mathbf{x}, \mathbf{y}\in S\cap T$を任意にとり、$\alpha \in [0, 1]$を任意にとる。示すべきは
\begin{equation} (1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in S \cap T \end{equation}
である。
$\mathbf{x}, \mathbf{y}\in S$であるから、$S$は凸集合という仮定より$(1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in S$となる。また$\mathbf{x}, \mathbf{y}\in T$であるから、$T$は凸集合という仮定より$(1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in T$となる。
したがって
\begin{equation} (1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in S \cap T \end{equation}
が言えて、補題が示された。

補題1を繰り返し用いると、3つの凸集合についてその共通部分が凸集合であることがいえる。つまり$R$, $S$, $T$をそれぞれ凸集合とすれば$R\cap S$が凸集合であり、$(R\cap S) \cap T$が凸集合であることが補題1からいえる。以降、4つの凸集合の共通部分、5つの凸集合の共通部分、のように同様の手続きを$\Lambda$の要素数（＝濃度）まで繰り返せば補題が示される。

$\mathbf{x}, \mathbf{y}\in \bigcap_{\lambda\in\Lambda} S_{\lambda}$を任意にとり、$\alpha \in [0, 1]$を任意にとる。各$\lambda$について、$\mathbf{x}, \mathbf{y}\in S_\lambda$であるから、$S_\lambda$は凸集合という仮定より$(1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in S_\lambda$となる。したがって
\begin{equation} (1-\alpha)\mathbf{x} + \alpha \mathbf{y} \in \bigcap_{\lambda\:\in\:\Lambda} S_\lambda \end{equation}
が言えて、補題が示された。

$\mathcal{C}$に属する各集合は$S$を含むから、右辺もまた$S$を含む。補題1から4により、右辺もまた凸集合である。したがって凸包の最小性により
\begin{equation} \mathrm{conv}(S) \subset \bigcap_{\lambda\: \in\: \Lambda} T_{\lambda} \end{equation}
が成り立つ。一方、凸包もまた$S$を含む凸集合であるから$\mathrm{conv}(S) \in \mathcal{C}$である。つまりある$\lambda^{\prime} \in \Lambda$が存在して$\mathrm{conv}(S) = T_{\lambda^{\prime}}$である。ゆえに、
\begin{equation} \bigcap_{\lambda\: \in\: \Lambda} T_{\lambda} \subset \mathrm{conv}(S) \end{equation}
が成り立つ。よって補題は示された。

定理の右辺で表される集合を$R$とする。$\mathrm{conv}(S)=R$を示したい。

(i)$\mathrm{conv}(S)\subset R$について：
$S\subset R$は明らかである（$K=1$）。$R$が凸集合であることを示せば、$\mathrm{conv}(S)$の最小性により$\mathrm{conv}(S)\subset R$が言える。以下はその証明である。

$\mathbf{x},$ $\mathbf{y}$をそれぞれ$R$の元とし，$\lambda \in [0, 1]$とする。$(1-\lambda)\mathbf{x} + \lambda \mathbf{y} \in R$を示したい。
まず$\mathbf{x} = \sum_{i=1}^{M}\alpha_i \mathbf{x}_i$と$\mathbf{y} = \sum_{j=1}^{N}\beta_j \mathbf{y}_j$としてそれぞれの凸結合の表現を得る。各$\alpha_i,\;\beta_{j},\;\mathbf{x}_i,\;\mathbf{y}_j$は$R$の制約に従う。すると
\begin{equation} (1-\lambda)\mathbf{x} + \lambda \mathbf{y} = \sum_{l=1}^{L} \gamma_{l}\mathbf{z}_l \end{equation}
のように書ける。ただし$L=M+N$であり、
\begin{equation} \{\gamma_1,\; \gamma_2,\;, \ldots,\; \gamma_L\} = \{(1-\lambda)\alpha_1,\; (1-\lambda)\alpha_2,\;, \ldots,\; (1-\lambda)\alpha_M, \; \lambda\beta_1,\; \lambda\beta_2,\;, \ldots,\; \lambda\beta_N\} \end{equation}
である。各$\mathbf{z}_l$は$\mathbf{x}_i$か$\mathbf{y}_j$のいずれかであり$\mathbf{z}_l\in S$である。また各$\gamma_l \geq 0$であることも明らかである。さらに
\begin{equation} \sum_{l=1}^{L}\gamma_l = (1-\lambda)\sum_{i=1}^{M} \alpha_i + \lambda\sum_{j=1}^{N}\beta_j= (1-\lambda) \cdot 1 + \lambda \cdot 1 = 1 \end{equation}
をも満たしている。よって$\sum_{l=1}^{L} \gamma_{l}\mathbf{z}_l$は凸結合であり、$(1-\lambda)\mathbf{x} + \lambda \mathbf{y}$は$R$の元であることがわかった。

(ii)$R \subset \mathrm{conv}(S)$について：
$K$についての数学的帰納法により示す。

• $K=1$のとき
  任意の$\mathbf{x}\in S$がまた$\mathbf{x}\in \mathrm{conv}(S)$を満たすことは明らかである。

• $K=N$のとき成り立つと仮定する。
  すなわち、任意の$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N \in S$について、その凸結合が$\mathrm{conv}(S)$に属すると仮定する。このとき任意の$N+1$個の点$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N, \mathbf{x}_{N+1} \in S$の凸結合が$\mathrm{conv}(S)$に属することを示したい。
  いま、$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N, \mathbf{x}_{N+1}$の凸結合が
  \begin{equation} \sum_{i=1}^{N+1}\alpha_i \mathbf{x}_i \end{equation}
  と書けたとする。ただし$\alpha_{i} \geq 0\;(i=1, 2, \ldots, N+1)$であり$\sum_{i=1}^{N+1}\alpha_i = 1$である。もし$\alpha_{N+1}=1$ならば、ほかの$\alpha_i$は$0$になってしまうが、$1\cdot \mathbf{x}_{N+1} = \mathbf{x}_{N+1} \in S$となるから$K=N+1$のときも成り立つ。よって以降は$0\leq \alpha_{N+1} < 1$と仮定する。
  上記の凸結合の式を変形すると
  \begin{eqnarray} \sum_{i=1}^{N+1}\alpha_i \mathbf{x}_i &=& \sum_{i=1}^{N}\alpha_i \mathbf{x}_i + \alpha_{N+1}\mathbf{x}_{N+1} \\ &=& (1-\alpha_{N+1})\sum_{i=1}^{N}\frac{\alpha_i}{1-\alpha_{N+1}}\mathbf{x}_i + \alpha_{N+1}\mathbf{x}_{N+1} \end{eqnarray}
  を得る。$\sum_{i=1}^{N+1}\alpha_i = 1$であるから$\sum_{i=1}^{N}\alpha_i = 1 - \alpha_{N+1}$であり、両辺を$1 - \alpha_{N+1} > 0$で割ると
  \begin{equation} \sum_{i=1}^{N}\frac{\alpha_i}{1-\alpha_{N+1}} = 1 \end{equation}
  である。また$\frac{\alpha_i}{1-\alpha_{N+1}} \geq 0$は仮定より明らかである。ゆえに
  \begin{equation} \sum_{i=1}^{N}\frac{\alpha_i}{1-\alpha_{N+1}}\mathbf{x}_i \end{equation}
  は凸結合であり、帰納法の仮定から$\mathrm{conv}(S)$に属する。よって
  \begin{equation} (1-\alpha_{N+1})\sum_{i=1}^{N}\frac{\alpha_i}{1-\alpha_{N+1}}\mathbf{x}_i + \alpha_{N+1}\mathbf{x}_{N+1} \end{equation}
  は二つの$\mathrm{conv}(S)$の点に関する凸結合であり、$\mathrm{conv}(S)$に属することがいえる。なぜならば$K=1$のとき$\mathbf{x}_{N+1}$は$\mathrm{conv}(S)$の点であり、$\mathrm{conv}(S)$はその定義により凸集合である（$\because$$K=2$のときの凸結合は凸集合の定義そのもの）。

以上により、任意の$K\in \mathbb{N}$と任意の$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_K \in S$について、その凸結合が$\mathrm{conv}(S)$に含まれることが示された。(i)と(ii)により$\mathrm{conv}(S)=R$がいえて、証明が終わる。

左辺を$\alpha$、右辺を$\beta$と置く。$\alpha \leq \beta$かつ$\alpha\geq \beta$をそれぞれ示すことで$\alpha=\beta$を証明する方針を取ることにする。

(i)$\alpha \leq \beta$：
$\beta$に関する下限の定義により、任意の実数$\epsilon >0$に対してある$\mathbf{x} \in \mathrm{conv}(S)$が存在し、
\begin{equation} \mathbf{c}^{\top}\mathbf{x} + a < \beta + \epsilon \end{equation}
が成り立つ。このとき補題6により、ある$K \in \mathbb{N}$と$\sum_{i=1}^{K}\gamma_{i} = 1$を満たす実数$\gamma_i \geq 0$（$i=1,2,\ldots, K$）が存在して
\begin{equation} \mathbf{x} = \sum_{i=1}^{K}\gamma_{i}\mathbf{x}_{i}, \end{equation}
と書けるから、
\begin{equation} \sum_{i=1}^{K}\gamma_{i}(\mathbf{c}^{\top}\mathbf{x}_i + a) < \beta + \epsilon \end{equation}
が成り立つ。左辺の各$\mathbf{c}^{\top}\mathbf{x}_i + a$の下限が$\alpha$であるから
\begin{equation} \alpha < \beta + \epsilon \end{equation}
である（$\because$$\sum_{i=1}^{K}\gamma_{i} = 1$）。さて$\epsilon$は任意だったから、特に$n$を自然数として右辺を$b_n = \beta + 1/n$と置いてみる。すると$b_n$は単調減少数列で下に有界だからある極限値に収束するが、これが$\beta$に他ならない。$\alpha$は$\{b_n\}$に対する１つの下界であり、$\beta$は最大下界の意味で$\alpha \leq \beta$が成り立つ。

(ii)$\beta \leq \alpha$：
$\alpha$に関する下限の定義より、任意の実数$\epsilon >0$に対してある$\mathbf{x} \in S$が存在し、
\begin{equation} \mathbf{c}^{\top}\mathbf{x} + a < \alpha + \epsilon \end{equation}
が成り立つ。凸包の定義より$\mathbf{x} \in \mathrm{conv}(S)$であり、左辺の下限が$\beta$であるから
\begin{equation} \beta < \alpha + \epsilon \end{equation}
である。あとは(i)の最後と同じ論法で$\beta \leq \alpha$が示されるわけだが、背理法で示すこともできる。仮に$\beta > \alpha$として$\epsilon = (\beta - \alpha) / 2$としてみる。すると$\beta < \alpha + \epsilon = (\beta + \alpha) / 2 < \beta$となり、矛盾するのである。

以上、(i)と(ii)により、補題2.10が示された。