WIIS

凸集合

狭義分離超平面定理(超平面による凸集合と点の狭義分離)

目次

Twitter
Mailで保存

超平面による集合と点の狭義分離

ユークリッド空間\(\mathbb{R} ^{n}\)における超平面とは、非ゼロの法線ベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)から、\begin{equation*}H\left( a,c\right) =\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x=c\right\}
\end{equation*}と定義される\(\mathbb{R} ^{n}\)の部分集合です。超平面\(H\left( a,c\right) \)が与えられれば空間\(\mathbb{R} ^{n}\)を開半空間\begin{eqnarray*}H^{++}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x>c\right\} \\
H^{− −}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x<c\right\}
\end{eqnarray*}へと分割することができます。空間\(\mathbb{R} ^{n}\)は超平面\(H\left( a,c\right) \)と上半空間\(H^{++}\left( a,c\right) \)と下半空間\(H^{− −}\left( a,c\right) \)に分割されます。これら3つの集合は互いに素です。

ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)と点\(y\in \mathbb{R} ^{n}\)および超平面\(H\left( a,c\right) \)が与えられたとき、開上半空間\(H^{++}\left( a,c\right) \)と開下半空間\(H^{− −}\left( a,c\right) \)のどちらか一方が集合\(X\)を部分集合として含むとともに、開上半空間と開下半空間のうち\(X\)を部分集合として含まないほうが点\(y\)を要素として含む場合には、すなわち、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ X\subset H^{++}\left( a,c\right) \wedge y\in
H^{− −}\left( a,c\right) \\
&&\left( b\right) \ X\subset H^{− −}\left( a,c\right) \wedge y\in
H^{++}\left( a,c\right)
\end{eqnarray*}のどちらか一方が成り立つ場合には、集合\(X\)と点\(y\)は超平面\(H\left(a,c\right) \)によって狭義分離される(strictly separated)または強分離されるなどと言います。開半空間の定義より、上の2つの条件を、\begin{eqnarray*}&&\left( a\right) \ \left( \forall x\in X:a\cdot x>c\right) \wedge a\cdot y<c
\\
&&\left( b\right) \ \left( \forall x\in X:a\cdot x<c\right) \wedge a\cdot y>c
\end{eqnarray*}とそれぞれ表現することもできます。

例(超平面によって狭義分離される集合と点)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X\)と点\(y\)が下図で与えられているものとします。

図:超平面によって狭義分離される集合と点
図:超平面によって狭義分離される集合と点

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。上半空間\(H^{+}\left( a,c\right) \)から超平面\(H\left( a,c\right) \)を除いた集合が開上半空間\(H^{++}\left( a,c\right) \)であり、下半空間\(H^{-}\left( a,c\right) \)から超平面\(H\left( a,c\right) \)を除いた集合が開下半空間\(H^{− −}\left( a,c\right) \)です。上図から明らかであるように、\(X\)は\(H^{++}\left( a,c\right) \)の部分集合である一方で\(y\)は\(H^{− −}\left( a,c\right) \)の要素であるため、\(X\)と\(y\)は\(H\left( a,c\right) \)によって狭義分離されています。

例(超平面によって狭義分離される集合と点)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X\)と点\(y\)が下図で与えられているものとします。

図:超平面によって狭義分離される集合と点
図:超平面によって狭義分離される集合と点

\(\mathbb{R} ^{2}\)における超平面は直線です。集合\(X\)は閉集合ではなく境界点を要素として持ちません。つまり、\(X\)はその内部\(X^{i}\)と一致し、その全体が開上半空間\(H^{++}\left( a,c\right) \)に含まれているため\(X\)は\(H^{++}\left( a,c\right) \)の部分集合です。同時に\(y\)は\(H^{− −}\left( a,c\right) \)の要素であるため、\(X\)と\(y\)は\(H\left( a,c\right) \)によって狭義分離されています。

集合と点は超平面によって狭義分離可能であるとは限りません。以下の例より明らかです。

例(超平面によって狭義分離されない集合と点)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X\)と点\(y\)が下図で与えられているものとします。\(y\)は\(X\)の境界点です。

図:超平面によって狭義分離されない集合と点
図:超平面によって狭義分離されない集合と点

\(\mathbb{R} ^{2}\)における超平面は直線です。\(\mathbb{R} ^{2}\)上のいかなる直線によっても集合\(X\)と点\(y\)を狭義分離することはできません。具体例として、上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目すると、点\(y\)は開下半空間\(H^{− −}\left( a,c\right) \)の点である一方で集合\(X\)は開上半空間\(H^{++}\left( a,c\right) \)の部分集合ではありません。他の任意の超平面\(H\left( a,c\right) \)についても同様です。したがって、この集合\(X\)と点\(y\)はいかなる超平面によっても狭義分離することはできません。この例は、集合とその境界点は超平面によって狭義分離できないことを示唆しています。

例(超平面によって狭義分離されない集合と点)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X\)と点\(y\)が下図で与えられているものとします。\(y\)は\(X\)の内点です。

図:超平面によって狭義分離されない集合と点
図:超平面によって狭義分離されない集合と点

\(\mathbb{R} ^{2}\)における超平面は直線です。\(\mathbb{R} ^{2}\)上のいかなる直線によっても集合\(X\)と点\(y\)を狭義分離することはできません。具体例として、上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目すると、点\(y\)は開下半空間\(H^{− −}\left( a,c\right) \)の要素であるものの、集合\(X\)は開上半空間\(H^{++}\left( a,c\right) \)の部分集合ではありません。他の任意の超平面\(H\left( a,c\right) \)についても同様です。したがって、この集合\(X\)と点\(y\)はいかなる超平面によっても狭義分離することはできません。この例は、集合とその内点は超平面によって狭義分離できないことを示唆しています。

例(超平面によって狭義分離されない集合と点)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X\)と点\(y\)が下図で与えられているものとします。この集合\(X\)は凸集合ではありません。

図:超平面によって狭義分離されない集合と点
図:超平面によって狭義分離されない集合と点

\(\mathbb{R} ^{2}\)における超平面は直線です。\(\mathbb{R} ^{2}\)上のいかなる直線によっても集合\(X\)と点\(y\)を狭義分離することはできません。具体例として、上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目すると、点\(y\)は開下半空間\(H^{− −}\left( a,c\right) \)の要素であるものの、集合\(X\)は開上半空間\(H^{++}\left( a,c\right) \)の部分集合ではありません。他の任意の超平面\(H\left( a,c\right) \)についても同様です。したがって、この集合\(X\)と点\(y\)はいかなる超平面によっても狭義分離することはできません。この例は、非凸集合と点は超平面によって狭義分離できないことを示唆しています。

 

狭義分離超平面定理

先の例が示唆するように、ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)が凸集合ではない場合や、点\(y\in \mathbb{R} ^{n}\)が問題としている集合\(X\)の内点や境界点である場合などには、集合\(X\)と点\(y\)はいかなる超平面によっても狭義分離できない可能性があります。では、逆に、集合\(X\)が凸集合であり、なおかつ点\(y\)が問題としている凸集合\(X\)の内点や境界点ではない場合には、すなわち\(y\)が凸集合\(X\)の外点である場合には、集合\(X\)と点\(y\)は何らかの超平面によって狭義分離されるとまで言えるのでしょうか。この問いに答えるのが以下の命題です。これを狭義分離超平面定理(strictly separating hyperplane theorem)と呼びます。

命題(狭義分離超平面定理)
ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)と点\(y\in \mathbb{R} ^{n}\)をそれぞれ任意に選ぶ。\(X\)が\(\mathbb{R} ^{n}\)上の非空な凸集合であるとともに、\(y\)が\(X\)の外点であるならば、すなわち\(y\)が\(X\)の触点でないならば、\(X\)と\(y\)を狭義分離する超平面\(H\left( a,c\right) \)が存在する。具体的には、\begin{equation*}y\in H^{++}\left( a,c\right) \wedge X\subset H^{− −}\left( a,c\right)
\end{equation*}すなわち、\begin{equation*}
a\cdot y>c\wedge \left( \forall x\in X:a\cdot x<c\right)
\end{equation*}を満たす法線ベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)が存在する。
証明

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

上の命題の結論\begin{equation*}
a\cdot y>c\wedge \left( \forall x\in X:a\cdot x<c\right)
\end{equation*}を1つにまとめると、\begin{equation*}
\forall x\in X:a\cdot x<a\cdot y
\end{equation*}すなわち、\begin{equation*}
\forall x\in X:a\cdot \left( x-y\right) <0
\end{equation*}となります。これは、非空な凸集合\(X\)の外点\(y\)が与えられたとき、その点から集合\(X\)上の点\(x\)へ伸びる任意のベクトル\(x-y\)との角度が鋭角になるようなベクトル\(a\)が存在するという主張です。

 

狭義分離超平面定理の言い換え

先の命題において存在が保証される法線ベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)を踏まえた上で、新たな法線ベクトル\(a^{\prime }\)とスカラー\(c^{\prime }\)をそれぞれ、\begin{eqnarray*}a^{\prime } &=&-a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \\
c^{\prime } &=&-c\in \mathbb{R} \end{eqnarray*}と定義します。この新たな法線ベクトル\(a^{\prime }\)とスカラー\(c\)のもとでの超平面は、\begin{equation*}H\left( a^{\prime },c^{\prime }\right) =\left\{ x\in \mathbb{R} ^{n}\ |\ a^{\prime }\cdot x=c^{\prime }\right\}
\end{equation*}となりますが、\begin{eqnarray*}
a^{\prime }\cdot x=c^{\prime } &\Leftrightarrow &-a\cdot x=-c \\
&\Leftrightarrow &a\cdot x=c
\end{eqnarray*}という関係が成り立つため、\begin{equation*}
H\left( a^{\prime },c^{\prime }\right) =H\left( a,c\right)
\end{equation*}となります。つまり、法線ベクトルとスカラーを\(\left( a,c\right) \)から\(\left(a^{\prime },c^{\prime }\right) =\left( -a,-c\right) \)へ入れ替えても超平面としては変わらないということです。ただし、\(a^{\prime }\ \left( =-a\right) \)は\(a\)とは逆向きのベクトルであるため、開上半空間と開下半空間は逆転します。つまり、\begin{eqnarray*}H^{++}\left( a^{\prime },c^{\prime }\right) &=&H^{− −}\left( a,c\right) \\
H^{− −}\left( a^{\prime },c^{\prime }\right) &=&H^{++}\left( a,c\right)
\end{eqnarray*}という関係が成り立つということです。

以上を踏まえた上で、先の命題の結論中の不等式の両辺をスカラー\(-1\)倍すると、\begin{equation*}-a\cdot y<-c\wedge \left( \forall x\in X:-a\cdot x>c\right)
\end{equation*}すなわち、\begin{equation*}
a^{\prime }\cdot y<c^{\prime }\wedge \left( \forall x\in X:a^{\prime }\cdot
x>c^{\prime }\right)
\end{equation*}すなわち、\begin{equation*}
y\in H^{− −}\left( a^{\prime },c^{\prime }\right) \wedge X\subset
H^{++}\left( a^{\prime },c^{\prime }\right)
\end{equation*}を得ます。\(\left( a,c\right) \)が存在する場合には\(\left( a^{\prime},c^{\prime }\right) =\left( -a,-c\right) \)もまた存在するため、先の命題を以下のように表現することもできます。

命題(狭義分離超平面定理)
ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)と点\(y\in \mathbb{R} ^{n}\)をそれぞれ任意に選ぶ。\(X\)が\(\mathbb{R} ^{n}\)上の非空な凸集合であるとともに、\(y\)が\(X\)の外点であるならば、すなわち\(y\)が\(X\)の触点でないならば、\(X\)と\(y\)を狭義分離する超平面\(H\left( a,c\right) \)が存在する。具体的には、\begin{equation*}y\in H^{− −}\left( a,c\right) \wedge X\subset H^{++}\left( a,c\right)
\end{equation*}すなわち、\begin{equation*}
a\cdot y<c\wedge \left( \forall x\in X:a\cdot x>c\right)
\end{equation*}を満たす法線ベクトル\(a\in \mathbb{R} ^{n}\backslash \left\{ 0\right\} \)とスカラー\(c\in \mathbb{R} \)が存在する。

 

演習問題

問題(超平面による凸な閉集合と点の狭義分離)
本文中で明らかにしたように、ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)と点\(y\in \mathbb{R} ^{n}\)をそれぞれ任意に選んだとき、\(X\)が非空な凸集合であるとともに\(y\)が\(X\)の外点である場合には、\(X\)と\(y\)を狭義分離する超平面\(H\left(a,c\right) \)が存在します(狭義分離超平面定理)。一方、\(X\)が非空な凸集合であるとともに閉集合でもある場合には、\(y\)が\(X\)に属さない点であれば、\(X\)と\(y\)を狭義分離する超平面\(H\left( a,c\right) \)が存在することを示してください。
証明

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

Twitter
Mailで保存

質問とコメント

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

関連知識

凸集合の定義

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

狭義凸集合の定義

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

凸包の定義

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

予算超平面(予算線)と限界交換率

予算集合に属する消費ベクトルの中でも、所得をすべて使い切るようなものからなる集合を予算超平面と呼びます。特に、2財モデルにおける予算超平面を予算線と呼びます。関連して、実質所得と名目所得、相対価格と絶対価格を定義します。

予算集合の凸性

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

凸集合のスカラー倍

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

生産集合の凸性

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

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

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

凸集合どうしの直積

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

実数空間において分離している2つの集合

実数空間の2つの部分集合が互いに素であるとともに、どちらも相手の集積点を要素として持たない場合、それらの集合は分離していると言います。分離の概念は触点や開集合を用いて表現することもできます。

実数空間における集合の切断

実数空間の部分集合Xが与えられたとき、開集合A,Bとの交わりをとることによりXを互いに素な2つの非空な集合に分割できる場合、これらの開集合A,BをXの切断と呼びます。

選好の凸性

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

超平面

ユークリッド空間における超平面と呼ばれる概念を定義するとともに、法線ベクトルと超平面の関係や、点と超平面の距離について解説します。

点としての超平面

1次元ユークリッド空間において点(1点集合)と超平面が概念として一致することを示します。

直線としての超平面

ユークリッド空間における直線と呼ばれる概念を定義するとともに、2次元ユークリッド空間において直線と超平面が概念として一致することを示します。