はじめに
本記事ではエピグラフに関する以下の定理を紹介する。
閉エピグラフの同値な表現
関数について、以下は同値である。
(1) エピグラフは閉集合
(2) は下半連続
準備
用語を定義し、補題を準備する。
エピグラフ
エピグラフ
関数について、以下で定義されるの部分集合を関数のエピグラフと呼ぶ。
エピグラフとはつまり、関数の「上側に位置する点の集合」である。
下半連続
下半連続
関数がとなる任意の点列について、
を満たすとき、は下半連続であるという。
ここで
は数列の下極限(かきょくげん)である。下半連続とはつまり、関数が少なくとも「下からつながっている」ことを保証するものである。
レベル集合
レベル集合もまた定理の証明の役に立つ重要な概念である。
レベル集合
任意の実数と関数について、以下の集合をレベル集合と呼ぶ。
要するに関数値が「等高線(=レベル)以下に入る」ような定義域の範囲を与えるのがレベル集合である。この定義により、エピグラフとレベル集合が密接な関係にあることは容易に想像がつく。
補題
上記の定義を用いて以下2つの補題を証明する。
補題2
実数を任意にとり、レベル集合上の任意の点列を考える。当然であり、または閉集合であるから、である。ゆえにがいえて、が閉集合であることが示された。
補題3
を任意に固定し、となる任意の点列を考える。と置く。下極限の性質により、任意の実数についてを満たすは無数に存在する。今あるを固定してと置く。の部分列でを満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するのでである。は閉集合であるからである。つまり任意の実数についてであるから、がいえて、関数は下半連続である。
定理の証明
補題を準備したおかげで定理の証明はすっきりと書くことができる。
(1)(2):
補題2と補題3を順に適用することで、「エピグラフは閉集合関数は下半連続」が従う。
(2)(1):
なる上の点列について、極限値がなるとき、を示したい。
であるから、任意の実数についてを満たすは無数に存在する。の下半連続性によりであり、は任意の実数だからがいえる。つまりであり、は閉集合である。
定理の系
定理1
とレベル集合について以下は同値である。
(1) 関数は下半連続
(2) レベル集合は閉集合
定理1と補題により、以下が成り立つので、同値性が示される。
- 関数は下半連続 エピグラフは閉集合 (定理1)
- エピグラフは閉集合レベル集合は閉集合 (補題2)
- レベル集合は閉集合 関数は下半連続 (補題3)
一方で、エピグラフを経由せずに、(1)(2)を直接証明することもできる。(2)(1)の別証明も書いておく。
定理1 系の別証
(1)(2)について:
実数を任意にとり、レベル集合上の任意の点列を考える。となるとき、を示したい。 レベル集合上に点列を取ったので、各についてである。ゆえにであるが、下半連続性によりである。これはを意味する。ゆえには閉集合である。
(2)(1)について(補題3の別証明):
を任意に固定し、となる任意の点列を考える。と置く。下極限の性質により、任意の実数についてを満たすは無数に存在する。今あるを固定してと置く。の部分列でを満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するのでである。各はに属するが(等号がつかないのでレベル集合ではない!)、が閉じるためには閉包をとってとなる。仮定より、任意の実数についてレベル集合は閉集合である。また明らかに
である。閉集合の性質により、共通部分もまた閉集合である。そして
であるからすなわちが成り立つ。一番左の包含関係は閉包の最小性による。は任意だからがいえて、関数は下半連続である。
おわりに
実は本記事で紹介した定理は金森/鈴木/竹内/佐藤著『機械学習のための連続最適化』(講談社)および福島著『非線形最適化の理論』(産業図書)の行間を埋めるものであった。前者についてはp.36に証明なしに言及されていた(関数が凸関数というオマケはついているが)。後者については、本記事の「定理1 系」が、定理2.10(p.26)として述べられているが、その証明を読み解くには行間を埋める必要があった。本記事の最後に書いた証明は同書を参考にして説明を補った形である。
本記事で紹介したエピグラフやレベル集合は凸関数の性質を述べる際にも用いられ、種々の定理が成り立つ。これらの紹介は記事を改めて行いたい。