凸集合

変形した円のような凸集合の図。点xと点yを結ぶ線分は、緑色で示されているように、集合内に完全に含まれています。これは、集合内の2点の任意の位置に対して成り立つため、この集合は凸集合です。

非凸集合の図。点xと点yを結ぶ線分は、赤で示されているように、集合の外側に部分的に伸びており、集合と線分の交点は黒で示されているように2箇所に存在します。

幾何学では、点の集合が凸集合であるとは、その集合内の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の凸結合と呼ばれます。実ベクトル空間の部分集合Sの凸包は、Sを含むすべての凸集合の積として定義されます。より具体的には、凸包はS内の点のすべての凸結合の集合です。特に、これは凸集合です。

（有界）凸多面体とは、あるユークリッド空間R ⁿの有限部分集合の凸包です。

交差と結合

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

1. 空集合と空間全体は凸です。
2. 凸集合の集合の交差は凸集合である。
3. 凸集合の集合の和集合は、それらの集合が包含に関して鎖（全順序集合）を形成する場合、凸集合である。この性質において、鎖への制限は重要である。なぜなら、2つの凸集合の和集合は必ずしも凸集合である必要はないからである。

閉凸集合

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

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

凸集合の面

凸集合の面とはの凸部分集合であって、の点が と の2点の間に厳密に存在するときはいつでも、 と は両方とも に含まれていなければならない。^[11]同様に、 と がに含まれ、がに含まれるような任意の実数に対しても が含まれていなければならない。この定義によれば、自身と空集合は の面である。これらはの自明面と呼ばれることもある。の極点とは の面である点である。 ${\displaystyle C}$ ${\displaystyle F}$ ${\displaystyle C}$ ${\displaystyle p}$ ${\displaystyle F}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle C}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle F}$ ${\displaystyle x,y\in C}$ ${\displaystyle 0<t<1}$ ${\displaystyle (1-t)x+ty}$ ${\displaystyle F}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle F}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$

をコンパクト（または同義的に、閉じていて有界な）な凸集合とする。すると、はその端点の凸包となる。^{[12]より一般的には、}局所凸位相ベクトル空間の各コンパクト凸集合は、その端点の閉じた凸包となる（クライン・ミルマンの定理）。 ${\displaystyle C}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle C}$

例えば：

• 平面上の三角形（内部領域を含む）は、コンパクト凸集合である。その非自明な面は、3つの頂点と3つの辺である。（したがって、端点は3つの頂点のみである。）
• 閉じた単位円 の唯一の非自明な面はその端点、つまり単位円上の点です。${\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x^{2}+y^{2}\leq 1\}}$ ${\displaystyle S^{1}=\{(x,y)\in \mathbb {R} ^{2}:x^{2}+y^{2}=1\}}$

凸集合と長方形

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

ブラシュケ・サンタロ図

すべての平面凸体の集合は 、凸体の直径D、その内接円r（凸体に含まれる最大の円）、および外接円R （凸体を含む最小の円） によってパラメータ化できます。実際、この集合は^{[14] [15]で示される不等式の集合で記述でき、凸体を (} r / R , D /2 R )で与えられるR ²点に写す関数g の像として視覚化できます。この関数の像は ( r , D , R ) Blachke-Santaló 図として知られています。^[15]${\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}}})}$$

平面凸体のBlaschke-Santaló ( r、D、R ) 図。線分、正三角形、ルーローの三角形、単位円を示します。${\displaystyle \mathbb {L} }$ ${\displaystyle \mathbb {I} _{\frac {\pi }{3}}}$ ${\displaystyle \mathbb {RT} }$ ${\displaystyle \mathbb {B} _{2}}$

あるいは、この集合は、 幅（任意の2つの異なる平行支持超平面間の最小距離）、周囲長、面積によってパラメータ化することもできる。^{[14] [15]}${\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 )}.}$$

ミンコフスキー加算

集合のミンコフスキー加法。平方Q ₁ =[0,1] ²と平方Q ₂ =[1,2] ^2の和は平方Q ₁ +Q ₂ =[1,3] ²である。

実ベクトル空間において、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}はミンコフスキー加法の単位元（空でない集合の集合上）である。^[16] $${\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).}$$

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

凸集合のミンコフスキー和

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

1966年にディドゥネによって証明された次の有名な定理は、2つの閉凸部分集合の差が閉じているための十分条件を与えている。^[20]この定理は、次のように定義される 空でない凸部分集合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 が線型部分空間であるとする。AまたはBが局所コンパクトならば、A  −  Bは閉である。 ${\displaystyle \operatorname {rec} A\cap \operatorname {rec} B}$

凸性の一般化と拡張

ユークリッド空間における凸性の概念は、定義を何らかの側面で修正することによって一般化できる。結果として得られる対象は凸集合の特定の性質を保持するため、「一般化凸性」という通称が用いられる。

星型凸集合

C を実ベクトル空間または複素ベクトル空間上の集合とする。Cが星型凸集合（星形集合）であるとは、 Cにx ₀が存在し、 x ₀からC内の任意の点yへの線分がCに含まれることを意味する。したがって、空でない凸集合は常に星型凸集合であるが、星型凸集合は常に凸集合であるとは限らない。

直交凸性

一般化凸性の例としては直交凸性がある。^[21]

ユークリッド空間の集合Sは、 Sの2点を結ぶ座標軸に平行な任意の線分がSの完全に内部に含まれるとき、直交凸集合または直交凸集合と呼ばれます。任意の直交凸集合の集合の交点が直交凸集合であることは容易に証明できます。凸集合の他のいくつかの性質も同様に成り立ちます。

非ユークリッド幾何学

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

秩序トポロジー

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

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] [23]}

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

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

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

凸空間

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

参照

• 吸収セット
• 凸集合上のアルゴリズム問題
• 有界集合（位相ベクトル空間）
• ブラウワー不動点定理
• 複雑な凸状性
• 凸円錐
• 凸級数
• 凸距離空間
• カラテオドリーの定理（凸包）
• ショケ理論
• ヘリーの定理
• 正則凸包
• 整凸集合
• ジョン楕円体
• 擬似凸性
• ラドンの定理
• シャプレー・フォークマンの補題
• 対称集合

参考文献

1. Morris, Carla C.; Stark, Robert M. (2015年8月24日). 有限数学：モデルと応用. John Wiley & Sons. p. 121. ISBN 9781119015383. 2017年4月5日閲覧。
2. Kjeldsen, Tinne Hoff. 「凸性と数理計画の歴史」(PDF) . Proceedings of the International Congress of Mathematicians (ICM 2010): 3233– 3257. doi :10.1142/9789814324359_0187. 2017年8月11日時点のオリジナル(PDF)からアーカイブ。 2017年4月5日閲覧。
3. ハルモス, ポール・R. (1982年11月8日). 『ヒルベルト空間問題集』 .大学院数学テキスト. 第19巻 (第2版). ニューヨーク:シュプリンガー・フェアラーク. p. 5. ISBN 978-0-387-90685-0OCLC  8169781 。
4. McConnell, Jeffrey J. (2006). 『コンピュータグラフィックス：理論から実践へ』 Jones & Bartlett Learning. p. 130. ISBN 0-7637-2250-2。。
5. Weisstein, Eric W.「Concave」. MathWorld .
6. 高山 明 (1994). 『経済学の分析手法』 ミシガン大学出版局. p. 54. ISBN 9780472081356よく見られる混同は「凹集合」です。凹関数と凸関数は集合ではなく関数の特定のクラスを指しますが、凸集合は関数の特定のクラスではなく集合の特定のクラスを指します。「凹集合」は集合と関数を混同します。
7. コルベ, ディーン; スティンチコム, マクスウェル B.; ゼマン, ジュライ (2009). 『経済理論と計量経済学のための数理分析入門』 プリンストン大学出版局. p. 347. ISBN 9781400833085凹集合というものは存在しません。
8. マイヤー、ロバート (1970). 「最適化手法群の妥当性」(PDF) . SIAM Journal on Control and Optimization . 8 : 41– 54. doi :10.1137/0308003. MR  0312915.。
9. Soltan、Valeriu、凸性の公理理論の紹介、Ştiinţa、Chişinău、1984 (ロシア語)。
10. Singer, Ivan (1997).抽象凸解析. カナダ数学協会モノグラフおよび上級テキストシリーズ. ニューヨーク: John Wiley & Sons, Inc. pp. xxii+491. ISBN 0-471-16015-6. MR  1461544。
11. ロッカフェラー 1997年、162ページ。
12. ロッカフェラー 1997年、166ページ。
13. ラサック、M. (1993)。 「凸体の長方形による近似」。ジオメトリエ・デディカタ。47 : 111–117。土井:10.1007/BF01263495。S2CID  119508642。
14. サンタロ、L. (1961)。 「すべてのシステムが完璧なデシグアルダデスを構成し、凸面の平面を構成します。」Mathematicae Notae。17 : 82-104 .
15. ブランデンベルク、ルネ;ゴンサレス・メリノ、ベルナルド（2017）。 「完全な 3 次元のブラシュケ・サンタロ図」。数学的不等式と応用(2): 301–348 . arXiv : 1404.6808。土井: 10.7153/mia-20-22。ISSN  1331-4343。
16. 空集合はミンコフスキー加算において重要です。なぜなら、空集合は他のすべての部分集合を消滅させるからです。ベクトル空間のすべての部分集合Sについて、空集合との和は空です。${\displaystyle S+\emptyset =\emptyset }$
17. 定理3（562–563ページ）：Krein, M. ; Šmulian, V. (1940). 「バナッハ空間に共役な空間内の規則凸集合について」Annals of Mathematics . Second Series. 41 (3): 556– 583. doi :10.2307/1968735. JSTOR  1968735.
18. ミンコフスキー加法と凸化の可換性については、シュナイダーの定理1.1.2（2～3ページ）を参照。この参考文献では、ミンコフスキー和集合の凸包に関する多くの文献が「第3章 ミンコフスキー加法」（126～196ページ）で議論されている。シュナイダー、ロルフ（1993年）。凸体：ブルン・ミンコフスキー理論。数学とその応用百科事典。第44巻。ケンブリッジ：ケンブリッジ大学出版局。pp. xiv+490。ISBN  0-521-35220-7. MR  1216521。
19. 補題5.3：アリプランティス、CD；ボーダー、KC（2006年）『無限次元解析　ヒッチハイク・ガイド』ベルリン：シュプリンガー、ISBN 978-3-540-29587-7。
20. Zălinescu, C. (2002).一般ベクトル空間における凸解析. リバーエッジ, ニュージャージー: World Scientific Publishing Co., Inc. p. 7. ISBN 981-238-067-1. MR  1921556。
21. Rawlins GJEとWood D、「Ortho-convexity and its generalizations」、Computational Morphology、137-152ページ。Elsevier 、1988年。
22. マンクレス、ジェームズ；トポロジー、プレンティス・ホール；第2版（1999年12月28日）。ISBN 0-13-181629-2。
23. van De Vel, Marcel LJ (1993).凸構造の理論. North-Holland Mathematical Library. アムステルダム: North-Holland Publishing Co. pp. xvi+540. ISBN 0-444-81505-8. MR  1234493。

参考文献

• ロッカフェラー, RT (1997) [1970]. 凸解析. プリンストン, ニュージャージー: プリンストン大学出版局. ISBN 1-4008-7317-7。

外部リンク

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