凸集合

ユークリッド空間における物体が凸（とつ、英: convex）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった立方体は凸であるが、例えば三日月形のように窪みや凹みのあるものは何れも凸でない。凸曲線（英語版）は凸集合の境界を成す。 凸集合の概念は後で述べるとおり他の空間へも一般化することができる。 S は実数体（あるいはより一般に適当な順序体）上のベクトル空間とする。ユークリッド空間はその例である。S 内の集合 C が凸であるとは、任意の x, y ∈ C および任意の t ∈ [0, 1] に対し、点 (1 − t)x + ty もまた C に属することをいう。即ち、x と y とを結ぶ線分上の各点が C に属する。これにより、実または複素位相線型空間における凸集合は弧状連結、したがって連結であることが従う。 さらに、C が狭義凸 (strictly convex) であるとは、x と y とを結ぶ線分上の各点が端点を除き C の内部に含まれるときにいう。 集合 C が絶対凸とは、それが凸かつ均衡であるときにいう。 実数全体の成す集合 R の凸部分集合とは、単に R の区間のことである。ユークリッド平面の凸部分集合の例には、中身のつまった正多角形、中身のつまった三角形、中身のつまった三角形の交わり、などが挙げられる。三次元ユークリッド空間の凸部分集合の例にはアルキメデスの立体、プラトンの立体などが挙げられる。ケプラー・ポアンソ多面体は非凸集合の例である。 凸でない集合は非凸集合 (non-convex set) と言う。凸多角形でない多角形は凹多角形とも呼ばれ、文献によってはより一般に非凸集合をあらわすのに凹集合 (concave set) という語を使用することもあるが、普通はそのような言い方は避けられる。 S が n-次元空間内の凸集合ならば、任意 r-個 (r > 1) の n-次元ベクトル u1, …, ur ∈ S と任意の非負数 λ1, …, λr で λ1 + ⋯ + λr = 1 を満たすものに対し ∑ k = 1 r λ k u k ∈ S {\displaystyle \sum _{k=1}^{r}\lambda _{k}u_{k}\in S} が成り立つ。このように書かれるベクトルは、u1, …, ur の凸結合と呼ばれる。 ベクトル空間の凸部分集合は以下の性質をもつ。 空集合とベクトル空間の全体は凸である。 凸集合の任意の交叉は凸である。 凸部分集合の非減少列の合併は凸集合である。 最後の凸集合の合併に関する性質については、合併をとる対象を包含関係を持つ列に制限することが大切である（ふたつの凸集合の合併は必ずしも凸集合でない）。 閉凸集合は、その極限点をすべて自身に含むような凸集合である。これらは、閉半空間（英語版）（超平面の片側に位置する空間内の点の集合）たちの交わりとして特徴付けることができる。 今述べたことのうち、そのよう交わりに書けるものが凸であり、それらが閉集合であるということは明らかである。その逆（つまり、任意の凸集合がそのような交わりとして表されること）を言うには、「閉凸集合 C とその外点 P が与えられたとき、C を含み P を含まない閉半空間 H が存在する」という形の支持超平面定理（英語版）が必要になる。この支持超平面定理は、函数解析学におけるハーン・バナッハの定理の特別な場合である。 ベクトル空間の部分集合 A は、もっとも小さな凸集合（A の凸包と呼ぶ）に含まれる。すなわち、凸包は、A を含むすべての凸集合の交叉である。凸包作用素 Conv() は包作用素（英語版）を特徴づける性質をもつ。 拡張性 S ⊆ Conv(S), 非減少性 S ⊆ T ならばConv(S) ⊆ Conv(T), べき等性 Conv(Conv(S)) = Conv(S). 凸包作用素は、凸集合全体の成す集合族が束を形成するために必要であり、その中で結び演算 ∨ は、2つの凸集合の合併の凸包 Conv(S) ∨ Conv(T) ≔ Conv(S ∪ T) = Conv(Conv(S) ∪ Conv(T)) として定義される。凸集合の任意の交叉は凸集合であり、従って（実または複素）ベクトル空間の凸部分集合全体は完備束を成す。 実線型空間において、二つの空でない集合 S1, S2 のミンコフスキー和 S1 + S2 は、加えられる各集合の元ごとの和の集合 S 1 + S 2 = { x 1 + x 2 : x 1 ∈ S 1 , x 2 ∈ S 2 } {\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1},\,x_{2}\in S_{2}\}} として定義される。より一般に、空でない部分集合の有限族 Sn のミンコフスキー和は、同様に元ごとの和をとって ∑ n S n := { ∑ n x n : x n ∈ S n } {\displaystyle \sum _{n}S_{n}:={\Bigl \{}\sum _{n}x_{n}:x_{n}\in S_{n}{\Bigr \}}} で与えられる。ミンコフスキー和に関して、零ベクトルのみからなる集合 {0} は特に重要である: 空でない任意の部分集合 S に対して S + {0} = S; 代数の言葉で言えば {0} は（空でない集合族上の）ミンコフスキー和の単位元である。 ミンコフスキー和は、凸包を取る操作に関して以下の命題が示す通りよく振舞う。 S1, S2 を実ベクトル空間の部分集合とすると、それらのミンコフスキー和の凸包は、凸包のミンコフスキー和 Conv(S1 + S2) = Conv(S1) + Conv(S2) である。 この結果は、有限個の空でない集合の集まりに対して、より一般的に成り立つ。 Conv ⁡ ( ∑ n S n ) = ∑ n Conv ⁡ ( S n ) . {\displaystyle \operatorname {Conv} {\Big (}\sum _{n}S_{n}{\Bigr )}=\sum _{n}\operatorname {Conv} (S_{n}).} 数学的な言い方をすれば、ミンコフスキー和と凸包を作る操作は、可換な操作である 2つのコンパクトな凸集合のミンコフスキー和はコンパクトであり、コンパクト凸集合と閉凸集合の和は閉である。 ユークリッド空間内の凸性の概念は、定義の一部を修正またはほかのものに取り換えて一般化することができる。「一般化された凸性」という語は、得られる対象が凸集合たちの持つある種の性質を保っていることを示唆して用いられる。 C を実または複素ベクトル空間内の集合とする。C が星状凸であるとは、C の点 x0 が存在して、x0 から C の任意の点 y へ結ぶ線分が再び C に全く含まれる場合をいう。従って、空でない凸集合は必ず星状凸であるが、星状凸集合は必ずしも凸でない。 一般化凸性の例として、直交凸性がある。 ユークリッド空間内の集合 S が直交凸であるとは、S の二点を結ぶ任意の座標軸に平行な任意の線分全体が、S の中に含まれる場合を言う。直交凸性を持つ集合の交叉が直交凸であることを証明することは容易である。凸集合の持つ他の性質も成立する。 任意の二点を結ぶ（直線の代わりに）測地線を含む集合として測地的凸集合（英語版）を定義することにより、凸集合や凸包の概念を非ユークリッド幾何学に対するものへ自然に拡張することができる。 順序位相（英語版）を持つ空間 X に対しても、その空間の全順序 < を用いて、凸性の概念を定義することができる。 Y ⊆ X とするとき、部分空間 Y が凸集合であるとは、Y の任意の二点 a, b で a < b を満たすものに対して、区間 (a, b) = {x ∈ X : a < x < b} が Y に含まれるときにいう。つまり、Y が凸となる必要十分条件は、任意の a, b ∈ Y に対し、a < b ならば (a, b) ⊆ Y が成り立つことである。 凸性の持つ特定の性質を公理として、ほかの対象へ凸性を一般化することができる。 与えられた集合 X に対し、X 上の凸型 (convexity) とは X の部分集合族 𝒞 であって以下の公理系を満足するものを言う: 空集合 ∅ および X は 𝒞 に属する。 𝒞 の元からなる任意の集合族の交わりは 𝒞 に属する。 𝒞 の元からなる（包含関係に関して）全順序な集合族の合併は 𝒞 に属する。 凸型 𝒞 の元を凸集合と呼び、対 (X, 𝒞) を凸型空間 (convexity space) と呼ぶ。通常の意味の凸性に対して、前二つの公理が成立する（三つ目は自明である）。 このように抽象的な凸性の、より離散幾何学に適した別定義は、反マトロイド（英語版）（抽象的凸幾何）に関連する凸幾何学を参照せよ。