WIIS

凸集合

凸錐包(錐包)の定義と具体例

目次

Mailで保存
Xで共有

集合の凸錐包

ユークリッド空間の部分集合\(C\subset \mathbb{R} ^{n}\)が凸錐であることは、\begin{equation*}\forall \boldsymbol{x}_{1}\in C,\ \forall \boldsymbol{x}_{2}\in C,\ \forall
\lambda _{1}\geq 0,\ \forall \lambda _{2}\geq 0:\lambda _{1}\boldsymbol{x}_{1}+\lambda _{2}\boldsymbol{x}_{2}\in C
\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 conic hull)や錐包(conic hull)などと呼び、\begin{equation*}\mathrm{Cone}\left( A\right)
\end{equation*}で表記します。定義より、\(\mathrm{Cone}\left( A\right) \)は凸錐であるとともに、\(A\subset C\)を満たす凸錐\(C\subset \mathbb{R} ^{n}\)を任意に選んだときに、\begin{equation*}\mathrm{Cone}\left( A\right) \subset C
\end{equation*}が成り立ちます。集合\(A\)の凸錐包について考える場合、\(A\)自身は凸錐である必要はありません。

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

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

証明

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

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

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

 

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

ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、\(A\)を部分集合として持つすべての凸錐からなる集合族\(\left\{ C_{\lambda }\right\}_{\lambda \in \Lambda }\)をとった上で、その共通部分をとれば\(A\)の凸錐包が得られることが明らかになりました。ただ、この集合族\(\left\{ C_{\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{equation*}\forall i\in \left\{ 1,\cdots ,k\right\} :\lambda _{i}\geq 0
\end{equation*}を満たす場合には、つまり、すべてのスカラーが非負である場合には、線型結合のことを錐結合と呼びます。

ユークリッド空間の部分集合\(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{Cone}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ k\in \mathbb{N} \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\subset \mathbb{R} ^{n}\)が与えられたとき、以下の関係\begin{equation*}\mathrm{Cone}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ k\in \mathbb{N} \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\subset \mathbb{R} ^{n}\)が有限\(k\in \mathbb{N} \)個の要素を持つ有限集合であるものとする。その要素が、\begin{equation*}A=\left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\}
\end{equation*}である場合、以下の関係\begin{equation*}
\mathrm{Cone}\left( A\right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\ |\ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda _{i}\geq
0\right\}
\end{equation*}が成り立つ。

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

有限個のベクトル\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\in \mathbb{R} ^{n}\)が与えられたとき、先の命題より、以下の集合\begin{equation}\mathrm{Cone}\left( \left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \right) =\left\{ \sum_{i=1}^{k}\lambda _{i}\boldsymbol{x}_{i}\
|\ \forall i\in \left\{ 1,\cdots ,k\right\} :\lambda _{i}\geq 0\right\}
\quad \cdots (1)
\end{equation}は\(\left\{ \boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\right\} \)を部分集合として含む最小の凸錐です。このような事情を踏まえた上で、\(\left( 1\right) \)をベクトル\(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\)が生成する凸錐(convex cone generated by the vectors \(\boldsymbol{x}_{1},\cdots ,\boldsymbol{x}_{k}\))と呼びます。\(\left( 1\right) \)のように有限個のベクトルから生成される凸錐を有限生成(finitely generated)される凸錐と呼びます。

 

演習問題

問題(標準基底の凸錐包)
ユークリッド空間\(\mathbb{R} ^{3}\)の標準基底\begin{equation*}\left\{ \boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}\right\}
=\left\{ \left(
\begin{array}{c}
1 \\
0 \\
0\end{array}\right) ,\left(
\begin{array}{c}
0 \\
1 \\
0\end{array}\right) ,\left(
\begin{array}{c}
0 \\
0 \\
1\end{array}\right) \right\}
\end{equation*}が与えられているものとします。その凸錐包は、\begin{equation*}
\mathrm{Conv}\left( \left\{ \boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}\right\} \right) =\mathbb{R} _{+}^{3}
\end{equation*}であることを示してください。

解答を見る

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

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

解答を見る

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

問題(凸錐包の凸錐包)
ユークリッド空間の部分集合\(A\subset \mathbb{R} ^{n}\)が与えられたとき、以下の関係\begin{equation*}\mathrm{Cone}\left( \mathrm{Cone}\left( A\right) \right) =\mathrm{Cone}\left( A\right)
\end{equation*}が成り立つことを示してください。

解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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