相対的内点の存在性

はじめに

この記事では、空でない凸集合 $S \subset \mathbb{R}^n$ について、その相対的内部(relative interior)
$$
\mathrm{ri}(S) := \{ x \in S \mid \exists \varepsilon > 0, B(x, \varepsilon) \cap \mathrm{aff}(S) \subset S \}
$$
が空でないことを証明します。ここで $\mathrm{aff}(S)$ はアフィン包で $S$ を包む最小のアフィン集合のことをいいます。アフィン集合の定義などは以下の記事をご参照ください。

準備

$S \subset \mathbb{R}^n$ と $x \in \mathbb{R}^n$ に対して
$$
S \pm x := \{ y \pm x \mid y \in S \}
$$
と定める。また、$S$ の（ユークリッド位相に関する）内部を $\mathrm{int}(S)$ で表す。

補題1
凸集合 $C \subset \mathbb{R}^n$ に対して、以下は同値。
(1)：$\mathrm{int}(C) \neq \emptyset$
(2)：$\mathrm{aff}(C) = \mathbb{R}^n$

証明
(1)⇒(2)：$x \in \mathrm{int}(C)$ とする。$0 \in \mathrm{int}(S -x)$ となるので、ある $\varepsilon > 0$ が存在して、$\varepsilon \mathbb{e}_j \in C -x ~~(j=1, \dots, n)$ となる。ここで $\mathbb{e}_j$ は 第 $j$ 成分のみ $1$ で、他の成分が $0$ である $\mathbb{R}^n$ の元である。また、アフィン集合の基本性質より、$0 \in S$ のとき $\mathrm{aff}(S) = \mathrm{span}(S)$ となるので
$$
\mathrm{aff}(C) - x = \mathrm{aff}(C - x) = \mathrm{span}(C - x)
$$
となる（ひとつめの等号は $\mathrm{aff}(C)$ が $C$ の元のアフィン結合で表されることからわかる）。以上から $\mathrm{span}(C-x) = \mathbb{R}^n$ となり、$\mathrm{aff}(C) = \mathbb{R}^n + x = \mathbb{R}^n$ を得る。
(2)⇒(1)：$C = \emptyset$ ではありえないことに注意して $x \in C$ を取る。$0 \in C - x$ より
$$
\mathrm{span}(C-x) = \mathrm{aff}(C-x) = \mathrm{aff}(C) - x = \mathbb{R}^n - x = \mathbb{R}^n
$$
となる。したがって、ある $x_1, \dots, x_n \in C - x$ が存在して、$\{ x_1, \dots, x_n \}$ が $\mathbb{R}^n$ の基底となる。いま、各 $j$ について、ある$v_j \in C$ が 存在して $x_j = v_j - x$ となる。そこで、
$$
z = \frac{1}{n+1}(x + v_1 + \cdots + v_n)
$$
とおくと $C$ の凸性より $z \in C$ となる。ここで $z$ が $C$ の内点となることを証明しよう。$c_1, \dots, c_n \in \mathbb{R}$ で $\sum_{j=1} |c_j| \leq 1/(n+1)$ なるものを任意に取る。このとき、
$$
\begin{align}
z + \sum_{j=1}^n c_j x_j
&= \frac{1}{n+1}(x + v_1 + \cdots + v_n) + \sum_{j=1}^n c_j x_j \\
&= \frac{1}{n+1}(x + v_1 + \cdots + v_n) + \sum_{j=1}^n c_j (v_j - x) \\
&= \frac{1}{n+1} \left( \left(1-(n+1)\sum_{j=1}^n c_j \right)x + (1+(n+1)c_1) v_1 + \cdots (1 + (n+1)c_n)v_n \right) \\
\end{align}
$$

となり、右辺の係数はすべて非負で、その総和が $1$ となるので、これは $C$ の元の凸結合である。よって、$C$ の凸性より
$$
z + \left\{ \sum_{j=1}^n \lambda_j x_j \mid \lambda_1, \dots, \lambda_n \in \mathbb{R}, ~ \sum_{j=1}^n |\lambda_j| \leq \frac{1}{n+1} \right\} \subset C \quad (*)
$$
となる。さて、$\{ x_1, \dots, x_n \}$ は $\mathbb{R}^n$ の基底であるので
$$
\| \cdot \|_1 : \mathbb{R}^n \ni y = \sum_{j=1}^n a_j x_j \mapsto \sum_{j=1}^n |a_j|
$$
は weii-defined でノルムを定める。このノルムを使えば、$(*)$ は
$$
z + \left\{ y \in \mathbb{R}^n \mid \| y \|_1 \leq \frac{1}{n+1} \right\} \subset C
$$
と表すことができる。有限次元線形空間上のノルムはすべて同値であるので、ユークリッドノルム $\| \cdot \| $ と上の定めたノルムは同値である。したがって、ある $M > 0$ が存在して、任意の $y \in \mathbb{R}^n$ について
$$
\| y \|_1 \leq M \| y \|
$$
となる。そこで、
$$
B \left(0, \frac{1}{M(n+1)} \right) = \left\{ y \in \mathbb{R}^n \mid \| y \| < \frac{1}{M(n+1)} \right\} \subset \left\{ y \in \mathbb{R}^n \mid \| y \|_1 \leq \frac{1}{n+1} \right\}
$$
となるので、$(*)$ より
$$
B \left(z, \frac{1}{M(n+1)} \right) = z + B \left(0, \frac{1}{M(n+1)} \right) \subset C
$$
を得る。これは $z$ が $C$ の内点であることを示す。

注意
上の証明では (2)⇒(1) の証明にのみ凸性を利用している。

相対的内点の存在性の証明

命題2
空でない凸集合 $S \subset \mathbb{R}^n$ について $\mathrm{ri}(S) \neq \emptyset$ となる。

証明
$S = \{x \}$ となるときは、$\mathrm{aff}(S) = \{ x \}$ であるので、
$$
\mathrm{ri}(S) = \{ y \in S \mid \exists \varepsilon > 0, B(y, \varepsilon) \cap \mathrm{aff}(S) \subset S \} = \{ x \} \neq \emptyset
$$
である。$S$ が2点以上含むとし、$x \in S$ をとる。$C := S - x$ とおくと $0 \in S$ であるので、$\mathrm{aff}(C)$ は $\mathbb{R}^n$ の線形部分空間である。その次元を $d$ とおけば、線形同型写像$f : \mathrm{aff}(C) \rightarrow \mathbb{R}^d$ が取れるので、$f$ の線形性より
$$
\mathbb{R}^d = f(\mathrm{aff}(C)) = \mathrm{aff}(f(C))
$$
を得る。ゆえに補題1より $ \mathrm{int}(f(C)) \neq \emptyset$ となる。したがって、ある $y \in C$ が存在して $f(y) \in \mathrm{int}(f(C))$ となる。この $y$ について $y \in \mathrm{ri}(C)$ が成り立つことを示そう。$f(y) \in \mathrm{int}(f(C))$ であるので、ある $\varepsilon' > 0$ が存在して、
$$
B_d(f(y), \varepsilon') \subset f(C)
$$
となる（$B_d$ は $d$ 次元の開球を表す）。また、$f$ は有限次元空間を定義域とする線形写像なので有界であるため、ある $M > 0$ が存在して、
$$
\| f(z) \| \leq M \| z \| \quad (\forall z \in \mathrm{aff}(C))
$$
となる。そこで $\varepsilon = \varepsilon' / M$ とおくと、任意の$z \in \mathrm{aff}(C) \cap B(y,\varepsilon)$ に対して、
$$
\| f(z) - f(y) || = \| f(z-y) \| \leq M \| z-y \| < \varepsilon'
$$
となる。ゆえに $f(z) \in f(C)$ となり、ある $z' \in C$ について $f(z) = f(z')$ となるため $f$ の単射性より $z = z' \in C$ となる。よって、$y \in \mathrm{ri}(C)$ である。最後に $x + y \in \mathrm{ri}(S)$ を示そう。いま、上で取った $\varepsilon$ について
$$
\mathrm{aff}(S-x) \cap B(y, \varepsilon) \subset S-x
$$
であるので、任意の$z \in \mathrm{aff}(S) \cap B(x+y, \varepsilon)$ について、
$$
z - x \in \mathrm{aff}(S-x) \cap B(y, \varepsilon) \subset S -x
$$
となる。よって、$z \in S$ である。これで示せた。