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

$\mathbf{x},\mathbf{y}\in S\cap T$を任意にとり、$\alpha \in [0,1]$を任意にとる。示すべきは
$$(1-\alpha )\mathbf{x}+\alpha \mathbf{y}\in S\cap T$$
である。
$\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$となる。
したがって
$$(1-\alpha )\mathbf{x}+\alpha \mathbf{y}\in S\cap T$$
が言えて、補題が示された。

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

$\mathbf{x},\mathbf{y}\in \bigcap _{\lambda \in \mathrm{\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 }$となる。したがって
$$(1-\alpha )\mathbf{x}+\alpha \mathbf{y}\in \bigcap _{\lambda \in \mathrm{\Lambda }}{S}_{\lambda }$$
が言えて、補題が示された。

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

定理の右辺で表される集合を$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$の制約に従う。すると
$$(1-\lambda )\mathbf{x}+\lambda \mathbf{y}=\sum _{l=1}^L{\gamma }_l{\mathbf{z}}_l$$
のように書ける。ただし$L=M+N$であり、
$$\{{\gamma }_1,{\gamma }_2,,\dots ,{\gamma }_L\}=\{(1-\lambda ){\alpha }_1,(1-\lambda ){\alpha }_2,,\dots ,(1-\lambda ){\alpha }_M,\lambda {\beta }_1,\lambda {\beta }_2,,\dots ,\lambda {\beta }_N\}$$
である。各${\mathbf{z}}_l$は${\mathbf{x}}_i$か${\mathbf{y}}_j$のいずれかであり${\mathbf{z}}_l\in S$である。また各${\gamma }_l\ge 0$であることも明らかである。さらに
$$\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$$
をも満たしている。よって$\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,\dots ,{\mathbf{x}}_N\in S$について、その凸結合が$\mathrm{conv}(S)$に属すると仮定する。このとき任意の$N+1$個の点${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_N,{\mathbf{x}}_{N+1}\in S$の凸結合が$\mathrm{conv}(S)$に属することを示したい。
  いま、${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_N,{\mathbf{x}}_{N+1}$の凸結合が
  $$\sum _{i=1}^{N+1}{\alpha }_i{\mathbf{x}}_i$$
  と書けたとする。ただし${\alpha }_i\ge 0(i=1,2,\dots ,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\le {\alpha }_{N+1}<1$と仮定する。
  上記の凸結合の式を変形すると
  $$\begin{array}{rcl}\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{array}$$
  を得る。$\sum _{i=1}^{N+1}{\alpha }_i=1$であるから$\sum _{i=1}^N{\alpha }_i=1-{\alpha }_{N+1}$であり、両辺を$1-{\alpha }_{N+1}>0$で割ると
  $$\sum _{i=1}^N\frac{{\alpha }_i}{1-{\alpha }_{N+1}}=1$$
  である。また$\frac{{\alpha }_i}{1-{\alpha }_{N+1}}\ge 0$は仮定より明らかである。ゆえに
  $$\sum _{i=1}^N\frac{{\alpha }_i}{1-{\alpha }_{N+1}}{\mathbf{x}}_i$$
  は凸結合であり、帰納法の仮定から$\mathrm{conv}(S)$に属する。よって
  $$(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}$$
  は二つの$\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,\dots ,{\mathbf{x}}_K\in S$について、その凸結合が$\mathrm{conv}(S)$に含まれることが示された。(i)と(ii)により$\mathrm{conv}(S)=R$がいえて、証明が終わる。

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

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

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

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