本記事ではエピグラフに関する以下の定理を紹介する。
関数$f: \mathbb{R}^{n}\rightarrow \mathbb{R} \cup \{-\infty, \infty\}$について、以下は同値である。
(1) エピグラフ$\mathrm{epi}(f)$は閉集合
(2) $f$は下半連続
用語を定義し、補題を準備する。
関数$f:\mathbb{R}^{n}\rightarrow \mathbb{R}\cup \{-\infty, \infty\}$について、以下で定義される$\mathbb{R}^{n} \times \mathbb{R}$の部分集合を関数$f$のエピグラフと呼ぶ。
\begin{equation}
\mathrm{epi}(f) = \{(\mathbf{x}, \alpha) \in \mathbb{R}^{n} \times \mathbb{R} \mid f(\mathbf{x}) \leq \alpha\}
\end{equation}
エピグラフとはつまり、関数の「上側に位置する点の集合」である。
関数$f:\mathbb{R}^{n}\rightarrow \mathbb{R}\cup \{-\infty, \infty\}$が$\lim_{n\to \infty}\mathbf{x}_n = \mathbf{x}$となる任意の点列$\{\mathbf{x}\}_{n=1}^{\infty}$について、
\begin{equation}
f(\mathbf{x}) \leq \liminf_{n\to \infty}f(\mathbf{x}_n)
\end{equation}
を満たすとき、$f$は下半連続であるという。
ここで
\begin{equation}
\liminf_{n \to \infty} f(\mathbf{x}_n) = \lim_{n \to \infty} \inf\{f(\mathbf{x}_m)\mid m\geq n\}
\end{equation}
は数列$\{f(x_n)\}_{n=1}^{\infty}$の下極限（かきょくげん）である。下半連続とはつまり、関数が少なくとも「下からつながっている」ことを保証するものである。
レベル集合もまた定理の証明の役に立つ重要な概念である。
任意の実数$\alpha\in \mathbb{R}$と関数$f: \mathbb{R}^{n}\rightarrow \mathbb{R} \cup \{-\infty, \infty\}$について、以下の集合$S_{f}(\alpha)\subset \mathbb{R}^{n}$をレベル集合と呼ぶ。
\begin{equation}
S_{f}(\alpha) = \{\mathbf{x}\in \mathbb{R}^{n} \mid f(\mathbf{x}) \leq \alpha\}
\end{equation}
要するに関数値が「等高線（＝レベル）以下に入る」ような定義域の範囲を与えるのがレベル集合である。この定義により、エピグラフとレベル集合が密接な関係にあることは容易に想像がつく。
上記の定義を用いて以下２つの補題を証明する。
エピグラフ$\mathrm{epi}(f)$は閉集合$\Rightarrow$レベル集合$S_{f}(\alpha)$は閉集合
実数$\alpha \in \mathbb{R}$を任意にとり、レベル集合$S_{f}(\alpha)$上の任意の点列$\{\mathbf{x}_n\}_{n=1}^{\infty}$を考える。当然$(\mathbf{x}_n, \alpha) \in \mathrm{epi}(f)$であり、また$\mathrm{epi}(f)$は閉集合であるから、$\lim_{n \to \infty}(\mathbf{x}_n, \alpha) = (\mathbf{x}, \alpha) \in \mathrm{epi}(f)$である。ゆえに$\mathbf{x}\in S_{f}(\alpha)$がいえて、$S_{f}(\alpha)$が閉集合であることが示された。
レベル集合$S_{f}(\alpha)$は閉集合$\Rightarrow$関数$f$は下半連続
$\mathbf{x} \in \mathbb{R}^{n}$を任意に固定し、$\lim_{n\to \infty}\mathbf{x}_n = \mathbf{x}$となる任意の点列$\{\mathbf{x}_n\}_{n=1}^{\infty}$を考える。$\liminf_{n\to \infty}f(\mathbf{x}_n) = \alpha$と置く。下極限の性質により、任意の実数$\epsilon > 0$について$f(\mathbf{x}_n) < \alpha +\epsilon$を満たす$n$は無数に存在する。今ある$\epsilon > 0$を固定して$\beta=\alpha+\epsilon$と置く。$\mathbf{x}_n$の部分列$\{\mathbf{y}_{n}\}_{n=1}^{\infty}$で$\lim_{n\to \infty}f(\mathbf{y}_n) \leq \beta$を満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するので$\lim_{n\to \infty}\mathbf{y}_n = \mathbf{x}$である。$S_f(\beta)$は閉集合であるから$f(\mathbf{x})\leq \beta$である。つまり任意の実数$\epsilon > 0$について$f(\mathbf{x})\leq \alpha +\epsilon$であるから、$f(\mathbf{x}) \leq \alpha=\liminf_{n\to \infty}f(\mathbf{x}_n)$がいえて、関数$f$は下半連続である。
補題を準備したおかげで定理の証明はすっきりと書くことができる。
(1)$\Rightarrow$(2):
補題2と補題3を順に適用することで、「エピグラフ$\mathrm{epi}(f)$は閉集合$\Rightarrow$関数は下半連続」が従う。
(2)$\Rightarrow$(1):
$(\mathbf{x}_{n}, \alpha_n) \in \mathrm{epi}(f)$なる$\mathrm{epi}(f)$上の点列について、極限値が$\lim_{n \to \infty}(\mathbf{x}_{n}, \alpha_n)=(\mathbf{x}, \alpha) \in \mathbb{R}^{n} \times \mathbb{R}$なるとき、$(\mathbf{x}, \alpha)\in \mathrm{epi}(f)$を示したい。
$f(\mathbf{x}_{n})\leq \alpha_n$であるから、任意の実数$\epsilon > 0$について$f(\mathbf{x}_n) \leq \alpha_n < \alpha +\epsilon$を満たす$n$は無数に存在する。$f$の下半連続性により$f(\mathbf{x}) \leq \liminf_{n \to \infty} f(\mathbf{x}_n) < \alpha +\epsilon$であり、$\epsilon > 0$は任意の実数だから$f(\mathbf{x})\leq \alpha$がいえる。つまり$(\mathbf{x}, \alpha)\in \mathrm{epi}(f)$であり、$\mathrm{epi}(f)$は閉集合である。
$f: \mathbb{R}^{n}\rightarrow \mathbb{R} \cup \{-\infty, \infty\}$とレベル集合$S_{f}(\alpha)$について以下は同値である。
(1) 関数$f$は下半連続
(2) レベル集合$S_{f}(\alpha)$は閉集合
定理1と補題により、以下が成り立つので、同値性が示される。
一方で、エピグラフを経由せずに、(1)$\Rightarrow$(2)を直接証明することもできる。(2)$\Rightarrow$(1)の別証明も書いておく。
(1)$\Rightarrow$(2)について：
実数$\alpha \in \mathbb{R}$を任意にとり、レベル集合$S_{f}(\alpha)$上の任意の点列$\{\mathbf{x}_n\}_{n=1}^{\infty}$を考える。$\lim_{n\to \infty}\mathbf{x}_n = \mathbf{x}$となるとき、$\mathbf{x} \in S_{f}(\alpha)$を示したい。 レベル集合$S_{f}(\alpha)$上に点列を取ったので、各$\mathbf{x}_{n}$について$f(\mathbf{x}_{n})\leq \alpha$である。ゆえに$\liminf_{n\to \infty}f(\mathbf{x}_n) \leq f(\mathbf{x}_{n})\leq \alpha$であるが、下半連続性により$f(\mathbf{x})\leq\liminf_{n\to \infty}f(\mathbf{x}_n)\leq \alpha$である。これは$\mathbf{x} \in S_{f}(\alpha)$を意味する。ゆえに$S_f(\alpha)$は閉集合である。
(2)$\Rightarrow$(1)について（補題3の別証明）：
$\mathbf{x} \in \mathbb{R}^{n}$を任意に固定し、$\lim_{n\to \infty}\mathbf{x}_n = \mathbf{x}$となる任意の点列$\{\mathbf{x}_n\}_{n=1}^{\infty}$を考える。$\liminf_{n\to \infty}f(\mathbf{x}_n) = \alpha$と置く。下極限の性質により、任意の実数$\epsilon > 0$について$f(\mathbf{x}_n) < \alpha +\epsilon$を満たす$n$は無数に存在する。今ある$\epsilon > 0$を固定して$\beta=\alpha+\epsilon$と置く。$\mathbf{x}_n$の部分列$\{\mathbf{y}_{n}\}_{n=1}^{\infty}$で$f(\mathbf{y}_n) < \beta$を満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するので$\lim_{n\to \infty}\mathbf{y}_n = \mathbf{x}$である。各$\mathbf{y}_{n}$は$\{\mathbf{z} \mid f(\mathbf{z}) < \beta \}$に属するが（等号がつかないのでレベル集合ではない！）、$\mathbf{y}_n \to \mathbf{x}$が閉じるためには閉包をとって$\mathbf{x} \in \overline{\{\mathbf{z} \mid f(\mathbf{z}) < \beta \}}$となる。仮定より、任意の実数$\gamma > 0$についてレベル集合$S_f(\beta + \gamma)$は閉集合である。また明らかに
\begin{equation}
\{\mathbf{z} \mid f(\mathbf{z}) < \beta \}\subset S_f(\beta + \gamma)
\end{equation}
である。閉集合の性質により、共通部分$\bigcap_{\gamma > 0}S_f(\beta + \gamma)$もまた閉集合である。そして
\begin{equation}
\overline{\{\mathbf{z} \mid f(\mathbf{z}) < \beta \}} \subset \bigcap_{\gamma > 0}S_f(\beta + \gamma) = S_f\left(\inf_{\gamma>0} (\beta + \gamma)\right) = S_f(\beta) = S_f(\alpha + \epsilon)
\end{equation}
であるから$\mathbf{x}\in S_f(\alpha + \epsilon)$すなわち$f(\mathbf{x}) \leq \alpha + \epsilon$が成り立つ。一番左の包含関係は閉包の最小性による。$\epsilon >0$は任意だから$f(\mathbf{x}) \leq \alpha = \liminf_{n\to \infty}f(\mathbf{x}_n)$がいえて、関数$f$は下半連続である。
実は本記事で紹介した定理は金森/鈴木/竹内/佐藤著『機械学習のための連続最適化』（講談社）および福島著『非線形最適化の理論』（産業図書）の行間を埋めるものであった。前者についてはp.36に証明なしに言及されていた（関数$f$が凸関数というオマケはついているが）。後者については、本記事の「定理1 系」が、定理2.10（p.26）として述べられているが、その証明を読み解くには行間を埋める必要があった。本記事の最後に書いた証明は同書を参考にして説明を補った形である。
本記事で紹介したエピグラフやレベル集合は凸関数の性質を述べる際にも用いられ、種々の定理が成り立つ。これらの紹介は記事を改めて行いたい。