凸包の定義と具体例

集合の凸包

ユークリッド空間の部分集合\(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*}が成り立つことを意味します。

集合\(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\)の凸包について考える場合、\(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*}がともに成り立つということです。この集合族の共通部分は\(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}\)が与えられたとき、スカラー\(\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}\)の点を\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\)の線型結合と呼びます。特に、スカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)が以下の条件\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*}をともに満たす場合には、すなわち、すべてのスカラーが非負であるとともにすべてのスカラーの和が\(1\)である場合には、線型結合のことを凸結合と呼びます。

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)の任意個の点の任意の凸結合をすべて集めれば、それは\(A\)の凸包と一致することが保証されます。ただし、\(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\)のすべての点の何らかの凸結合として表すことができるということです。ただし、その表現は一意的ではありません。以下の例より明らかです。

演習問題