凸集合

出典: フリー百科事典『ウィキペディア(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)).

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

ミンコフスキー和の凸包[編集]

ミンコフスキーの追加は、凸包を取る操作の観点から、次のような位置により示すように、うまく振舞う。

S1, S2 を実ベクトル空間の部分集合とすると、それらのミンコフスキー和の凸包は、凸包のミンコフスキー和

Conv(S1 + S2) = Conv(S1) + Conv(S2)

である。

この結果は、有限個の空でない集合の集まりに対して、より一般的に成り立つ。

\text{Conv}\left ( \sum_n S_n \right ) = \sum_n \text{Conv} \left (S_n \right).

数学的な用語では、ミンコフスキー和と凸包を作る操作英語版(operation)は、可換な操作である[3][4]

閉凸集合[編集]

凸集合は、閉じた半空間英語版(half-space)の交叉として特徴付けることができる(超平面の片側に位置する空間内の点の集合)。今述べたことは、そのような交叉が凸であり、それらも閉集合であるということは明らかであるということである。凸性を証明するために、つまり、すべての凸集合がそのような交叉により表すことができることを証明するためには、閉凸集合 C とその外側に点 P が与えられると、C を含むが P は含まないような閉半空間 H が存在することを閉めるために、サポーティング超平面定理英語版(supporting hyperplane theorem)を必要とする。サポーティング超平面定理は、函数解析ハーン・バナッハの定理の特別な場合である。

2つのコンパクトな凸集合のミンコフスキーの和は、コンパクトであり、コンパクト凸集合と閉凸集合の和は閉である[5]

凸性の一般化と拡張[編集]

ユークリッド空間内の凸性の考え方は、様々な面で定義を変更して一般化することができる。結果として出てくる対象は、ある凸集合の性質を持っているので、「一般凸性」という用語が使われる。

関連項目[編集]

参考文献[編集]

  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. 
  3. ^ Theorem 3 (pages 562–563): Krein, M.; Šmulian, V. (1940年). “On regularly convex sets in the space conjugate to a Banach space”. Annals of Mathematics (2), Second series 41: pp. 556–583. doi:10.2307/1968735 
  4. ^ For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196): Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN 0-521-35220-7. MR1216521. 
  5. ^ Lemma 5.3: Aliprantis, C.D.; Border, K.C. (2006). Infinite Dimensional Analysis, A Hitchhiker's Guide. Berlin: Springer. ISBN 978-3-540-29587-7.