0
大学数学基礎解説
文献あり

閉エピグラフに関する定理

843
0

はじめに

本記事ではエピグラフに関する以下の定理を紹介する。

閉エピグラフの同値な表現

関数f:RnR{,}について、以下は同値である。
(1) エピグラフepi(f)は閉集合
(2) fは下半連続

準備

用語を定義し、補題を準備する。

エピグラフ

エピグラフ

関数f:RnR{,}について、以下で定義されるRn×Rの部分集合を関数fのエピグラフと呼ぶ。
epi(f)={(x,α)Rn×Rf(x)α}

エピグラフとはつまり、関数の「上側に位置する点の集合」である。

下半連続

下半連続

関数f:RnR{,}limnxn=xとなる任意の点列{x}n=1について、
f(x)lim infnf(xn)
を満たすとき、fは下半連続であるという。

ここで
lim infnf(xn)=limninf{f(xm)mn}
は数列{f(xn)}n=1の下極限(かきょくげん)である。下半連続とはつまり、関数が少なくとも「下からつながっている」ことを保証するものである。

レベル集合

レベル集合もまた定理の証明の役に立つ重要な概念である。

レベル集合

任意の実数αRと関数f:RnR{,}について、以下の集合Sf(α)Rnをレベル集合と呼ぶ。
Sf(α)={xRnf(x)α}

要するに関数値が「等高線(=レベル)以下に入る」ような定義域の範囲を与えるのがレベル集合である。この定義により、エピグラフとレベル集合が密接な関係にあることは容易に想像がつく。

補題

上記の定義を用いて以下2つの補題を証明する。

エピグラフepi(f)は閉集合レベル集合Sf(α)は閉集合

補題2

実数αRを任意にとり、レベル集合Sf(α)上の任意の点列{xn}n=1を考える。当然(xn,α)epi(f)であり、またepi(f)は閉集合であるから、limn(xn,α)=(x,α)epi(f)である。ゆえにxSf(α)がいえて、Sf(α)が閉集合であることが示された。

レベル集合Sf(α)は閉集合関数fは下半連続

補題3

xRnを任意に固定し、limnxn=xとなる任意の点列{xn}n=1を考える。lim infnf(xn)=αと置く。下極限の性質により、任意の実数ϵ>0についてf(xn)<α+ϵを満たすnは無数に存在する。今あるϵ>0を固定してβ=α+ϵと置く。xnの部分列{yn}n=1limnf(yn)βを満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するのでlimnyn=xである。Sf(β)は閉集合であるからf(x)βである。つまり任意の実数ϵ>0についてf(x)α+ϵであるから、f(x)α=lim infnf(xn)がいえて、関数fは下半連続である。

定理の証明

補題を準備したおかげで定理の証明はすっきりと書くことができる。

(1)(2):
補題2と補題3を順に適用することで、「エピグラフepi(f)は閉集合関数は下半連続」が従う。

(2)(1):
(xn,αn)epi(f)なるepi(f)上の点列について、極限値がlimn(xn,αn)=(x,α)Rn×Rなるとき、(x,α)epi(f)を示したい。

f(xn)αnであるから、任意の実数ϵ>0についてf(xn)αn<α+ϵを満たすnは無数に存在する。fの下半連続性によりf(x)lim infnf(xn)<α+ϵであり、ϵ>0は任意の実数だからf(x)αがいえる。つまり(x,α)epi(f)であり、epi(f)は閉集合である。

定理の系

定理1

f:RnR{,}とレベル集合Sf(α)について以下は同値である。
(1) 関数fは下半連続
(2) レベル集合Sf(α)は閉集合

定理1と補題により、以下が成り立つので、同値性が示される。

  • 関数fは下半連続 エピグラフepi(f)は閉集合 (定理1)
  • エピグラフepi(f)は閉集合レベル集合Sf(α)は閉集合 (補題2)
  • レベル集合Sf(α)は閉集合 関数fは下半連続 (補題3)

一方で、エピグラフを経由せずに、(1)(2)を直接証明することもできる。(2)(1)の別証明も書いておく。

定理1 系の別証

(1)(2)について:
実数αRを任意にとり、レベル集合Sf(α)上の任意の点列{xn}n=1を考える。limnxn=xとなるとき、xSf(α)を示したい。 レベル集合Sf(α)上に点列を取ったので、各xnについてf(xn)αである。ゆえにlim infnf(xn)f(xn)αであるが、下半連続性によりf(x)lim infnf(xn)αである。これはxSf(α)を意味する。ゆえにSf(α)は閉集合である。

(2)(1)について(補題3の別証明):
xRnを任意に固定し、limnxn=xとなる任意の点列{xn}n=1を考える。lim infnf(xn)=αと置く。下極限の性質により、任意の実数ϵ>0についてf(xn)<α+ϵを満たすnは無数に存在する。今あるϵ>0を固定してβ=α+ϵと置く。xnの部分列{yn}n=1f(yn)<βを満たすものが取れる。収束列の部分列は元の列と同じ極限値に収束するのでlimnyn=xである。各yn{zf(z)<β}に属するが(等号がつかないのでレベル集合ではない!)、ynxが閉じるためには閉包をとってx{zf(z)<β}となる。仮定より、任意の実数γ>0についてレベル集合Sf(β+γ)は閉集合である。また明らかに
{zf(z)<β}Sf(β+γ)
である。閉集合の性質により、共通部分γ>0Sf(β+γ)もまた閉集合である。そして
{zf(z)<β}γ>0Sf(β+γ)=Sf(infγ>0(β+γ))=Sf(β)=Sf(α+ϵ)
であるからxSf(α+ϵ)すなわちf(x)α+ϵが成り立つ。一番左の包含関係は閉包の最小性による。ϵ>0は任意だからf(x)α=lim infnf(xn)がいえて、関数fは下半連続である。

おわりに

実は本記事で紹介した定理は金森/鈴木/竹内/佐藤著『機械学習のための連続最適化』(講談社)および福島著『非線形最適化の理論』(産業図書)の行間を埋めるものであった。前者についてはp.36に証明なしに言及されていた(関数fが凸関数というオマケはついているが)。後者については、本記事の「定理1 系」が、定理2.10(p.26)として述べられているが、その証明を読み解くには行間を埋める必要があった。本記事の最後に書いた証明は同書を参考にして説明を補った形である。

本記事で紹介したエピグラフやレベル集合は凸関数の性質を述べる際にも用いられ、種々の定理が成り立つ。これらの紹介は記事を改めて行いたい。

参考文献

[1]
金森敬文、鈴木大慈、竹内一郎、佐藤一誠, 機械学習のための連続最適化, 機械学習プロフェッショナルシリーズ, 講談社, 2016
[2]
福島 雅夫, 非線形最適化の理論, 講座・数理計画法, 産業図書, 1980
投稿日:2021225
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 準備
  3. エピグラフ
  4. 下半連続
  5. レベル集合
  6. 補題
  7. 定理の証明
  8. 定理の系
  9. おわりに
  10. 参考文献