凸包の定義と具体例

集合の凸包

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が凸集合であることの定義を改めて確認すると、\begin{equation*}\forall \boldsymbol{x}_{1}\in A,\ \forall \boldsymbol{x}_{2}\in A,\ \forall
\lambda \in \left[ 0,1\right] :\lambda \boldsymbol{x}_{1}+\left( 1-\lambda
\right) \boldsymbol{x}_{2}\in A
\end{equation*}となります。つまり、凸集合上の2つの点を任意に選んで結んだとき、その線分がもとの凸集合の外に出てしまう事態は起こり得ません。

集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)自身は凸集合であるとは限りませんが、\(A\)を部分集合として持つ凸集合は必ず存在します。実際、ユークリッド空間\begin{equation*}\mathbb{R} ^{n}\end{equation*}自身は凸集合であるとともに、\begin{equation*}
A\subset \mathbb{R} ^{n}
\end{equation*}が成り立つため、\(A\)を部分集合として持つ凸集合が必ず存在することが明らかになりました。

集合\(A\subset \mathbb{R} ^{n}\)を部分集合として持つ凸集合は1つだけであるとは限りません。そこで、\(A\)を部分集合として持つ凸集合の中でも包含関係に関して最小の凸集合を\(A\)の凸包（convex hull）と呼び、\begin{equation*}\mathrm{Conv}\left( A\right)
\end{equation*}で表記します。つまり、\(\mathrm{Conv}\left( A\right) \)は凸集合であるとともに、\(A\subset B\)を満たす凸集合\(B\subset \mathbb{R} ^{n}\)を任意に選んだときに、\begin{equation*}\mathrm{Conv}\left( A\right) \subset B
\end{equation*}が成り立つということです。

集合\(A\subset \mathbb{R} ^{n}\)の凸包について考える場合、\(A\)自身は凸集合である必要はありません。複雑で歪な形をしたデータ集合\(A\)を扱う際、そのままでは計算や解析が困難です。しかし、それを凸集合という数学的に扱いやすい性質を持つ最小の枠で囲むことで、データの広がりや境界をシンプルに表現できるようになります。さらに、集合\(A\)を囲む凸集合の中から最小のものを選ぶことにより、余計な情報を増やし過ぎないで済むというメリットもあります。集合\(A\)の凸包とは、\(A\)を包み込む、最も無駄がなく、凸であるという意味において最も整った\(A\)の外枠に相当する概念です。凸包の役割は以上の通りです。

共通部分を用いた凸法の定義

集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)を部分集合として持つ凸集合をすべて集めることにより得られる集合族を、\begin{equation*}\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }
\end{equation*}で表記します。つまり、\begin{eqnarray*}
&&\left( a\right) \ \forall \lambda \in \Lambda :A\subset A_{\lambda } \\
&&\left( b\right) \ \forall \lambda \in \Lambda :A_{\lambda }\text{は凸集合}
\end{eqnarray*}がともに成り立つということです。先に確認したように\(\mathbb{R} ^{n}\)は\(A\)を部分集合として持つ凸集合であるため、この集合族\(\left\{A_{\lambda }\right\} _{\lambda \in \Lambda }\)は非空です。加えて、この集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の共通部分は\(A\)の凸包と一致することが保証されます。つまり、以下の関係\begin{equation*}\mathrm{Conv}\left( A\right) =\bigcap\limits_{\lambda \in \Lambda }A_{\lambda
}
\end{equation*}が成り立つということです。

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(\mathbb{R} ^{n}\)は\(A\)を部分集合として持つ凸集合であるため\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)は非空であり、したがってその共通部分を常にとることができます。さらに先の命題より、その共通部分は\(A\)の凸包と一致します。以上より、\(A\)の凸包が必ず存在することが明らかになりました。

凸結合を利用した凸包の特定

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)を部分集合として持つすべての凸集合からなる集合族\(\left\{ A_{\lambda}\right\} _{\lambda \in \Lambda }\)を特定した上で、その共通部分をとれば\(A\)の凸包が得られることが明らかになりました。ただ、この集合族\(\left\{ A_{\lambda}\right\} _{\lambda \in \Lambda }\)を特定するのは容易ではなく、また、特定できた場合でも、その共通部分をとる作業が困難であるような状況は起こり得ます。このような問題への対処として、凸包をベクトルの凸結合を用いて表現します。

ユークリッド空間上の有限個の点\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\in \mathbb{R} ^{n}\)の凸結合とは、以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda
_{i}\geq 0 \\
&&\left( b\right) \ \sum_{i=1}^{k}\lambda _{i}=1
\end{eqnarray*}を満たす何らかのスカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}\boldsymbol{x}_{1}+\cdots +\lambda _{k}\boldsymbol{x}_{k}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点として定義されます。

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)に属する任意かつ有限個の点の任意の凸結合をすべて集めれば、それは\(A\)の凸包と一致することが保証されます。つまり、自然数\(k\in \mathbb{N} \)を任意に選んだ上で、さらに\(k\)個の点\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\in A\)を任意に選び、さらに、それらの凸結合\begin{equation*}\sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}=\lambda _{1}\boldsymbol{x}_{1}+\cdots +\lambda _{k}\boldsymbol{x}_{k}
\end{equation*}をすべて集めれば\(A\)の凸包になるという主張になります。つまり、以下の関係\begin{equation*}\mathrm{Conv}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ k\in \mathbb{N} \wedge \sum_{i=1}^{k}\lambda _{i}=1\wedge \forall i\in \left\{ 1,\cdots
,k\right\} :\left( \lambda _{i}\geq 0\wedge \boldsymbol{x}_{i}\in A\right)
\right\}
\end{equation*}が成り立つということです。

有限集合の凸包

先の命題を踏まえると、有限集合の凸包を以下のように表現できます。

以上の命題より、有限集合\(A\)の凸包は、\(A\)に属するすべての点の凸結合をすべて集めることにより得られる集合と一致することが明らかになりました。言い換えると、有限集合\(A\)の凸包の要素は、\(A\)のすべての点の何らかの凸結合として表せるということです。ただし、その表現は一意的ではありません。以下の例より明らかです。

上の例では、\(\mathbb{R} \)の有限な部分集合\(A\)について、\begin{equation*}\mathrm{Conv}\left( A\right) =\left[ \min A,\max A\right] \end{equation*}が成立していますが、これは一般的に成立します。

ちなみに、この命題において\(A\subset \mathbb{R} \)が有限集合であるという条件は不可欠です。\(A\)が無限集合である場合、この命題の主張は成り立つとは限りません。以下の例より明らかです。

演習問題