凸集合のソースを表示

[[File:Convex polygon illustration1.svg|right|thumb|円板のように見える凸集合、（緑色）の凸集合は {{mvar|x}} と {{mvar|y}} を繋ぐ（黒色）の直線部分を含んでいる。凸集合の内部に直線の部分の全体が含まれる。]]
[[File:Convex polygon illustration2.svg|right|thumb|ブーメランのように見える非凸集合、{{mvar|x}} と {{mvar|y}} を繋ぐ（黒色）の直線の一部が（緑色）の非凸集合の'''外側'''へはみ出ている。]]

[[ユークリッド空間]]における物体が'''凸'''（とつ、{{lang-en-short|''convex''}}）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ[[線分]]上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった[[立方体]]は凸であるが、例えば[[三日月]]形のように窪みや凹みのあるものは何れも凸でない。{{仮リンク|凸曲線|en|convex curve}}は凸集合の境界を成す。

凸集合の概念は後で述べるとおり他の空間へも一般化することができる。

== ベクトル空間内の凸集合 ==
[[File:Convex supergraph.svg|right|thumb|[[凸函数|函数]]が凸であることと、函数のグラフの（緑色の）領域が函数のグラフの上にあるような函数は（下に）凸である。]]
{{mvar|S}} は[[実数]]体（あるいはより一般に適当な[[順序体]]）上の[[ベクトル空間]]とする。ユークリッド空間はその例である。{{mvar|S}} 内の[[集合]] {{mvar|C}} が'''凸'''であるとは、任意の {{math|''x'', ''y'' &isin; ''C''}} および任意の {{math|''t'' &isin; [[区間 (数学)|{{math|[0, 1]}}]]}} に対し、点 {{math|(1 − ''t'')''x'' + ''ty''}} もまた {{mvar|C}} に属することをいう。即ち、{{mvar|x}} と {{mvar|y}} とを結ぶ[[線分]]上の各点が {{mvar|C}} に属する。これにより、[[実数|実]]または[[複素数|複素]][[位相線型空間]]における凸集合は[[弧状連結]]、したがって[[連結空間|連結]]であることが従う。
さらに、{{mvar|C}} が狭義凸 (strictly convex) であるとは、{{mvar|x}} と {{mvar|y}} とを結ぶ線分上の各点が端点を除き {{mvar|C}} の[[内部 (位相空間論)|内部]]に含まれるときにいう。

集合 {{mvar|C}} が[[絶対凸]]とは、それが凸かつ[[均衡集合|均衡]]であるときにいう。

実数全体の成す集合 {{mathbf|R}} の凸[[部分集合]]とは、単に {{mathbf|R}} の区間のことである。[[ユークリッド平面]]の凸部分集合の例には、中身のつまった[[正多角形]]、中身のつまった三角形、中身のつまった三角形の交わり、などが挙げられる。三次元[[ユークリッド空間]]の凸部分集合の例には[[アルキメデスの立体]]、[[プラトンの立体]]などが挙げられる。[[ケプラー・ポアンソ多面体]]は非凸集合の例である。

=== 凹集合 ===

凸でない集合は'''非凸集合''' (''non-convex set'') と言う。[[凸多角形]]でない[[多角形]]は[[凹多角形]]とも呼ばれ<ref>{{citation |first=Jeffrey J. |last=McConnell |year=2006 |title=Computer Graphics: Theory Into Practice |isbn=0-7637-2250-2}}.</ref>{{rp|130}}、文献によってはより一般に非凸集合をあらわすのに'''凹集合''' (''concave set'') という語を使用することもある<ref>{{MathWorld|title=Concave|id=Concave}}</ref>が、普通はそのような言い方は避けられる{{efn|{{harvtxt|Takayama|1994}}「しばしばみられる混乱が『凹集合』である。凹函数と凸函数はある種の函数のクラスを指すのであって集合のではない、その一方凸集合は集合のある種のクラスを指すのであって函数のではない。『凹集合』は集合か函数か紛らわしい」<ref>{{citation|title=Analytical Methods in Economics|first=Akira|last=Takayama|publisher=University of Michigan Press|year=1994|isbn=9780472081356|url= {{google books|id=_WmZA0MPlmEC|plainurl=1}}|ref=harv}}</ref>{{rp|{{google books quote|id=_WmZA0MPlmEC|pg=PA54|text=An often seen confusion is a “concave set”. Concave and convex functions designate certain classes of functions, not of sets, whereas a convex set designates a certain class of sets, and not a class of functions. A “concave set” confuses sets with functions.|54}}}}}}{{efn|{{harvtxt|Corbae|Stinchcombe|Zeman|2009}}「凹集合というようなものは存在しない」<ref>{{citation|title=An Introduction to Mathematical Analysis for Economic Theory and Econometrics|first1=Dean|last1=Corbae|first2=Maxwell B.|last2=Stinchcombe|first3= Juraj|last3=Zeman|publisher=Princeton University Press|year=2009|isbn=9781400833085|url={{google books|id=j5P83LtzVO8C|plainurl=1}}|ref=harv}}</ref>{{rp|{{google books quote|id=j5P83LtzVO8C|pg=PT347|text=There is no such thing as a concave set|347}}}}}}。

== 性質 ==
{{mvar|S}} が {{mvar|n}}-次元空間内の凸集合ならば、任意 {{mvar|r}}-個 ({{math|''r'' > 1}}) の {{mvar|n}}-次元ベクトル {{math|''u''{{sub|1}}, …, ''u{{sub|r}}'' ∈ ''S''}} と任意の[[正数|非負数]] {{math|''λ''{{sub|1}}, …, ''λ{{sub|r}}''}} で {{math|''λ''{{sub|1}} + ⋯ + ''λ{{sub|r}}'' {{=}} 1}} を満たすものに対し
:<math>\sum_{k=1}^r\lambda_k u_k \in S</math>
が成り立つ。このように書かれるベクトルは、{{math|''u''{{sub|1}}, …, ''u{{sub|r}}''}} の[[凸結合]]と呼ばれる。

===交叉と合併===
ベクトル空間の凸部分集合は以下の性質をもつ<ref name="Soltan" >Soltan, Valeriu, ''Introduction to the Axiomatic Theory of Convexity'', Ştiinţa, [[Chişinău]], 1984 (in Russian).
</ref><ref name="Singer" >{{cite book|last=Singer|first=Ivan|title=Abstract convex analysis|series=Canadian Mathematical Society series of monographs and advanced texts|publisher=John Wiley&nbsp;&&nbsp;Sons, Inc.|location=New&nbsp;York|year= 1997|pages=xxii+491|isbn=0-471-16015-6|mr=1461544}}</ref>。
# [[空集合]]とベクトル空間の全体は凸である。
# 凸集合の任意の交叉は凸である。
# 凸部分集合の[[全順序#鎖|非減少]][[有向点族|列]]の合併は凸集合である。

最後の凸集合の合併に関する性質については、合併をとる対象を包含関係を持つ列に制限することが大切である（ふたつの凸集合の合併は必ずしも凸集合でない）。

===閉凸集合===
[[閉集合|閉]]凸集合は、その[[極限点]]をすべて自身に含むような凸集合である。これらは、'''閉{{仮リンク|半空間|en|Half-space (geometry)}}'''（[[超平面]]の片側に位置する空間内の点の集合）たちの交わりとして特徴付けることができる。

今述べたことのうち、そのよう交わりに書けるものが凸であり、それらが閉集合であるということは明らかである。その逆（つまり、任意の凸集合がそのような交わりとして表されること）を言うには、「閉凸集合 {{mvar|C}} とその外点 {{mvar|P}} が与えられたとき、{{mvar|C}} を含み {{mvar|P}} を含まない閉半空間 {{mvar|H}} が存在する」という形の{{仮リンク|支持超平面定理|en|supporting hyperplane theorem}}が必要になる。この支持超平面定理は、[[函数解析学]]における[[ハーン・バナッハの定理]]の特別な場合である。

== 凸包とミンコフスキー和 ==
===凸包===
{{Main|凸包}}
ベクトル空間の部分集合 {{mvar|A}} は、もっとも小さな凸集合（{{mvar|A}} の[[凸包]]と呼ぶ）に含まれる。すなわち、凸包は、{{mvar|A}} を含むすべての凸集合の交叉である。凸包作用素 {{math|Conv()}} は{{仮リンク|閉包作用素|label=包作用素|en|closure operator}}を特徴づける性質をもつ。
; 拡張性: {{math|''S'' ⊆ Conv(''S'')}},
; [[単調写像|非減少性]]: {{math|''S'' ⊆ ''T''}} ならば{{math|Conv(''S'') ⊆ Conv(''T'')}},
; [[冪等|べき等性]]: {{math|Conv(Conv(''S'')) {{=}} Conv(''S'')}}.

凸包作用素は、凸集合全体の成す集合族が[[束 (束論)|束]]を形成するために必要であり、その中で[[結びと交わり|結び演算]] {{math|∨}} は、2つの凸集合の合併の凸包
: {{math|Conv(''S'') ∨ Conv(''T'') {{coloneqq}} Conv(''S'' ∪ ''T'') {{=}} Conv(Conv(''S'') ∪ Conv(''T''))}}
として定義される。凸集合の任意の交叉は凸集合であり、従って（実または複素）ベクトル空間の凸部分集合全体は[[完備束]]を成す。

=== ミンコフスキーの和 ===
{{Main|{{仮リンク|ミンコフスキー演算|en|Minkowski addition}}}}
[[File:Minkowski sum.png|thumb|集合の[[ミンコフスキー和]]: 正方形 {{math|Q{{sub|1}} {{=}} {{closed-closed|0,1}}{{sup|2}}}}, {{math|Q{{sub|2}} {{=}} {{closed-closed|1,2}}{{sup|2}}}} の[[sumset|和集合]] {{math|1= Q{{sub|1}} + Q{{sub|2}} = {{closed-closed|1,3}}{{sup|2}}}}.]]

実線型空間において、二つの空でない集合 {{math|''S''{{sub|1}}, ''S''{{sub|2}}}} の[[ミンコフスキー和]] {{math|''S''{{sub|1}} + ''S''{{sub|2}}}} は、加えられる各集合の[[sumset|元ごとの和の集合]]
: <math>S_1+S_2 = \{x_1+x_2 : x_1 \in S_1,\,x_2\in S_2\}</math>

として定義される。より一般に、空でない部分集合の有限族 {{mvar|S{{sub|n}}}} のミンコフスキー和は、同様に元ごとの和をとって
: <math>\sum_n S_n := \Bigl\{\sum_n x_n : x_n \in S_n\Bigr\}</math>

で与えられる。ミンコフスキー和に関して、[[零ベクトル]]のみからなる集合 {{math|{{mset|0}}}} は特に重要である: 空でない任意の部分集合 {{mvar|S}} に対して
:{{math|''S'' + {{mset|0}} {{=}} ''S''}};
代数の言葉で言えば {{math|{{mset|0}}}} は（空でない集合族上の）ミンコフスキー和の[[単位元]]である{{efn|空集合はミンコフスキー和において重要である。空集合は他の任意の部分集合を零化 (annihilate) する: 任意の部分集合 {{mvar|S}} に対して、それと空集合との和 {{math|''S'' + ∅ {{=}} ∅}} は空集合である。}}。

====ミンコフスキー和の凸包====
ミンコフスキー和は、凸包を取る操作に関して以下の命題が示す通りよく振舞う。

{{math|''S''{{sub|1}}, ''S''{{sub|2}}}} を実ベクトル空間の部分集合とすると、それらのミンコフスキー和の[[凸包]]は、凸包のミンコフスキー和
:{{math|Conv(''S''{{sub|1}} + ''S''{{sub|2}}) {{=}} Conv(''S''{{sub|1}}) + Conv(''S''{{sub|2}})}}
である。

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

:<math>\operatorname{Conv}\Big( \sum_n S_n\Bigr) = \sum_n \operatorname{Conv}(S_n).</math>

数学的な言い方をすれば、ミンコフスキー和と[[凸包]]を作る[[算法|操作]]は、[[可換性|可換]]な操作である<ref>{{cite news|first1=M.|last1=Krein|authorlink1=Mark Krein|first2=V.|last2=Šmulian|year=1940|title=On regularly convex sets in the space conjugate to a Banach space|journal=Annals of Mathematics&nbsp;(2), Second series| volume=41 |pages=556–583|jstor=1968735|doi=10.2307/1968735}}</ref>{{rp|at=Theorem 3 (pp. 562–563)}}{{efn|name="Schneider"|ミンコフスキー和と凸化の可換性は {{harv|Schneider|1993|loc=Theorem 1.1.2 |pp=2–3}} を参照。{{harv|Schneider|1993|loc= Chapter 3 Minkowski addition |pp=126–196}} はミンコフスキー和集合の凸包に関する多くの文献を論じている<ref>{{cite book|last=Schneider|first=Rolf|title=Convex bodies: The Brunn–Minkowski theory|series=Encyclopedia of mathematics and its applications|volume=44|publisher=Cambridge&nbsp;University Press| location=Cambridge | year=1993| pages=xiv+490 |isbn=0-521-35220-7|mr=1216521|ref=harv}}</ref>}}

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

2つのコンパクトな凸集合のミンコフスキー和はコンパクトであり、コンパクト凸集合と閉凸集合の和は閉である<ref>Lemma&nbsp;5.3: {{cite book|first1=C.D.|last1= Aliprantis|first2=K.C.| last2=Border|title=Infinite Dimensional Analysis, A Hitchhiker's Guide| publisher=Springer| location=Berlin|year=2006|isbn=978-3-540-29587-7}}</ref>。

==凸性の一般化と拡張==
ユークリッド空間内の凸性の概念は、定義の一部を修正またはほかのものに取り換えて一般化することができる。「一般化された凸性」という語は、得られる対象が凸集合たちの持つある種の性質を保っていることを示唆して用いられる。

===星状凸===
{{main|星状領域}}
{{mvar|C}} を実または複素ベクトル空間内の集合とする。{{mvar|C}} が'''星状凸'''であるとは、{{mvar|C}} の点 {{math|''x''<sub>0</sub>}} が存在して、{{math|''x''<sub>0</sub>}} から {{mvar|C}} の任意の点 {{mvar|y}} へ結ぶ線分が再び {{mvar|C}} に全く含まれる場合をいう。従って、空でない凸集合は必ず星状凸であるが、星状凸集合は必ずしも凸でない。

===直交凸===
{{main|{{仮リンク|直交凸包|en|Orthogonal convex hull}}}}
一般化凸性の例として、'''直交凸性'''がある<ref>Rawlins G.J.E. and Wood D, "Ortho-convexity and its generalizations",  in: ''Computational Morphology'', 137-152. [[Elsevier]], 1988.</ref>。

ユークリッド空間内の集合 {{mvar|S}} が'''直交凸'''であるとは、{{mvar|S}} の二点を結ぶ任意の座標軸に平行な任意の線分全体が、{{mvar|S}} の中に含まれる場合を言う。直交凸性を持つ集合の交叉が直交凸であることを証明することは容易である。凸集合の持つ他の性質も成立する。

=== 非ユークリッド幾何学 ===
任意の二点を結ぶ（直線の代わりに）[[測地線]]を含む集合として{{仮リンク|測地凸性|label=測地的凸集合|en|geodesic convexity}}を定義することにより、凸集合や凸包の概念を非ユークリッド幾何学に対するものへ自然に拡張することができる。

=== 順序位相 ===
{{仮リンク|順序位相|en|order topology}}を持つ空間 {{mvar|X}} に対しても、その空間の[[全順序]] {{math|<}} を用いて、凸性の概念を定義することができる<ref>[[James Munkres|Munkres, James]]; ''Topology'', Prentice Hall; 2nd edition (December 28, 1999). ISBN 0-13-181629-2.</ref><ref>{{ProofWiki|urlname=Definition:Convex_Set_(Order_Theory)|title=Definition:Convex Set (Order Theory)}}</ref>。

{{math|''Y'' ⊆ ''X''}} とするとき、部分空間 {{mvar|Y}} が凸集合であるとは、{{mvar|Y}} の任意の二点 {{math|''a'', ''b''}} で {{math|''a'' < ''b''}} を満たすものに対して、区間 {{math|(''a'', ''b'') {{=}} {''x'' ∈ ''X'' : ''a'' < ''x'' < ''b''} }} が {{mvar|Y}} に含まれるときにいう。つまり、{{mvar|Y}} が凸となる必要十分条件は、任意の {{math|''a'', ''b'' &isin; ''Y''}} に対し、{{math|''a'' < ''b''}} ならば {{math|(''a'', ''b'') ⊆ ''Y''}} が成り立つことである。

=== 凸型空間 ===
凸性の持つ特定の性質を[[公理]]として、ほかの対象へ凸性を一般化することができる。

与えられた集合 {{mvar|X}} に対し、{{mvar|X}} 上の'''凸型''' (''convexity'') とは {{mvar|X}} の部分集合族 {{math|''𝒞''}} であって以下の公理系を満足するものを言う<ref name="vanDeVel" >{{cite book|last=van De Vel|first=Marcel L. J.|title=Theory of convex structures|series=North-Holland Mathematical Library|publisher=North-Holland Publishing Co.|location=Amsterdam|year= 1993|pages=xvi+540|isbn=0-444-81505-8|mr=1234493}}</ref><ref name="Soltan"/><ref name="Singer"/>:

# 空集合 {{math|&empty;}} および {{mvar|X}} は {{math|''𝒞''}} に属する。
# {{math|''𝒞''}} の元からなる任意の集合族の交わりは {{math|''𝒞''}} に属する。
# {{math|''𝒞''}} の元からなる（包含関係に関して）[[全順序]]な集合族の合併は {{math|''𝒞''}} に属する。

凸型 {{math|''𝒞''}} の元を凸集合と呼び、対 {{math|(''X'', ''𝒞'')}} を'''凸型空間''' (''convexity space'') と呼ぶ。通常の意味の凸性に対して、前二つの公理が成立する（三つ目は自明である）。

このように抽象的な凸性の、より{{仮リンク|離散幾何学|en|discrete geometry}}に適した別定義は、{{仮リンク|反マトロイド|en|antimatroid}}（抽象的凸幾何）に関連する'''凸幾何学'''を参照せよ。

== 注釈 ==
{{notelist}}

== 参考文献 ==
{{reflist}}

== 関連項目 ==
* [[凸包]]
* [[擬凸性]]
* [[離散凸集合]]

== 外部リンク ==
* {{nlab|urlname=convex+set|title=convex set}}
* {{MathWorld|urlname=ConvexSet|title=Convex Set}}
* {{PlanetMath|urlname=ConvexSet|title=convex set}}
* {{ProofWiki|urlname=Definition:Convex_Set_(Vector_Space)|title=Definition:Convex Set (Vector Space)}}
* {{SpringerEOM|urlname=Convex_set|title=Convex set|author= Burago, Yu.D.; Zalgaller, V.A.}}

{{Functional Analysis}}
{{DEFAULTSORT:とつしゆうこう}}
[[category:凸幾何学|凸幾何学]]
[[Category:数学に関する記事]]