WIIS

凸集合

凸包の定義

目次

前のページ:

狭義凸集合の定義

次のページ:

凸集合のスカラー倍

Twitter
Mailで保存

集合の凸包

ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が凸集合でない場合でも、\(A\)を部分集合として持つ凸集合は必ず存在します。実際、\(\mathbb{R} ^{n}\)は凸集合であるとともに、\begin{equation*}A\subset \mathbb{R} ^{n}
\end{equation*}が明らかに成り立つため、\(\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*}という関係が成り立ちます。

\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\(A\)を部分集合として持つすべての凸集合を要素として持つ\(\mathbb{R} ^{n}\)の部分集合族を\(\left\{A_{\lambda }\right\} _{\lambda \in \Lambda }\)で表記します。つまり、\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*}という関係が成り立つということです。

命題(凸包の生成)
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\(A\)を部分集合として持つすべての凸集合からなる集合族を\(\left\{ A_{\lambda }\right\} _{\lambda \in\Lambda }\)で表記する。このとき、\begin{equation*}\mathrm{Conv}\left( A\right) =\bigcap\limits_{\lambda \in \Lambda }A_{\lambda
}
\end{equation*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

\(\mathbb{R} ^{n}\)は\(A\)を部分集合として持つ凸集合であるため\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)は非空であり、したがってその共通部分を常にとることができます。したがって、\(A\)の凸包は必ず存在します。

命題(凸包の存在)
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\(A\)の凸包は必ず存在する。

 

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

繰り返しになりますが、\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\(A\)を部分集合として持つすべての凸集合からなる集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)をとった上で、その共通部分をとれば\(A\)の凸包が得られます。ただし、\(A\)を部分集合として持つ凸集合をすべて特定するのは容易ではありませんし、仮にそれらをすべて特定できた場合でも、それらの共通部分をとる作業が困難である可能性もあります。このような問題への対処として、凸包をベクトルの凸結合を用いて表現できることを以下で示します。

有限個の点\(x_{1},\cdots ,x_{k}\in \mathbb{R} ^{n}\)が与えられたとき、スカラー\(\lambda _{1},\cdots ,\lambda _{k}\in \mathbb{R} \)を用いて、\begin{equation*}\lambda _{1}x_{1}+\cdots +\lambda _{k}x_{k}
\end{equation*}という形で表される\(\mathbb{R} ^{n}\)の点を\(x_{1},\cdots ,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\)である場合には、線型結合のことを凸結合と呼びます。

\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\(A\)の任意個の点の任意の凸結合をすべて集めれば、それは\(A\)の凸包と一致することが保証されます。ただし、\(A\)の点の凸結合は\(A\)の有限個の点に対して定義される概念であることを踏まえると、これは、自然数\(k\)を任意に選んだ上で、さらに\(k\)個の点\(x_{1},\cdots ,x_{k}\in A\)を任意に選び、さらに、その凸結合\begin{equation*}\sum_{i=1}^{k}\lambda _{i}x_{i}=\lambda _{1}x_{1}+\cdots +\lambda _{k}x_{k}
\end{equation*}をすべて集めれば\(A\)の凸包になるという主張になります。つまり、\begin{equation*}\mathrm{Conv}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}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 x_{i}\in A\right) \right\}
\end{equation*}という関係が成り立つということです。

命題(凸結合を利用した凸包の特定)
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が与えられたとき、\begin{equation*}\mathrm{Conv}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}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 x_{i}\in A\right) \right\}
\end{equation*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

上の命題を踏まえると、問題としている集合が有限集合である場合には、その凸包を以下のように表現できます。

命題(有限集合の凸包)

ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)が有限集合であるとともに、\begin{equation*}A=\left\{ x_{1},\cdots ,x_{n}\right\}
\end{equation*}である場合、\begin{equation*}
\mathrm{Conv}\left( A\right) =\left\{ \sum_{i=1}^{n}\lambda _{i}x_{i}\ |\
\sum_{i=1}^{n}\lambda _{i}=1\wedge \forall i\in \left\{ 1,\cdots ,n\right\}
:\left( \lambda _{i}\geq 0\wedge x_{i}\in A\right) \right\}
\end{equation*}という関係が成り立つ。ただし、\(n\in \mathbb{N} \)である。

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

例(凸包)
\(\mathbb{R} \)の部分集合\begin{equation*}A=\left\{ 0,1,2\right\}
\end{equation*}の凸包は、先の命題より、\begin{eqnarray*}
\mathrm{Conv}\left( A\right) &=&\left\{ \lambda _{1}0+\lambda _{2}1+\lambda
_{3}2\ |\ \lambda _{1}+\lambda _{2}+\lambda _{3}=1\wedge \lambda _{1}\geq
0\wedge \lambda _{2}\geq 0\wedge \lambda _{2}\geq 0\right\} \\
&=&\left\{ \lambda _{2}+\lambda _{3}2\ |\ \lambda _{1}+\lambda _{2}+\lambda
_{3}=1\wedge \lambda _{1}\geq 0\wedge \lambda _{2}\geq 0\wedge \lambda
_{2}\geq 0\right\} \\
&=&\left[ 0,2\right] \end{eqnarray*}となります。凸包の定義より、これは\(A\)を部分集合として含む最小の凸集合です。なお、この凸包の要素\(1\in \mathrm{Conv}\left( A\right) \)は、\begin{eqnarray*}1 &=&0\cdot 0+1\cdot 1+0\cdot 2 \\
&=&\frac{1}{2}\cdot 0+0\cdot 1+\frac{1}{2}\cdot 2 \\
&=&\cdots
\end{eqnarray*}などと様々な線型結合として表現できます。

 

演習問題

問題(凸包と包含関係)
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A,B\)について、\begin{equation*}A\subset B\Rightarrow \mathrm{Conv}\left( A\right) \subset \mathrm{Conv}\left(
B\right)
\end{equation*}という関係が成り立つことを示してください。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(凸包の凸包)
ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A\)について、\begin{equation*}\mathrm{Conv}\left( \mathrm{Conv}\left( A\right) \right) =\mathrm{Conv}\left(
A\right)
\end{equation*}という関係が成り立つことを示してください。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

前のページ:

狭義凸集合の定義

次のページ:

凸集合のスカラー倍

Twitter
Mailで保存

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

凸集合の定義

ユークリッド空間の部分集合に属する2つの点を任意に選んだとき、それらの任意の凸結合がその集合の要素であるならば、その集合を凸集合と呼びます。

狭義凸集合の定義

ユークリッド空間の部分集合に属する異なる2つの点を任意に選んだとき、それらの任意の狭義凸結合がその集合の内点であるならば、その集合を狭義凸集合と呼びます。

予算集合の凸性

消費者理論では予算集合が凸集合であることを仮定することがあります。この場合、非分割財の消費などは分析対象から除外されることになります。

凸集合のスカラー倍

ユークリッド空間の部分集合が与えられたとき、その集合のすべての点をスカラー倍して得られる新たな集合をもとの集合のスカラー倍と呼びます。凸集合のスカラー倍は凸集合であることが保証されます。

生産集合の凸性

生産者理論では生産集合が凸集合であることを仮定することがあります。これは変換関数が準凸関数であることを意味します。

凸集合どうしの線型結合(凸結合)

集合のスカラー倍およびミンコフスキー和を利用して、集合どうしの線型結合や凸結合などの概念を定義します。凸集合どうしの線型結合や凸結合は凸集合になります。

凸集合どうしの直積

凸集合どうしの直積(カルテシアン積)や、凸集合族の直積などはいずれも凸集合になります。

選好の凸性

消費ベクトル x 以上に望ましい消費ベクトル y,z を任意に選んだとき、それらを任意の割合で混ぜることで得られる消費ベクトルもまた x 以上に望ましいことが保証されるのであれば、選好は凸性を満たすと言います。凸性を満たす選好は準凹な効用関数によって特徴づけられます。