凸集合

幾何学では、点の集合が凸集合であるとは、その集合内の2点を結ぶ線分がすべて含まれる場合を言う。同様に、凸集合または凸領域とは、線分、単一点、または空集合内のすべての線と交差する集合のことである。^{[1] [2]} たとえば、立方体は凸集合であるが、中が空洞であったり、三日月形のようにくぼみがあるものは凸集合ではない。

平面上の凸集合の境界は常に凸曲線です。ユークリッド空間の特定の部分集合A を含むすべての凸集合の共通部分は、Aの凸包と呼ばれます。これはA を含む最小の凸集合です。

凸関数は、そのエピグラフ(関数のグラフ上またはグラフ上の点の集合) が凸集合であるという性質を持つ区間上で定義される実数値関数です。凸最小化は、凸集合上の凸関数を最小化する問題を研究する最適化のサブフィールドです。凸集合と凸関数の性質の研究に特化した数学の分野は、凸解析と呼ばれます。

凸集合が定義される空間には、ユークリッド空間、実数上のアフィン空間、および特定の非ユークリッド幾何学が含まれます。ユークリッド空間における凸集合の概念は、その定義を変更することによって、たとえば、そのような集合に含まれる必要がある線分を制限することによって、いくつかの方法で一般化できます。

S を実数上のベクトル空間またはアフィン空間、またはより一般的には、ある順序体上のアフィン空間（これにはアフィン空間であるユークリッド空間が含まれます）とします。 Sの部分集合Cが凸であるとは、C内のすべてのxとyに対して、xとyを結ぶ線分がCに含まれることを意味します。

これは、区間[0, 1]内のC内のすべてのx,yとtに対して、アフィン結合 (1 − t ) x + ty がCに属することを意味します。これは、凸性がアフィン変換に対して不変であることを意味します。さらに、実数または複素位相ベクトル空間内の凸集合はパス連結である(したがって連結でもある) ことを意味します。

集合Cは厳密に凸とは、 xとyを結ぶ線分上の端点以外のCの位相的内部境界点端点である場合に限る。^[3]

集合C は、凸かつ均衡である場合に絶対凸である。

R (実数の集合)の凸集合は、 Rの区間と点です。ユークリッド平面の凸集合の例としては、実正多角形、実三角形、実三角形の交差などがあります。ユークリッド 3 次元空間の凸集合の例としては、アルキメデス立体やプラトン立体などがあります。ケプラー・ポアンソ多面体は非凸集合の例です。

凸集合でない集合は非凸集合と呼ばれる。凸多角形でない多角形は凹多角形と呼ばれることもある^[4]。また、一部の資料ではより一般的に凹集合という用語を非凸集合の意味で使用しているが^{[5] 、ほとんどの権威はこの用法を禁止している[6]}。^[7]

凸集合の補集合、例えば凹関数のエピグラフは、特に数学的最適化の文脈では逆凸集合と呼ばれることがある。^[8]

凸集合S内のr個の点u ₁、...、u _rと、λ ₁ + ... + λ _r = 1となるr個の非負数λ ₁、...、λ _rが与えられた場合、アフィン結合はS に属します。凸集合の定義はr = 2 の場合であるため、この特性は凸集合を特徴付けます。 $${\displaystyle \sum _{k=1}^{r}\lambda _{k}u_{k}}$$

このようなアフィン結合はu ₁ , ..., u _rの凸結合と呼ばれます。

ベクトル空間、アフィン空間、ユークリッド空間の凸集合の集合は 次のような性質を持つ: ^{[9] [10]}

1. 空集合と空間全体は凸です。
2. 任意の凸集合の集合の交差は凸である。
3. 一連の凸集合の和集合が、包含に関して非減少の連鎖を形成する場合、その和集合は凸集合です。この特性では、連鎖への制限が重要であり、2 つの凸集合の和集合は必ずしも凸集合である必要はありません。

閉じた凸集合は、そのすべての極限点を含む凸集合です。閉じた半空間(超平面上および超平面の片側にある空間内の点の集合)の交差として特徴付けることができます。

これまで述べたことから、そのような交差は凸であることは明らかであり、また閉集合となる。逆、すなわちすべての閉凸集合はそのような交差として表すことができることを証明するには、与えられた閉凸集合Cとその外部の点Pに対して、 C を含みP を含まない閉半空間Hが存在するという形の支持超平面定理が必要である。支持超平面定理は、関数解析のハーン・バナッハの定理の特殊なケースである。

C を平面上の凸体（内部が空でない凸集合）とする。長方形r をCに内接させることができ、 rの相似コピーR はCに外接する。正の相似比は最大で 2 であり、次の式が成り立つ: ^[11] $${\displaystyle {\tfrac {1}{2}}\cdot \operatorname {面積} (R)\leq \operatorname {面積} (C)\leq 2\cdot \operatorname {面積} (r)}$$

すべての平面凸体の集合は 、凸体の直径D、その内接円r（凸体に含まれる最大の円）、およびその外接円R（凸体を含む最小の円）によってパラメータ化できます。実際、この集合は^{[12] [13]}で与えられる不等式の集合で記述でき、凸体を( r / R、D /2 R ) で与えられるR ²点に写像する 関数gの像として視覚化できます。この関数の像は、( r、D、R ) Blachke-Santaló 図として知られています。^[13]${\displaystyle {\mathcal {K}}^{2}}$ $${\displaystyle 2r\leq D\leq 2R}$$ $${\displaystyle R\leq {\frac {\sqrt {3}}{3}}D}$$ $${\displaystyle r+R\leq D}$$ $${\displaystyle D^{2}{\sqrt {4R^{2}-D^{2}}}\leq 2R(2R+{\sqrt {4R^{2}-D^{2}}})}$$

あるいは、集合は 幅（任意の2つの異なる平行サポート超平面間の最小距離）、周囲、面積によってパラメータ化することもできます。^{[12] [13]}${\displaystyle {\mathcal {K}}^{2}}$

X を位相ベクトル空間とし、凸とする。 ${\displaystyle C\subseteq X}$

• ${\displaystyle \operatorname {Cl} C}$は両方とも凸です（つまり、凸集合の閉包と内部は凸です）。${\displaystyle \operatorname {Int} C}$
• であれば、（ただし）です。${\displaystyle a\in \operatorname {Int} C}$${\displaystyle b\in \operatorname {Cl} C}$${\displaystyle [a,b[\,\subseteq \operatorname {Int} C}$${\displaystyle [a,b[\,:=\left\{(1-r)a+rb:0\leq r<1\right\}}$
• その場合: ${\displaystyle \operatorname {Int} C\neq \emptyset }$
  • ${\displaystyle \operatorname {cl} \left(\operatorname {Int} C\right)=\operatorname {Cl} C}$、 そして
  • ${\displaystyle \operatorname {Int} C=\operatorname {Int} \left(\operatorname {Cl} C\right)=C^{i}}$、ここで はCの代数的内部です。${\displaystyle C^{i}}$

ベクトル空間のすべての部分集合A は、最小の凸集合（ Aの凸包と呼ばれる）に含まれます。つまり、 A を含むすべての凸集合の共通部分です。凸包演算子 Conv() は、包演算子の特徴的なプロパティを持ちます。

• 拡張：S  ⊆ Conv( S )、
• 非減少： S  ⊆  T はConv( S ) ⊆ Conv( T )を意味し、
• べき等性: Conv(Conv( S )) = Conv( S )。

凸包演算は、凸集合が格子を形成するために必要であり、その「結合」演算は、2 つの凸集合の和集合の凸包です。 凸集合の任意の集合の交差は、それ自体が凸であるため、(実数または複素数の) ベクトル空間の凸部分集合は完全な格子を形成します。 $${\displaystyle \operatorname {Conv} (S)\vee \operatorname {Conv} (T)=\operatorname {Conv} (S\cup T)=\operatorname {Conv} {\bigl (}\operatorname {Conv} (S)\cup \operatorname {Conv} (T){\bigr )}.}$$

実ベクトル空間では、2つの（空でない）集合S ₁とS _2のミンコフスキー和は、加数集合からベクトルを要素ごとに加算して形成される 集合S ₁  +  S ₂として定義されます。 より一般的には、（空でない）集合S _nの有限族のミンコフスキー和は、ベクトルを要素ごとに加算して形成される集合です。 $${\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1},x_{2}\in S_{2}\}.}$$$${\displaystyle \sum _{n}S_{n}=\left\{\sum _{n}x_{n}:x_{n}\in S_{n}\right\}.}$$

ミンコフスキー加法では、零ベクトル0のみを含む零集合 {0}は特別な重要性を持つ。 代数用語では、ベクトル空間の空でない部分集合Sごとに 、 {0}はミンコフスキー加法の単位元（空でない集合の集合上）である。 ^[14] $${\displaystyle S+\{0\}=S;}$$

ミンコフスキー加算は、次の命題で示されるように、凸包を取る操作に関して適切に動作します。

S ₁、S _{2 を}実ベクトル空間の部分集合とすると、それらのミンコフスキー和の凸包はそれらの凸包のミンコフスキー和である。 $${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$$

この結果は、空でない集合の有限集合ごとにより一般的に当てはまります。 $${\displaystyle {\text{Conv}}\left(\sum _{n}S_{n}\right)=\sum _{n}{\text{Conv}}\left(S_{n}\right).}$$

数学用語では、ミンコフスキー和と凸包形成の操作は可換操作である。^{[15] [16]}

2つのコンパクト凸集合のミンコフスキー和はコンパクトである。コンパクト凸集合と閉じた凸集合の和は閉じている。^[17]

1966年にディウドネによって証明された次の有名な定理は、2つの閉じた凸部分集合の差が閉じているための十分条件を与えている。^[18]これは、次のように定義される 空でない凸部分集合Sの後退錐の概念を使用している。 ここで、この集合はを含み、を満たす凸錐である。Sが閉じており凸である場合、は閉じており、すべてのに対して、 $${\displaystyle \operatorname {rec} S=\left\{x\in X\,:\,x+S\subseteq S\right\},}$$${\displaystyle 0\in X}$${\displaystyle S+\operatorname {rec} S=S}$${\displaystyle \operatorname {rec} S}$${\displaystyle s_{0}\in S}$$${\displaystyle \operatorname {rec} S=\bigcap _{t>0}t(S-s_{0}).}$$

定理(ディウドネ)。AとBを、線形部分空間となる局所凸位相ベクトル空間の空でない閉じた凸部分集合とします。AまたはBが局所コンパクトであれば、A  −  B は閉じています。 ${\displaystyle \operatorname {rec} A\cap \operatorname {rec} B}$

ユークリッド空間における凸性の概念は、いくつかの側面で定義を変更することによって一般化できます。結果として得られるオブジェクトは凸集合の特定のプロパティを保持するため、「一般化凸性」という一般的な名前が使用されています。

C を実ベクトル空間または複素ベクトル空間内の集合とします。Cにx 0_が存在し、x ₀からC内の任意の点yまでの線分がCに含まれる場合、 Cは星型凸 (星形)です。したがって、空でない凸集合は常に星型凸ですが、星型凸集合は常に凸であるとは限りません。

一般化された凸性の例としては直交凸性が挙げられる。^[19]

ユークリッド空間の集合S は、 Sの 2 点を結ぶ座標軸に平行な任意の線分がS内に完全に収まる場合、直交凸集合または直交凸集合と呼ばれます。直交凸集合の任意の集合の交差が直交凸集合であることは簡単に証明できます。凸集合の他のいくつかの特性も有効です。

凸集合と凸包の定義は、測地凸集合を集合内の任意の 2 点を結ぶ 測地線を含むものとして定義することにより、ユークリッド幾何学以外の幾何学に自然に拡張されます。

凸性は、順序位相を備えた全順序集合 Xに対して拡張することができる。^[20]

Y ⊆ Xとします。部分空間Yが凸集合であるとは、 Y内の点a、bの各対でa ≤ b となるものに対して、区間[ a、b ] = { x ∈ X | a ≤ x ≤ b }がYに含まれる場合です。つまり、Yが凸であるためには、 Y内のすべてのa、bに対して、a ≤ bであるとき[ a、b ] ⊆ Yが成り立ちます。

凸集合は一般に連結ではありません。反例として、凸かつ連結ではない Zの部分空間 {1,2,3} が挙げられます。

凸性の概念は、凸性の特定の特性を公理として選択すれば、他のオブジェクトにも一般化できます。

集合Xが与えられたとき、X上の凸性とは、以下の公理を満たすXの部分集合の集合である: ^{[9] [10] [21]}

1. 空集合とXは𝒞に含まれる
2. 𝒞からの任意のコレクションの共通部分は𝒞にあります。
3. 𝒞の要素の連鎖（包含関係に関して）の和集合は𝒞にあります。

𝒞の元は凸集合と呼ばれ、ペア( X、𝒞 )は凸空間と呼ばれます。通常の凸性の場合、最初の 2 つの公理は成り立ち、3 つ目は自明です。

離散幾何学により適した抽象的な凸性の別の定義については、反マトロイドに関連する凸幾何学を参照してください。

凸性は抽象的な代数構造として一般化できます。つまり、点の凸結合を取ることができる場合、空間は凸です。

無料辞書『ウィクショナリー』で凸集合を調べてください。

• 「凸部分集合」。数学百科事典。EMS Press。2001 [1994]。
• 凸集合に関する講義、ニールス・ラウリッツェンによるメモ、オーフス大学、2010 年 3 月。