Proposition 1.3.2（Bertsekas 2009）

Convex Set
定理

非空の凸集合$C$に対して以下が成立する。

(a) $\operatorname{ri}C$ は非空の凸集合であり、$C$と同じアフィン包を持つ。

(b) $m$が $\operatorname{aff}C$ の次元であり、$m > 0$ であれば、ベクトル $x_0, x_1, \dots, x_m \in \operatorname{ri}C$ が存在し、$x_1 - x_0, \dots, x_m - x_0$ が $\operatorname{aff}C$ に平行な部分空間を張る。

方針

(a)　$\operatorname{aff}C$の相対開集合（open relative）$X$を構築する。それが非空であることから$\operatorname{ri}C$が非空であることを導き、$\operatorname{aff}C = \operatorname{aff}X$であることから$\operatorname{aff}(\operatorname{ri}C) = \operatorname{aff}C$を導く。

不明点

(a)　$\operatorname{ri}C$ が非空という条件を用いずに、非空な$m$次元凸集合$C$から$m$個の線型独立なベクトルが存在すること。本稿では、原著に倣い既知の事実としています。

証明

(a)
　$\operatorname{ri}C$ の凸性はTheorem 6.1（Rockafellar 1970）において、$y \in \operatorname{ri}C$とすることで得られる。

（$C$には線型独立なベクトルが$n$個含まれる。）
　$0 \in C$とする。（$0 \notin C$の場合は、適当な$x \in C$だけ並行移動させれば良い。）
$\operatorname{aff}(C)$は$C$を含む部分空間であり、その次元を$m$とする。

　$m = 0$ならば、$C$と$\operatorname{aff}C$は単一の点からならなり、その点は単一の相対的内点となる。
$m > 0$ならば、$C$に含まれる$m$個の線形独立なベクトル$\lbrace z_1, \cdots, z_m \rbrace$が存在し、それらは$\operatorname{aff}C$の基底ベクトルとなる。（不明点で言及した箇所）

（$\operatorname{ri}C$に含まれる$n$次元凸集合$X$の定義）
　以下では、次のような集合$X$を考える。

\begin{aligned} X = \lbrace x \mid x = \sum_{i=1}^m \alpha_i z_i, \sum_{i=1}^m \alpha_i < 1, \alpha_i > 0, i = 1, \dots, m \rbrace \end{aligned}

　$C$は凸集合であり、その定義から $X \subset C$ となる。 このとき、$X$は $\operatorname{aff}C$ の相対開集合（$\exists \epsilon > 0 \quad \text{s.t.} \quad \lbrace x \in B(\bar{x}, \epsilon)\mid B(\bar{x}, \epsilon) \cap \operatorname{aff}C \subset X, \bar{x} \in X \rbrace \neq \emptyset$）となる。（証明は後述）

（非空及び同じアフィン包ことの証明）
　相対開集合であることと$X \subset C$より、$\operatorname{ri}C$は非空であり、$X \subset \operatorname{ri}C$である。
$X, C$は定義よりそのアフィン包は$n$次元凸集合であることから、$\operatorname{aff}C = \operatorname{aff}X$となり、$\operatorname{aff}C \subset \operatorname{aff}(\operatorname{ri}C)$が導ける。 （一致することの理由が正しいかは議論の余地あり）
　また$\operatorname{ri}C \subset C$であることから$\operatorname{aff}C \supset \operatorname{aff}(\operatorname{ri}C)$となるため、$\operatorname{aff}C = \operatorname{aff}(\operatorname{ri}C)$が示される。

（参考：$X$は$C$の相対開集合であることの証明）
　以下を定義する。

\begin{aligned} &B(\bar{x}, \epsilon) = \lbrace x \mid \| x - \bar{x} \| < \epsilon \rbrace \\ &A = \left\lbrace (\alpha_1, \cdots, \alpha_m) \mid \Sigma_i^{m} \alpha_i <1, \alpha_i > 0, i = 1, \cdots,m \right\rbrace \\ &Z = (z_1, \cdots, z_n) \in \mathbb{R}^{n \times m} \end{aligned}

　$\bar{x} \in X, x \in \operatorname{aff}C$となる$x, \bar{x}$について考える。それぞれは基底ベクトルと適切な係数を用いて表現でき、$\bar{x} = Z \bar{\alpha}, x = Z \alpha$とできる。$Z$が線型独立な基底ベクトルから成るため、$Z^{T}Z$が正定値対称行列となり、以下が成立する。

\begin{aligned} \| \bar{x} - x \|^{2} = (\bar{\alpha} - \alpha)^{T} Z^{T} Z (\bar{\alpha} - \alpha) \ge \gamma (\bar{\alpha} - \alpha)^{2} \end{aligned}

　$\bar{x} \in X$であるため、$\bar{\alpha} \in A$となる。$x \in B(\bar{x}, \epsilon)$のとき上式より$\epsilon > \gamma ( \bar{\alpha} - \alpha )^{2}$となることから$\alpha \in A$となり、$x \in X$が導かれる。
　以上を整理すると、$X \subset\operatorname{aff}C$であることから$B(\bar{x}, \epsilon) \cap \operatorname{aff}C$は空集合ではなく、十分小さい$\epsilon$に対して$B(\bar{x}, \epsilon) \cap \operatorname{aff}C \subset X$が成立する。よって相対開集合であることが示された。

(b)
　(a)より$\operatorname{ri}C$は非空であるため、$\exists x_0 \in C$となる。また、その点を中心に摂動を加えた点も$\operatorname{ri}C$に含まれるため、その点を標準基底の係数倍だけ並行移動させて得られるベクトルも含まれることから、$m$個の線形独立なベクトル$\lbrace z_1, \cdots, z_m \rbrace$が存在する。Theorem 6.1（Rockafellar 1970）より$0 \in \operatorname{ri}(C-x_0)$との凸結合を考えると、$\alpha \in (0,1)$に対して$\alpha z_i \in \operatorname{ri}(C-x_0)$が成立する。
　これを$x_0$だけ並行移動させると、$\forall i \ (1 \le i \le m) \quad x_i = x_0 + \alpha z_0 (\in \operatorname{ri}C \subset C)$なり、$x_0, x_1, \cdots, x_m \in \operatorname{ri}C$は示される。
　また$x_i - x_0 = z_i \in \operatorname{ri}(C-x_0)$は$\operatorname{aff}(C-x_0)$を構成する基底ベクトルである。つまり、$x_1-x_0, \cdots, x_n - x_0$は$\operatorname{aff}C$を$x_0$だけ並行移動させた部分空間を張る。

参考文献

Bertsekas, Dimitri. Convex optimization theory. Vol. 1. Athena Scientific, 2009. p24