集合の種類がどれがなんだったか忘れてしまうことが多かったので簡単にまとめました。
アフィン集合
ある集合を$C$とし、$k$個の点$x_1,\ldots,x_k\in C$をアフィン結合して得られる点$\theta_1 x_1+\ldots+\theta_kx_k$が集合$C$に含まれる時、集合$C$のことをアフィン集合という。
アフィン結合
$k$個の点$x_1,\ldots,x_k\in C$を線形結合する係数の和が1に等しい時、この線形結合の方法をアフィン結合という。($\theta_1+\ldots+\theta_k=1$)
ポイント
- 異なる2点、3点のアフィン結合はそれぞれ直線、平面となる。また、異なる何点かをアフィン結合させたものは超平面となる。(超平面については下記に記載。)
- アフィン集合は有界集合ではなく、原点を必ずしも含まないので部分空間でももない。
- アフィン集合は部分空間とアフィン集合に含まれる任意の一点で表現することができる。これは、$x_0\in C$とした時、$V=\bigl\{x-x_0|x\in C\bigr\}$が部分空間であることを示せば良い。まず、$v_a,v_b\in V$に対し、$x_a=v_a+x_0\in C,x_b=v_b+x_0\in C$と任意の実数$\alpha,\beta$を用いると、ある点$\alpha v_a+\beta v_b+x_0$は
\alpha v_a+\beta v_b +x_0=\alpha (x_a-x_0)+\beta (x_b-x_0) +x_0=\alpha x_a+\beta x_b +(1-\alpha-\beta)x_0 \in C
\tag{1}
であることがわかる。ここで、集合$V$の定義により、
(\alpha v_a+\beta v_b +x_0)-x_0=\alpha v_a+\beta v_b \in V
\tag{2}
であるので、集合$V$は部分集合であることが示された。
凸集合
ある集合を$C$とし、$k$個の点$x_1,\ldots,x_k\in C$を凸結合して得られる点$\theta_1 x_1+\ldots+\theta_kx_k$が集合$C$に含まれる時、集合$C$のことを凸集合という。
凸結合
アフィン結合において結合係数が非負ではない場合、この結合方法を凸結合という。($\theta_1+\ldots+\theta_k=1$かつ$\theta_i \in[0,1]$)
凸包(convex hull)
必ずしも凸ではない集合$C'$の中の$k$個の点$x_1,\ldots,x_k\in C'$を凸結合した集合、つまり
{\rm conv}C'=\bigl\{\theta_1 x_1+\ldots+\theta_kx_k|x_i \in C',\theta_i\ge 0,\theta_1+\ldots+\theta_k=1\bigr\}
\tag{3}
は集合$C'$の凸包という。${\rm conv}C'$は集合$C'$を内包する凸集合の中で最も小さい集合であり、閉凸集合である。
ポイント
- 異なる2点、3点の凸結合はそれぞれ線分、三角形となる。
- 凸集合に含まれる任意の二点を結ぶすべての点は凸集合に含まれる。($x_1,x_2\in C$ならば、$\theta x_1+(1-\theta)x_2$よりわかる。)
- 凸集合は閉集合とは限らない。
- アフィン集合はすべて凸集合。(アフィン集合上の二点をつなぐ直線は線分を含むため。)
円錐
ある集合を$C$とし、任意の係数$\theta\ge 0$に関して、$x\in C$ならば$\theta x\in C$となる時、集合$C$のことを円錐という。
円錐結合
$k$個の点$x_1,\ldots,x_k \in C$を係数$\theta_1,\ldots,\theta_k \ge 0$で線形結合する方法を円錐結合という。
円錐包
必ずしも円錐ではない集合$C'$の中の$k$個の点$x_1,\ldots,x_k\in C'$を円錐結合した集合、つまり
\bigl\{\theta_1 x_1+\ldots+\theta_kx_k|x_i \in C',\theta_i\ge 0,i=1,\ldots,k \bigr\}
\tag{4}
は集合$C'$の円錐包という。この円錐包は集合$C'$を内包する凸円錐の中で最も小さい凸円錐である。
ポイント
- 凸である円錐を凸円錐という。
- 凸円錐$C$について、$x_1,x_2\in C$を凸結合した点($\theta x_1+(1-\theta)x_2\in C$)を定数倍したものも$C$に含まれるため、任意の$\theta_1,\theta_2\ge 0$について
\theta_1 x_1+\theta_2 x_2 \in C
\tag{5}
が成り立つ。
超平面
超平面とはベクトル$a\in \mathbb{R}^n$とスカラ$b\in \mathbb{R}$について、$a^Tx=b$を満たすすべての点$x\in \mathbb{R}^n$の集合のことをいう。($\bigl\{x\in \mathbb{R}^n |a^T x=b \bigr\}$)
ポイント
- 超平面はそれぞれ二次元空間、三次元空間の場合、法線ベクトルaに持つ直線、平面の集合のこと。
- $x_0$を超平面の一つの点とする時、超平面上のすべての点$x$は
a^T(x-x_0)=b-b=0
\tag{6}
よって、ベクトル$a$と超平面上の2点を結ぶベクトル$x-x_0$は直交するとわかる。
半空間
１つの超平面によって分けられる２つの空間を半空間という。($\bigl\{x|a^T x\le b \bigr\},\bigl\{x|a^T x\ge b \bigr\}$)
ポイント
- 半空間は凸集合だが、アフィン集合ではない。(超平面$a^T x=b$より反対側に解集合を持たないため。)
- 超平面上の点$x_0$から半空間$\bigl\{x|a^T x\le b \bigr\}$上の点$x$に向かうベクトルは法線ベクトル$a$と鈍角をなす($\bigl\{x|a^T (x-x_0)\le 0 \bigr\}$)。一方、半空間$\bigl\{x|a^T x\ge b \bigr\}$とは鋭角をなす($\bigl\{x|a^T (x-x_0)\ge 0 \bigr\}$)。
楕円体
楕円体とは、$x_c$を楕円体の中心、$P$を正定行列とした時
\bigl\{x|(x-x_c)^T P^{-1}(x-x_c) \le 1 \bigr\}
\tag{7}
を満たす集合のことをいう。
ポイント
- n次元楕円体について、$P$の固有値を$\lambda_i$とする時、$\sqrt{\lambda_i}$は楕円体の半軸の長さ、${\rm det}P$はn次元楕円体の体積を表す。(証明略)
多面体
多面体$\mathbb{P}$は複数の半空間と超平面の交わりで作られる集合のことをいう。
\mathbb{P}=\bigl\{x|a_i^T x \le b_i,i=1,\ldots,m,c_j^Tx=d_j,j=1,\ldots,r \bigr\}
\tag{8}
ポイント
- アフィン集合、線分、半空間はすべて多面体であり、これらはすべて凸集合。
- 有界の多面体はポリトープ(polytope)という。