凸集合

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
円板のように見える凸集合、(緑色)の凸集合は x と y を繋ぐ(黒色)の直線部分を含んでいる。凸集合の内部に直線の部分の全体が含まれる。
ブーメランのように見える非凸集合、x と y を繋ぐ(黒色)の直線の一部が(緑色)の非凸集合の外側へはみ出ている。

凸集合とは、ユークリッド空間において、集合の任意の二点を結ぶ線分が集合に含まれるような集合をいう。

たとえば、立方体は、凸集合であるが、へこみのあるような集合は凸集合ではない。凸曲線英語版(convex curve)は凸集合の境界となる。

凸集合の考え方は、下記に述べるように他の空間の考え方へ一般化することができる。

ベクトル空間の中で[編集]

函数が凸であることと、函数のグラフの(緑色)の領域が函数のグラフの上にあるような函数は(下に)凸である。

S を実数上のベクトル空間、あるいはより一般的にある順序体とする。この定義はユークリッド空間を含んでいる。S の中のある集合 C が凸であるとは、すべての C の中の x, y と、区間 [0, 1] の中の t に対し、点 (1 − t)x + ty も C に属していることである。言い換えると、x と y とを繋ぐ線分のすべての点が、C に属していることである。このことは実数複素数位相ベクトル空間の凸集合は、弧状連結であり、従って連結空間であることを意味する。

集合 C が凸であり、均衡のとれた集合のとき、絶対凸英語版(absolutely convex)という。

R (実数の集合)の凸部分集合は、単純に R の区間である。ユークリッド平面の凸集合の例は、中身を含む正多角形、中身を含む三角形や、複数の中身を含む三角形の交叉がある。3-次元ユークリッド空間の凸部分集合の例は、アルキメデスのソリッド英語版(Archimedean solid)や、プラトンのソリッド英語版(Platonic solid)がある。ケプラー・ポアソーの多面体英語版(Kepler-Poinsot polyhedra)は非凸集合の例である。

性質[編集]

S が n-次元空間内の凸集合であれば、S の中の任意の集合、r, r > 1, n-次元ベクトル空間 u1, ..., ur と任意の非負である数で λ1 + ... + λr = 1 であるような λ1, ..., λr に対し、

\sum_{k=1}^r\lambda_k u_k \in S

である。このようなベクトルは、u1, ..., ur凸結合英語版(convex combination)として知られている。

交叉と合併[編集]

ベクトル空間の凸部分集合は、次の性質をもつ。[1][2]

  1. 空集合とベクトル空間の全体は凸である。
  2. 凸集合の任意の交叉は凸である。
  3. 凸部分集合の非減少有向点族の合併は、凸集合である。凸集合の非減少な有効点族の集合の合併の性質にとって、この性質をもつ集合への制限は重要である。つまり、2つ凸集合の合併は、必ずしも凸集合とはかぎらない。

凸包[編集]

ベクトル空間のすべての部分集合 A は、もっとも小さな凸集合( A の凸包と呼ぶ)に含まれる。すなわち、凸包は、A を含むすべての凸集合の交叉である。凸包作用素 Conv() は包作用素英語版(hull operator)の特別な性質をもつ。

拡張性   S ⊆ Conv(S),
非減少性   S ⊆ Tは、Conv(S) ⊆ Conv(T)を意味する,
べき等性  Conv(Conv(S)) = Conv(S).

凸包作用素は、凸集合が格子を形成するために必要であり、その中で合併と交叉英語版(join and meet)は、2つの凸集合の凸包である。

Conv(S) ∨ Conv(T) = Conv(S ∪ T) = Conv(Conv(S) ∪ Conv(T)).

凸集合の任意の交叉は、凸集合であり、従って、(実、複素)ベクトル空間の凸部分集合は完全格子を形成する。

関連項目[編集]

参考文献[編集]

  1. ^ Soltan, Valeriu, Introduction to the Axiomatic Theory of Convexity, Ştiinţa, Chişinău, 1984 (in Russian).
  2. ^ Singer, Ivan (1997). Abstract convex analysis. Canadian Mathematical Society series of monographs and advanced texts. New York: John Wiley & Sons, Inc.. pp. xxii+491. ISBN 0-471-16015-6. MR1461544.