ユークリッド空間における物体が凸(とつ、英: convex)であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった立方体は凸であるが、例えば三日月形のように窪みや凹みのあるものは何れも凸でない。凸曲線(英語版)は凸集合の境界を成す。
凸集合の概念は後で述べるとおり他の空間へも一般化することができる。
ベクトル空間内の凸集合函数が凸であることと、函数のグラフの(緑色の)領域が函数のグラフの上にあるような函数は(下に)凸である。
S は実数体(あるいはより一般に適当な順序体)上のベクトル空間とする。ユークリッド空間はその例である。S 内の集合 C が凸であるとは、任意の x, y ∈ C および任意の t ∈ [0, 1] に対し、点 (1 ? t)x + ty もまた C に属することをいう。即ち、x と y とを結ぶ線分上の各点が C に属する[1]。これにより、実または複素位相線型空間における凸集合は弧状連結、したがって連結であることが従う。さらに、C が狭義凸 (strictly convex) であるとは、x と y とを結ぶ線分上の各点が端点を除き C の内部に含まれるときにいう。
実数全体の成す集合 R の凸部分集合とは、単に R の区間のことである。ユークリッド平面の凸部分集合の例には、中身のつまった正多角形、中身のつまった三角形、中身のつまった三角形の交わり、などが挙げられる。三次元ユークリッド空間の凸部分集合の例にはアルキメデスの立体、プラトンの立体などが挙げられる。ケプラー・ポアンソ多面体は非凸集合の例である。 凸でない集合は非凸集合 (non-convex set) と言う。凸多角形でない多角形は凹多角形とも呼ばれ[2]:130、文献によってはより一般に非凸集合をあらわすのに凹集合 (concave set) という語を使用することもある[3]が、普通はそのような言い方は避けられる[注釈 1][注釈 2]。 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 の凸結合と呼ばれる。 ベクトル空間の凸部分集合は以下の性質をもつ[6][7]。 最後の凸集合の合併に関する性質については、合併をとる対象を包含関係を持つ列に制限することが大切である(ふたつの凸集合の合併は必ずしも凸集合でない)。 今述べたことのうち、そのよう交わりに書けるものが凸であり、それらが閉集合であるということは明らかである。その逆(つまり、任意の凸集合がそのような交わりとして表されること)を言うには、「閉凸集合 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))
として定義される。凸集合の任意の交叉は凸集合であり、従って(実または複素)ベクトル空間の凸部分集合全体は完備束を成す。
ミンコフスキーの和詳細は「ミンコフスキー演算(英語版)」を参照集合のミンコフスキー和: 正方形 Q1 = [0,1]2, Q2 = [1,2]2 の和集合 Q1 + Q2 = [1,3]2.
実線型空間において、二つの空でない集合 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} は(空でない集合族上の)ミンコフスキー和の単位元である[注釈 3]。 ミンコフスキー和は、凸包を取る操作に関して以下の命題が示す通りよく振舞う。 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}).} 数学的な言い方をすれば、ミンコフスキー和と凸包を作る操作は、可換な操作である[8](Theorem 3 (pp. 562?563))[注釈 4] 2つのコンパクトな凸集合のミンコフスキー和はコンパクトであり、コンパクト凸集合と閉凸集合の和は閉である[10]。 ユークリッド空間内の凸性の概念は、定義の一部を修正またはほかのものに取り換えて一般化することができる。「一般化された凸性」という語は、得られる対象が凸集合たちの持つある種の性質を保っていることを示唆して用いられる。 C を実または複素ベクトル空間内の集合とする。C が星状凸であるとは、C の点 x0 が存在して、x0 から C の任意の点 y へ結ぶ線分が再び C に全く含まれる場合をいう。従って、空でない凸集合は必ず星状凸であるが、星状凸集合は必ずしも凸でない。 一般化凸性の例として、直交凸性がある[11]。
ミンコフスキー和の凸包
凸集合のミンコフスキー和
凸性の一般化と拡張
星状凸詳細は「星状領域」を参照
直交凸詳細は「直交凸包(英語版