WIIS

凸集合

凸集合どうしのミンコフスキー和(ミンコフスキー差)

目次

Twitter
Mailで保存

集合のミンコフスキー和

ユークリッド空間\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、\(A_{1}\)の点と\(A_{2}\)の点のベクトル和をすべて集めてできる集合を、\begin{equation*}A_{1}+A_{2}=\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\}
\end{equation*}で表記し、これを\(A_{1}\)と\(A_{2}\)のミンコフスキー和(Minkowski sum)や(sum)などと呼びます。

例(集合のミンコフスキー和)
\(\mathbb{R} ^{2}\)の部分集合\begin{eqnarray*}A_{1} &=&\left\{ \left( 1,0\right) ,\left( 0,1\right) ,\left( 0,-1\right)
\right\} \\
A_{2} &=&\left\{ \left( 0,0\right) ,\left( 1,1\right) ,\left( 1,-1\right)
\right\}
\end{eqnarray*}が与えられたとき、\begin{equation*}
A_{1}+A_{2}=\left\{ \left( 1,0\right) ,\left( 2,1\right) ,\left( 2,-1\right)
,\left( 0,1\right) ,\left( 1,2\right) ,\left( 0,-1\right) ,\left(
1,-2\right) \right\}
\end{equation*}となります。

例(集合のミンコフスキー和)
\(\mathbb{R} \)の部分集合である偶数集合を、\begin{equation*}E=\left\{ \cdots ,-4,-2,0,2,4,\cdots \right\}
\end{equation*}で表記し、奇数集合を、\begin{equation*}
O=\left\{ \cdots ,-3,-1,1,3,\cdots \right\}
\end{equation*}で表記するとき、偶数と奇数の和は奇数であることを踏まえると、\begin{equation*}
E+O=O
\end{equation*}となります。

例(空集合とのミンコフスキー和)
空集合\(\phi \)もまた\(\mathbb{R} ^{n}\)の部分集合であるため、空集合と任意の集合\(A\subset \mathbb{R} ^{n}\)のミンコフスキー和をとることができますが、\begin{equation*}A+\phi =\phi +A=\phi
\end{equation*}が成り立ちます(演習問題)。

例(1点集合とのミンコフスキー和)
点\(a\in \mathbb{R} ^{n}\)と集合\(A\subset \mathbb{R} ^{n}\)をそれぞれ任意に選んだとき、\begin{equation*}a+A=\left\{ a\right\} +A
\end{equation*}という表記を採用します。つまり、\begin{equation*}
a+A=\left\{ a+x\in \mathbb{R} ^{n}\ |\ x\in A\right\}
\end{equation*}です。特に、点\(a\)がゼロベクトルである場合には、\begin{eqnarray*}0+A &=&\left\{ 0+x\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&\left\{ x\in \mathbb{R} ^{n}\ |\ x\in A\right\} \\
&=&A
\end{eqnarray*}となります。

例(集合のミンコフスキー差)
\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、\(A_{1}\)の点と\(A_{2}\)の点のベクトル差をすべて集めてできる集合を、\begin{equation*}A_{1}-A_{2}=\left\{ x_{1}-x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\}
\end{equation*}で表記し、これを\(A_{1}\)と\(A_{2}\)のミンコフスキー差(Minkowski difference)や(difference)などと呼びます。集合のスカラー倍の定義より、\begin{equation}-A_{2}=\left\{ -x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \cdots (1)
\end{equation}となるため、\begin{eqnarray*}
A_{1}-A_{2} &=&\left\{ x_{1}-x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \quad \because \text{ミンコフスキー差の定義} \\
&=&\left\{ x_{1}+\left( -x_{2}\right) \in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \\
&=&\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in -A_{2}\right\} \quad \because \left(
1\right) \\
&=&A_{1}+\left( -A_{2}\right) \quad \because \text{ミンコフスキー和の定義}
\end{eqnarray*}すなわち、\begin{equation*}
A_{1}-A_{2}=A_{1}+\left( -A_{2}\right)
\end{equation*}を得ます。つまり、ミンコフスキー差\(A_{1}-A_{2}\)は集合\(A_{1}\)と集合\(A_{2}\)のスカラー\(-1\)倍のミンコフスキー和として理解できます。

 

ミンコワスキー和の幾何学的解釈

\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、それらのミンコフスキー和\(A_{1}+A_{2}\)を視覚的に理解するためには、まず一方の集合の要素\(x_{1}\in A_{1}\)を任意に選んだ上で、それともう一方の集合\(A_{2}\)のミンコワスキー和\begin{equation}x_{1}+A_{2}=\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \cdots (1)
\end{equation}をとります。\(A_{1}\)のそれぞれの要素\(x_{1}\)について上の集合をとれば\(\mathbb{R} ^{n}\)の部分集合族\(\left\{x_{1}+A_{2}\right\} _{x_{1}\in A_{1}}\)が得られるため、その和集合をとると、\begin{eqnarray*}\bigcup\limits_{x_{1}\in A_{1}}\left( x_{1}+A_{2}\right)
&=&\bigcup\limits_{x_{1}\in A_{1}}\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{2}\in A_{2}\right\} \quad \because \left( 1\right) \\
&=&\left\{ x_{1}+x_{2}\in \mathbb{R} ^{n}\ |\ x_{1}\in A_{1}\wedge x_{2}\in A_{2}\right\} \\
&=&A_{1}+A_{2}
\end{eqnarray*}となり、そもそものミンコフスキー和\(A_{1}+A_{2}\)が得られます。このように分割して考えることにより、ミンコワスキー和を視覚的に理解しやすくなります。

例(ミンコワスキー和の幾何学的解釈)
\(\mathbb{R} ^{2}\)の部分集合\(A\)が、\begin{equation*}A=\left\{ \left( x_{1},y_{1}\right) \in \mathbb{R} ^{2}\ |\ x_{1}^{2}+y_{1}^{2}=1\right\}
\end{equation*}で与えられているものとします。これは原点を中心とする半径\(1\)の円です。このとき、以下のミンコワスキー和\begin{equation*}A+\mathbb{R} _{+}^{2}
\end{equation*}はどのような図形になるのでしょうか。円上の点\(\left( x_{1},y_{1}\right) \in A\)を任意に選んだとき、これと\(\mathbb{R} _{+}^{2}\)のミンコワスキー和は、\begin{equation*}\left( x_{1},y_{1}\right) +\mathbb{R} _{+}^{2}=\left\{ \left( x_{1}+x_{2},y_{1}+y_{2}\right) \in \mathbb{R} ^{2}\ |\ x_{2}\geq 0\wedge y_{2}\geq 0\right\}
\end{equation*}となりますが、これは下図のグレーの領域として描かれます。

図:点と集合のミンコフスキー和
図:点と集合のミンコフスキー和

円\(A\)上の他の点についても同様に考えた上で、得られた集合の和集合をとると\(A+\mathbb{R} _{+}^{2}\)が得られますが、これは下図のグレーの領域として描かれます。

図:ミンコフスキー和
図:ミンコフスキー和

 

2つの凸集合のミンコフスキー和は凸集合

\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)がともに凸集合である場合、それらのミンコスキー和\(A_{1}+A_{2}\)もまた凸集合になることが保証されます。

命題(凸集合のミンコフスキー和)
ユークリッド空間の部分集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)がともに凸集合であるならば、ミンコフスキー和\(A_{1}+A_{2}\)もまた凸集合である。
証明

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

例(凸集合のミンコフスキー差)
先に明らかにしたように、\(\mathbb{R} ^{n}\)の部分集合\(A_{1},A_{2}\)が与えられたとき、\begin{equation*}A_{1}-A_{2}=A_{1}+\left( -A_{2}\right)
\end{equation*}という関係が成り立ちます。\(A_{1}\)と\(A_{2}\)がともに凸集合であるものとします。\(-A_{2}\)は凸集合のスカラー\(-1\)倍であるため凸集合です。したがって、\(A_{1}+\left(-A_{2}\right) \)は凸集合どうしのミンコフスキー和であるため先の命題よりこれは凸集合であり、それと等しい\(A_{1}-A_{2}\)もまた凸集合です。つまり、凸集合どうしのミンコフスキー差もまた凸集合であるということです。
例(凸集合のミンコフスキー和)
\(a<b<c<d\)を満たす実数\(a,b,c,d\in \mathbb{R} \)を任意に選んだ上で、2つの有界開区間\begin{eqnarray*}\left( a,b\right) &=&\left\{ x\in \mathbb{R} \ |\ a<x<b\right\} \\
\left( c,d\right) &=&\left\{ x\in \mathbb{R} \ |\ c<x<d\right\}
\end{eqnarray*}をとります。これらはともに\(\mathbb{R} \)上の凸集合であるため、これらのミンコフスキー和とミンコフスキー差はともに凸集合です。実際、ミンコフスキー和は、\begin{eqnarray*}\left( a,b\right) +\left( c,d\right) &=&\left\{ x+y\in \mathbb{R} \ |\ a<x<b\wedge c<y<d\right\} \\
&=&\left( a+c,b+d\right)
\end{eqnarray*}となりますが、これは有界開区間であるため凸集合です。一方、ミンコフスキー差は、\begin{eqnarray*}
\left( a,b\right) -\left( c,d\right) &=&\left\{ x-y\in \mathbb{R} \ |\ a<x<b\wedge c<y<d\right\} \\
&=&\left( a-d,b-c\right)
\end{eqnarray*}となりますが、これも有界開区間であるため凸集合です。

 

有限個の凸集合のミンコフスキー和は凸集合

先の命題は3個以上の凸集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。

命題(凸集合のミンコフスキー和)
ユークリッド空間の部分集合\(A_{1},A_{2},\cdots ,A_{n}\subset \mathbb{R} ^{n}\)がいずれも凸集合であるならば、ミンコフスキー和\(A_{1}+A_{2}+\cdots +A_{n}\)もまた凸集合である。ただし、\(n\in \mathbb{N} \)である。
証明

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

 

演習問題

問題(ミンコフスキー差)
\(\mathbb{R} ^{2}\)の部分集合\begin{eqnarray*}A_{1} &=&\left\{ \left( 1,0\right) ,\left( 0,1\right) ,\left( 0,-1\right)
\right\} \\
A_{2} &=&\left\{ \left( 0,0\right) ,\left( 1,1\right) ,\left( 1,-1\right)
\right\}
\end{eqnarray*}が与えられたとき、\(A_{1}-A_{2}\)と\(A_{2}-A_{1}\)の要素をそれぞれ特定してください。
解答を見る

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

問題(ミンコフスキー和の交換律)
集合\(A_{1},A_{2}\subset \mathbb{R} ^{n}\)を任意に選んだとき、\begin{equation*}A_{1}+A_{2}=A_{2}+A_{1}
\end{equation*}が成り立つことを証明してください。

解答を見る

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

問題(ミンコフスキー和の結合律)
集合\(A_{1},A_{2},A_{3}\subset \mathbb{R} ^{n}\)を任意に選んだとき、\begin{equation*}\left( A_{1}+A_{2}\right) +A_{3}=A_{1}+\left( A_{2}+A_{3}\right)
\end{equation*}が成り立つことを証明してください。

解答を見る

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

問題(空集合とのミンコフスキー和)
任意の集合\(A\subset \mathbb{R} ^{n}\)について、\begin{equation*}A+\phi =\phi +A=\phi
\end{equation*}が成り立つことを証明してください。

解答を見る

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

Twitter
Mailで保存

質問とコメント

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

関連知識

凸集合の定義

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

ベクトル加法(ベクトル和)

ベクトルを被演算子とする「ベクトル加法」と呼ばれる演算を定義するとともに、その意味や性質などについて解説します。

ベクトル減法(ベクトル差)

ベクトルを被演算子とする「ベクトル減法」と呼ばれる演算を定義するとともに、その意味や性質などについて解説します。

ベクトル加法

n次元空間の2つの点 x,y が与えられたとき、それらの対応する成分どうしを足すことにより得られる新たな点をxとyのベクトル和と呼びます。ベクトル和を与える演算をベクトル加法と呼びます。

狭義凸集合の定義

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

実数の減法

減法と呼ばれる二項演算は加法から間接的に定義されます。減法に関する性質もまた、加法の性質を規定する公理から証明されてはじめて正しいものとして認められます。

凸包の定義

ユークリッド空間の部分集合Aが与えられたとき、Aを部分集合として持つ凸集合の中でも最小のものをAの凸包と呼びます。

ベクトル加法の性質

ベクトル空間上に定義されたベクトル加法が満たす性質を、ベクトル空間の公理系から導きます。また、ベクトル加法を用いて、ベクトル減法と呼ばれる新たな演算を定義します。

ベクトル減法

ベクトル加法を用いてベクトル減法と呼ばれる演算を間接的に定義します。

予算集合の凸性

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

凸集合のスカラー倍

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

生産集合の凸性

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

部分空間どうしの直和

ベクトル空間の複数の部分空間がゼロベクトルだけを共通のベクトルとして持つ場合、そのような部分空間どうしの和(ミンコフスキー和)を直和と呼びます。

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

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

凸集合どうしの直積

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

点列のベクトル和の極限

ユークリッド空間上の収束点列が2つ任意に与えられたとき、それらの一般項どうしのベクトル和を一般項とする点列もまた収束することが保証されます。同様に、収束する点列のベクトル差として定義される点列もまた収束します。