教材一覧
教材一覧
教材検索

凸集合

分離超平面定理(超平面による2つの凸集合の分離)

目次

Twitter
Mailで保存

超平面による2つの集合の分離

ユークリッド空間\(\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\geq c\right\} \\
H^{-}\left( a,c\right) &=&\left\{ x\in \mathbb{R} ^{n}\ |\ a\cdot x\leq c\right\}
\end{eqnarray*}へと分割することができます。空間\(\mathbb{R} ^{n}\)は超平面\(H\left( a,c\right) \)を境に上半空間\(H^{+}\left( a,c\right) \)と下半空間\(H^{-}\left( a,c\right) \)に分割されますが、上半空間と下半空間は互いに素ではなく、両者の交わりは超平面と一致します。

ユークリッド空間上の2つの集合\(X,Y\subset \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\subset
H^{-}\left( a,c\right) \\
&&\left( b\right) \ X\subset H^{-}\left( a,c\right) \wedge Y\subset
H^{+}\left( a,c\right)
\end{eqnarray*}のどちらか一方が成り立つ場合には、2つの集合\(X,Y\)は超平面\(H\left(a,c\right) \)によって分離される(separated)と言います。半空間の定義より、上の2つの条件を、\begin{eqnarray*}&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:\left( a\cdot x\geq
c\wedge a\cdot y\leq c\right) \\
&&\left( b\right) \ \forall x\in X,\ \forall y\in Y:\left( a\cdot x\leq
c\wedge a\cdot y\geq c\right)
\end{eqnarray*}すなわち、\begin{eqnarray*}
&&\left( a\right) \ \forall x\in X,\ \forall y\in Y:a\cdot y\leq c\leq
a\cdot x \\
&&\left( b\right) \ \forall x\in X,\ \forall y\in Y:a\cdot x\leq c\leq
a\cdot y
\end{eqnarray*}とそれぞれ表現することもできます。

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

図:超平面によって分離される2つの集合
図:超平面によって分離される2つの集合

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。空間\(\mathbb{R} ^{2}\)は超平面\(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つの集合)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)における集合\(X,Y\)が下図で与えられているものとします。

図:超平面によって分離される2つの集合
図:超平面によって分離される2つの集合

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。2つの集合\(X,Y\)は超平面\(H\left( a,c\right) \)上の1点で交わっています。ただ、集合\(X\)は\(H^{+}\left( a,c\right) \)の部分集合であるとともに集合\(Y\)は\(H^{-}\left( a,c\right) \)の部分集合であるため、\(X\)と\(Y\)は\(H\left( a,c\right) \)によって分離されています。

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

図:超平面によって分離される2つの集合
図:超平面によって分離される2つの集合

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。2つの集合\(X,Y\)は超平面\(H\left( a,c\right) \)上の1点で交わっています。ただ、集合\(X\)は\(H^{+}\left( a,c\right) \)の部分集合であるとともに集合\(Y\)は\(H^{-}\left( a,c\right) \)の部分集合であるため、\(X\)と\(Y\)は\(H\left( a,c\right) \)によって分離されています。

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

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

図:超平面によって分離されない2つの集合
図:超平面によって分離されない2つの集合

\(\mathbb{R} ^{2}\)における超平面は直線です。この2つの集合\(X,Y\)はいかなる超平面によっても分離不可能です。具体例として、上図の直線として表される超平面\(H\left(a,c\right) \)に注目します。集合\(Y\)は\(H^{-}\left( a,c\right) \)の部分集合である一方で集合\(X\)は\(H^{+}\left( a,c\right) \)の部分集合ではないため、\(X\)と\(Y\)は\(H\left( a,c\right) \)によって分離されません。他の任意の超平面についても同様です。この例は、互いに素ではない2つの集合はいかなる超平面によっても分離されないことを示唆しています。

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

図:超平面によって分離されない2つの集合
図:超平面によって分離されない2つの集合

\(\mathbb{R} ^{2}\)における超平面は直線です。この2つの集合\(X,Y\)はいかなる超平面によっても分離不可能です。具体例として、上図の直線として表される超平面\(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つの集合のうちの少なくとも一方が凸集合でない場合には、2つの集合はいかなる超平面によっても分離されない状況が起こり得ることを示唆しています。

 

分離超平面定理

先の例が示唆するように、ユークリッド空間上の2つの集合\(X,Y\subset \mathbb{R} ^{n}\)が互いに素でない場合や、少なくとも一方が凸集合ではない場合などには、これらの集合\(X,Y\)はいかなる超平面によっても分離できない可能性があります。では、逆に、集合\(X,Y\)が互いに素であり、なおかつ\(X,Y\)がともに凸集合である場合には、これらの集合\(X,Y\)を何らかの超平面によって分離されるとまで言えるのでしょうか。この問いに答えるのが以下の命題です。これを分離超平面定理(separating hyperplane theorem)やミンコフスキーの定理(Minkowski’s theorem)などと呼びます。

命題(分離超平面定理)

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

証明

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

上の命題の結論\begin{equation*}
\forall x\in X,\ \forall y\in Y:a\cdot x\leq c\leq a\cdot y
\end{equation*}より、\begin{equation*}
\forall x\in X,\ \forall y\in Y:a\cdot x\leq a\cdot y
\end{equation*}すなわち、\begin{equation*}
\forall x\in X,\ \forall y\in Y:a\cdot \left( x-y\right) \leq 0
\end{equation*}を得ます。これは、非空かつ互いに素な2つの凸集合\(X,Y\)が与えられたとき、\(Y\)上の点から\(X\)上の点へ伸びる任意のベクトルとの角度が直角または鈍角になるような非ゼロベクトル\(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*}\forall x\in X,\ \forall y\in Y:-a\cdot x\geq -c\geq -a\cdot y
\end{equation*}すなわち、\begin{equation*}
\forall x\in X,\ \forall y\in Y:a^{\prime }\cdot x\geq c^{\prime }\geq
a^{\prime }\cdot y
\end{equation*}すなわち、\begin{equation*}
X\subset H^{+}\left( a^{\prime },c^{\prime }\right) \wedge Y\subset
H^{-}\left( a^{\prime },c^{\prime }\right)
\end{equation*}を得ます。\(\left( a,c\right) \)が存在する場合には\(\left( a^{\prime},c^{\prime }\right) =\left( -a,-c\right) \)もまた存在するため、先の命題を以下のように表現することもできます。

命題(分離超平面定理)

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

Twitter
Mailで保存

質問とコメント

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

関連知識