はじめに

最適化理論（凸解析）の勉強をしていると劣微分がよく出てきますが、その存在性については触れられないことも多いです。そこで、この記事では真凸関数 $f:\mathbb{R}^d \rightarrow \mathbb{R} \cup \{\infty\}$ についてその有効定義域 dom$(f)$ の相対的内部 ri$(\mathrm{dom}(f))$ の点 $x$ において劣微分 $\partial f(x)$ が空でないことを真分離定理を使って示します。ここで、関数 $g:\mathbb{R}^d \rightarrow \mathbb{R} \cup \{\infty \}$ について $g$ の有効定義域は
$$
\mathrm{dom}(g) := \{ x \in \mathbb{R}^d \mid g(x) < \infty \}
$$
と定義され、$g$ が凸関数であるとは、
$$
\forall x, y \in \mathrm{dom}(g), \forall \alpha \in [0, 1], ~ g(\alpha x + (1-\alpha)y) \leq \alpha g(x) + (1 - \alpha) g(y)
$$
となることをいいます。そして、$g$ が真であるとは $\mathrm{dom}(g) \neq \emptyset$ となることをいい、$g$ が真凸関数であるとは $g$が真かつ凸関数であることをいいます。$g$ の点 $x \in \mathbb{R}^d$ での劣微分 $\partial g(x)$ は以下のように定義されます。
$$
\partial g(x) := \{ \xi \in \mathbb{R}^d \mid \forall y \in \mathbb{R}^d, ~ g(y) \geq g(x) + \left < \xi, y-x \right > \}.
$$
また、集合 $S \subset \mathbb{R}^d$ について、$S$ のアフィン包 $\mathrm{aff}(S)$ は
$$
\mathrm{aff}(S) := \left\{ \sum_{j=1}^m t_j x_j \mid m \in \mathbb{N}, ~ t_j \in \mathbb{R}, ~ x_j \in S \right\}
$$
と定義され、$S$ の相対的内部 $\mathrm{ri}(S)$ は
$$
\mathrm{ri}(S) := \{ x \in S \mid \exists \varepsilon > 0, B(x, \varepsilon) \cap \mathrm{aff}(S) \subset S \}
$$
と定義されます。相対的内部については以下の記事がわかりやすく図説してくれていますのでぜひご参照ください。

また、アフィン集合についての基本的な性質については以下の記事にまとめましたので適宜ご参照ください。

準備

本節では、相対的内部についての分離定理である真分離定理の証明のためにいくつかの補題を証明しておきます。いま、$S, T \subset \mathbb{R}^d$ と $\alpha \in \mathbb{R}$について
$$
\begin{align}
&\alpha \cdot S := \{ \alpha x \mid x \in S \}, \\
&S + T := \{ s + t \mid s \in S, t \in T \}
\end{align}
$$
と定義します。また、$S$ の（ユークリッド位相についての）閉包を $\mathrm{cl}(S)$ で表すこととします。

補題1
空でない凸集合 $C \subset \mathbb{R}^d$ について
$$
\forall \lambda \in (0, 1], ~ \lambda \cdot \mathrm{ri}(C) + (1-\lambda) \cdot \mathrm{cl}(C) \subset \mathrm{ri}(C)
$$
となる。

証明
$\lambda \in (0, 1]$ を任意にとる。 $C$ が空でない凸集合であることから $\mathrm{ri}(C) \neq \emptyset$ である¹。そこで、$x \in \mathrm{ri}(C), y \in \mathrm{cl}(C)$ とする。

(Step1)：ある $\delta > 0$ が存在して $\mathrm{aff}(C) \cap B(\lambda x + (1-\lambda)y, \delta) \subset C$ となることを示す。$\mathrm{ri}(C)$ の定義より $\mathrm{aff}(C) \cap B(x, 2\varepsilon) \subset C$ なる $\varepsilon > 0$ が取れる。また、$y \in \mathrm{cl}(C)$ より $z \in C$ で $(1-\lambda) \| y-z \| \leq \lambda \varepsilon$ なるものが取れる。$\mathrm{aff}(C) \cap B(\lambda x + (1-\lambda)y, \lambda \varepsilon) \subset C$ を示そう。$w$ を左側の集合の元とし、$v := w - (\lambda x + (1-\lambda) y)$ とおく。$v \in B(0, \lambda \varepsilon)$ であるので、$u := (v + (1-\lambda)(y-z) ) / \lambda \in B(0, 2\varepsilon)$ となる。いま、
$$
w = \lambda x + (1-\lambda) y + v = \lambda (x + u) + (1-\lambda) z
$$
となるので、$x+u \in \mathrm{aff}(C) \cap B(x, 2\varepsilon)$ となることが示されれば、$C$ の凸性より $w \in C$ が従う。さて、$u \in B(0, 2\varepsilon)$ より $x + u \in B(x, 2 \varepsilon)$ である。また、
$$
\begin{align}
x + u
&= x + \frac{1}{\lambda}( w - \lambda x - (1 - \lambda) y + (1- \lambda) (y-z) ) \\
&= \frac{1}{\lambda} w - \frac{1-\lambda}{\lambda} z = \lambda w + \left (1 - \frac{1}{\lambda} \right )z
\end{align}
$$
であり、$w \in \mathrm{aff}(C)$ かつ $z \in C \subset \mathrm{aff}(C)$ であるので、$\mathrm{aff}(C)$ の凸性より $x + u \in \mathrm{aff}(C)$ となる。これで示された。

(Step2)：$\lambda x + (1-\lambda)y \in C$ を示す。$x \in \mathrm{ri}(C) \subset C \subset \mathrm{aff}(C)$ である。また、$\mathrm{aff}(C)$ が $C$ を包む閉集合であることより²、$y \in \mathrm{cl}(C) \subset \mathrm{aff}(C)$ となる。よって、$\mathrm{aff}(C)$ が凸集合であることより $\lambda x + (1-\lambda)y \in \mathrm{aff}(C)$ となる。Step1より $\mathrm{aff}(C) \cap B(\lambda x + (1-\lambda)y, \lambda \varepsilon) \subset C$ であるので、$\lambda x + (1-\lambda)y \in C$ となる。

補題2
空でない凸集合 $C \subset \mathbb{R}^d$ が $0 \notin \mathrm{ri}(C)$ を満たすならば、$0$ に収束する点列 $\{ x_j \}_{j \in \mathbb{N}} \subset \mathbb{R}^d \setminus \mathrm{cl}(C)$ が存在する。さらに、$0 \in \mathrm{cl}(C)$ を満たす場合は $0$ に収束する点列 $\{ x_j \}_{j \in \mathbb{N}} \subset \mathrm{aff}(C) \setminus \mathrm{cl}(C)$ が存在する。

証明
$C$ は空でない凸集合なので $\mathrm{ri}(C) \neq \emptyset$ である¹。そこで $x_0 \in \mathrm{ri}(C)$ が取れる。すると、任意の $ t > 0$ に対して $-t x_0 \notin \mathrm{cl}(C)$ である。なぜなら、もしある $t_0 > 0$ で $-t_0 x_0 \in \mathrm{cl}(C)$ となるとすると、補題1より
$$
0 = \frac{t_0}{1+t_0} x_0 + \frac{1}{1+t_0} (-t_0 x_0) \in \mathrm{ri}(C)
$$
となり、矛盾に達するからである。よって、$x_j := - \frac{1}{j} x_0$ とおけばよい。後半については、$C \subset \mathrm{aff}(C)$ かつ $\mathrm{aff}(C)$ が閉集合であることより $0 \in \mathrm{cl}(C) \subset \mathrm{aff}(C)$ となり、したがって $\mathrm{aff}(C)$ が線形部分空間になること、および $x_0 \in \mathrm{ri}(C) \subset C \subset \mathrm{aff}(C)$ であることに注意すれば、 $x_j \in \mathrm{aff}(C)$ が得られるのでよい。

補題3
$S \subset \mathbb{R}^d$ を空でない凸集合とし、$x \in \mathbb{R}^d$ とするとき、 $x_0 \in S$ について、$\| x - x_0 \| = \inf_{y \in S} \| x - y || $ が成り立つならば、$\forall z \in S , ~ \left < x - x_0, z - x_0 \right > \leq 0$ となる。

証明
$0 \leq \theta \leq 1$ に対して、
$$
f(\theta) := \| x - x_0 - \theta (z - x_0) \|^2 = \| x - ( (1 - \theta) x_0 + \theta z )\|^2
$$
とおく。$S$ は凸集合なので $(1 - \theta) x_0 + \theta z \in S$ となり、したがって仮定より $f$ は $0$ で最小値を取る。いま、
$$
f(\theta) = \| x - x_0 \|^2 - 2 \theta \left < x- x_0, z- x_0 \right > + \theta^2 \| z - x_0 \|^2
$$
であるので、$f'(\theta) = 2\theta \| z - x_0 \|^2 - 2 \left < x- x_0, z- x_0 \right >$ となる（端点での微分係数は片側極限を考える）。しかるに、$f$ の $0$ での最小性より $f'(0) = - 2 \left < x- x_0, z- x_0 \right > \geq 0$ とならなければならない。これで示された。

補題4
空でない閉凸集合 $S \subset \mathbb{R}^d$ と線形部分空間 $L \subset \mathbb{R}^d$ について、$S \subset L$ かつ $x_0 \in L \setminus S$ ならば $b \in L \setminus \{0\}$ が存在して、
$$
\left < x_0, b \right > < \inf_{x \in S} \left < x, b \right >.
$$

証明
最短距離定理³より $\hat{x_0} \in S$ で $\| x_0 - \hat{x_0} \| = \inf_{y \in S} \| x_0 - y \|$ なるものが取れる。$x_0 \notin S$ であるので、$\| x_0 - \hat{x_0} \|^2 > 0$ である。また、補題3より任意の $z \in S$ に対して $\left < x_0 - \hat{x_0}, z - \hat{x_0} \right > \leq 0$ であるので、
$$
\left <\hat{x_0} - x_0, z \right > \geq \left <\hat{x_0} - x_0, \hat{x_0} \right > > \left <\hat{x_0} - x_0, x_0 \right >
$$
となる。よって、$b = \hat{x_0} - x_0$ とおけば不等式を満たし、且つ $S \subset L$ より $b \in L \setminus \{0\}$ となる。

真分離定理

この節では真分離定理を証明します。分離定理には強分離定理、弱分離定理などいろいろ種類があり、そのうちのひとつが真分離定理です。時間が取れれば「いろいろな分離定理」みたいな記事を書き、その中で他の分離定理の証明も書くつもりですのでお楽しみに。

定理（真分離定理）
$S \subset \mathbb{R}^d$ を空でない凸集合とする。このとき、以下は同値。
(1) $0 \notin \mathrm{ri}(S)$
(2) $\exists b \in \mathbb{R}^d \setminus \{ 0 \}, ~ \left ( (\forall y \in S, ~ \left < y, b \right > \geq 0 ) \land (\exists y_0 \in S, \left < y_0, b \right > > 0 ) \right )$

証明
(1)⇒(2)：まず $0 \notin \mathrm{cl}(S)$ の場合は、$\mathrm{cl}(S)$ が閉凸集合であることから $L = \mathbb{R}^d$ として補題4を使うとある $b \in \mathbb{R}^d \setminus \{ 0 \}$ が存在して、$0 = \left <0, b \right > < \inf_{x \in \mathrm{cl}(C)} \left < x, b \right>$ となる。よって、$S \subset \mathrm{cl}(S)$ より(2)の2条件が成立する。次に $0 \in \mathrm{cl}(S)$ とする。すると、補題2より $0$ に収束する点列 $\{ x_j \} \subset \mathrm{aff}(S) \setminus \mathrm{cl}(S)$ が取れる。いま、$L = \mathrm{aff}(S)$ は $0$ を含むため線形部分空間であるので、補題4より各 $j$ に対して、ある $0 \neq b_j \in L$ が存在して、$\left < x_j, b_j \right > < \inf_{y \in \mathrm{cl}(C)} \left < y, b_j \right >$ となる。
$$
\left \{ \frac{b_j}{ | b_j |} \right \}_{j \in \mathbb{N}} \subset S^{d-1} = \{ x \in \mathbb{R}^d \mid \| x \| = 1 \}
$$
であり、$S^{d-1}$ は有界閉集合なので部分列 $\{ b_{j_k} / \| b_{j_k} \| \}_{k \in \mathbb{N}}$ と $v \in S^{d-1}$ が存在して部分列は $v$ に収束する。この $v$ が求めるものであることを示す。$y \in S$ を任意に取ると、$b_j$ の定義より
$$
\begin{align}
&\left < x_{j_k}, b_{j_k} \right > < \left < y, b_{j_k} \right >, \\
&\left < x_{j_k}, \frac{b_{j_k}}{\| b_{j_k} \|} \right > < \left < y, \frac{b_{j_k}}{\| b_{j_k} \|} \right > \quad (*)
\end{align}
$$
となるが、Cauchy-Schwarzの不等式より $\| \left < x_{j_k}, \frac{b_{j_k}}{\| b_{j_k} \|} \right > \| \leq \| x_{j_k} \| \rightarrow 0 \quad (k \rightarrow \infty)$ であるので、$(*)$ において $k \rightarrow \infty$ として $0 \leq \left < y, v \right >$ が得られる。よって、$\forall y \in S, \left < y, v \right > \geq 0$ となる。次にある $y_0 \in S$ について $\left < y_0, v \right > > 0$となることを示す。いま、$b_{j_k} / \| b_{j_k} \| \in L$ かつ $L$は閉集合なので $v \in L$ である。もし、任意の $y \in S$ について $\left < y, v \right > \leq 0$ となるとすると、上で示したことより任意の $y \in S$ について $\left < y, v \right > = 0$ となるが、$v \in L$ より、ある $N \in \mathbb{N}$ と $\lambda_i \in \mathbb{R}, v_i \in S ~(i = 1, \dots, N)$ が存在して、
$$
v = \sum_{i=1}^N \lambda_i v_i , ~ \sum_{i=1}^N \lambda_i = 1
$$
となる。すると、$v \in S^{d-1}$ より
$$
1 = \left < v, v \right > = \sum_{i=1}^N \left < v_i, v \right > = 0
$$
となり矛盾。
(2)⇒(1)：仮に $0 \in \mathrm{ri}(S)$ であるとしよう。 $0 \in S$ となるので$L := \mathrm{aff}(S)$ は線形部分空間である。$0 \in \mathrm{ri}(S)$ より $L \cap B(0,2\varepsilon) \subset S$ なる $\varepsilon > 0$ が取れる。仮定より、ある$y_0 \in S \subset L$ が存在して $ \left < y_0, b \right > > 0$ となる。$-\varepsilon y_0 / \| y_0 \| \in L \cap B(0,2\varepsilon)$ なので $-\varepsilon y_0 / \| y_0 \| \in S$ である。仮定より $\forall y \in S, \left < y, b \right > \geq 0$ であるので、
$$
0 \leq \left < -\varepsilon \frac{y_0}{\| y_0 \|}, b \right > = - \frac{\varepsilon}{\| y_0 \|} \left < y_0, b \right > < 0
$$
となり不合理。

劣微分の存在

命題
$f:\mathbb{R}^d \rightarrow (-\infty, \infty]$ を真凸関数とし、$x_0 \in \mathrm{ri}(\mathrm{dom}(f))$ とする。このとき、
$$
\partial f(x_0) = \{ \xi \in \mathbb{R}^d \mid \forall y \in \mathbb{R}^d, ~ f(y) \geq f(x_0) + \left < \xi, y-x_0 \right > \} \neq \emptyset .
$$

証明
$\mathrm{dom}(f)$ は凸集合であり、$f$ が真凸関数であることより空でない。したがって、$\mathrm{ri}(\mathrm{dom}(f)) \neq \emptyset$ であることに注意する。以下のように定義する。
$$
\mathrm{epi}(f) := \{ (x, y) \in \mathbb{R}^d \times \mathbb{R} \mid f(x) \leq y \}
$$
すると、$(x_0, f(x_0)) \notin \mathrm{ri}(\mathrm{epi}(f))$ となる。実際、任意の $\varepsilon > 0$ に対して、
$$
\begin{align}
&(x_0, f(x_0) - \frac{\varepsilon}{2}) \in \mathrm{aff}(\mathrm{epi}(f)) \cap B((x_0, f(x_0)), \varepsilon), \\
&(x_0, f(x_0) - \frac{\varepsilon}{2}) \notin \mathrm{epi}(f)
\end{align}
$$
である。なぜなら、$(x_0, f(x_0)), (x_0, f(x_0)+1) \in \mathrm{epi}(f) \subset \mathrm{aff}(\mathrm{epi}(f))$ より
$$
\mathrm{aff}(\mathrm{epi}(f)) \ni \left ( 1+ \frac{\varepsilon}{2} \right ) (x_0, f(x_0)) + \left (- \frac{\varepsilon}{2} \right) (x_0, f(x_0)+1) = (x_0, f(x_0) - \frac{\varepsilon}{2})
$$
であるからである。$\mathrm{epi}(f)$ は $f$ が真凸関数であることから空でない凸集合であるので、真分離定理より $0$ でない $(z, v) \in \mathbb{R}^d \times \mathbb{R}$ が存在して、
$$
\begin{align}
&\forall (x,y) \in \mathrm{epi}(f), ~ \left < x, z \right > + vy \geq \left < x_0, z \right > + vf(x_0) \quad (*1) \\
&\exists (x_1, y_1) \in \mathrm{epi}(f), ~ \left < x_1, z \right > + v y_1 > \left < x_0, z \right > + vf(x_0) \quad (*2)
\end{align}
$$
が成り立つ。$v > 0$を示そう。$(*1)$ において $y \geq f(x_0)$ ならば $(x_0, y)$ であるので $y$ はいくらでも大きくとれるので、もし $v < 0$ ならば $\mathrm{左辺} \rightarrow -\infty$ とできてしまい不合理。$v=0$ とすると $(*1), (*2)$ より
$$
\begin{align}
&\forall x \in \mathrm{dom}(f), ~ \left < x, z \right > \geq \left < x_0, z \right > \quad (*3) \\
&\exists x_1 \in \mathrm{dom}(f), ~ \left < x_1, z \right > > \left < x_0, z \right > \quad (*4)
\end{align}
$$
が得られる。よって、真分離定理より $x_0 \notin \mathrm{ri}(\mathrm{dom}(f))$ となる。しかし、仮定より $x_0 \in \mathrm{ri}(\mathrm{dom}(f))$ であるのでこれは不合理。よって、$v > 0$ でなければならない。さて、このことと $(*1)$ より任意の$x \in \mathrm{dom}(f)$ に対して、
$$
\begin{align}
&\left < x, \frac{z}{v} \right > + f(x) \geq \left < x_0, \frac{z}{v} \right > + f(x_0), \\
&\therefore ~ f(x) \geq \left < x - x_0, -\frac{z}{v} \right > + f(x_0) \quad (*5)
\end{align}
$$
となる。$(*5)$ は $x \notin \mathbb{R}^d \mathrm{dom}(f)$ に対しても成立するので $-\frac{z}{v} \in \partial f(x_0)$ となる。

証明は相対的内点の存在性に記しています。 ↩ ↩²
証明はアフィン集合の基本性質に記しています。 ↩
証明は KKT条件についてに記しています。 ↩