LoginSignup
1
2

More than 3 years have passed since last update.

コンパクトな集合〜1次元有界閉区間を例にとって〜

Last updated at Posted at 2019-08-07

はじめに

数理最適化において,コンパクトな集合はよく用いられる概念です.主にある集合がコンパクトであるときにその集合の部分集合の近似が可能であったり,最大もしくは最小が存在するという保証がつきます.

以下の話は数学的に厳密でなく,メモ程度なのであしからず.

定義

ある集合 $X$ の部分集合 $A$ の開被覆 $U_w$ とは, $A \subset U_w$ であることを指す.また,任意の開被覆 $U_w$ の有限な部分集合族 $U_w^i \subset U_w$ もまた $A$ を被覆するとき $A$ はコンパクトである.

具体例

X \in \mathbb{R} \\
A = [0, 1] \subset X

$X$ と $A$ を上記のように取ると,$U_w$ としては多くの選択肢が存在する.具体的には,$a < 0$ かつ $b > 1$ を満たすような任意の $(a, b)$ はすべて $U_w$ となる.

例えば,$U_w = (-1, 2)$ もまた,$A$ の開被覆となる.

かなり雑な議論をするとしたら,1次元有界閉区間 $A$ の開被覆として,最も $A$ にサイズが近い $(-\epsilon, 1 + \epsilon)$ という開被覆を考えてあげて,その部分被覆として,$0 < \epsilon'<\epsilon$ なる $\epsilon'$ を用いて,$(-\epsilon', 1 + \epsilon')$ を開被覆として取ると,それもまた,$A$ を被覆するのでコンパクトと言えます.(たぶん)

開区間ならコンパクトでない

とりあえず,開区間は境界に対して漸近するような開被覆のとり方をしてあげると無限に部分集合族を取らないと被覆できない例が出てしまうので,コンパクトでない,みたいな議論が多い.コンパクトであるために重要なのは任意の被覆方法に対して例外なく有限の部分族のみで被覆可能であるということ.

コンパクトなら閉区間

コンパクトな集合に属さない点を1点取り,コンパクトな集合からも1点とり,それらが重複しないようにうまく半径 $\epsilon$ を取り,その半径で覆うような集合を作る.コンパクトな集合から点を取る操作を適当に行うことで有限回数繰り返した時点でコンパクトな集合内の点の周りに張った集合によって,コンパクトな集合は被覆される(コンパクトなので).また,最初に取った点は採択した $\epsilon$ のうち最小のものを取ることでコンパクトな集合との重複を避けた上でその点の近傍の開集合を形成できる.これらの操作をコンパクトな集合に属さない任意の点に関して行うことでコンパクトな集合の補集合は開集合の和集合となり,コンパクトな集合の補集合は開集合となるため,コンパクトな集合は閉集合となる.

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2