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

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

ユークリッド空間\(\mathbb{R} ^{n}\)における超平面とは、法線ベクトル\(\boldsymbol{a}\in \mathbb{R} ^{n}\backslash \left\{ \boldsymbol{0}\right\} \)とスカラー\(c\in \mathbb{R} \)から、\begin{equation*}H\left( \boldsymbol{a},c\right) =\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{a}\cdot \boldsymbol{x}=c\right\}
\end{equation*}と定義される\(\mathbb{R} ^{n}\)の部分集合です。超平面\(H\left( \boldsymbol{a},c\right) \)が与えられれば空間\(\mathbb{R} ^{n}\)を半空間\begin{eqnarray*}H^{+}\left( \boldsymbol{a},c\right) &=&\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{a}\cdot \boldsymbol{x}\geq c\right\} \\
H^{-}\left( \boldsymbol{a},c\right) &=&\left\{ \boldsymbol{x}\in \mathbb{R} ^{n}\ |\ \boldsymbol{a}\cdot \boldsymbol{x}\leq c\right\}
\end{eqnarray*}へと分割できます。空間\(\mathbb{R} ^{n}\)は超平面\(H\left( \boldsymbol{a},c\right) \)を境に上半空間\(H^{+}\left( \boldsymbol{a},c\right) \)と下半空間\(H^{-}\left( \boldsymbol{a},c\right) \)に分割されますが、上半空間と下半空間は互いに素ではなく、両者の交わりは超平面と一致します。

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

例（超平面によって分離される2つの集合）

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

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( \boldsymbol{a},c\right) \)に注目します。空間\(\mathbb{R} ^{2}\)は超平面\(H\left( \boldsymbol{a},c\right) \)を境に上半空間\(H^{+}\left( \boldsymbol{a},c\right) \)と下半空間\(H^{-}\left( \boldsymbol{a},c\right) \)に分割されますが、両者の交わりが\(H\left( \boldsymbol{a},c\right) \)です。集合\(X\)は\(H^{+}\left( \boldsymbol{a},c\right) \)の部分集合であるとともに集合\(Y\)は\(H^{-}\left( \boldsymbol{a},c\right) \)の部分集合であるため、\(X\)と\(Y\)は\(H\left( \boldsymbol{a},c\right) \)によって分離されています。

例（超平面によって分離される2つの集合）

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

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

例（超平面によって分離される2つの集合）

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

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

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

例（超平面によって分離されない2つの集合）

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

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

例（超平面によって分離されない2つの集合）

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

\(\mathbb{R} ^{2}\)における超平面は直線です。この2つの集合\(X,Y\)はいかなる超平面によっても分離不可能です。具体例として、上図の直線として表される超平面\(H\left( \boldsymbol{a},c\right) \)に注目します。集合\(X\)は\(H^{+}\left( \boldsymbol{a},c\right) \)の部分集合である一方で集合\(Y\)は\(H^{-}\left( \boldsymbol{a},c\right) \)の部分集合ではないため、\(X\)と\(Y\)は\(H\left( \boldsymbol{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）などと呼びます。

先の命題の結論\begin{equation*}
\forall \boldsymbol{x}\in X,\ \forall \boldsymbol{y}\in Y:\boldsymbol{a}\cdot \boldsymbol{x}\leq c\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}より、\begin{equation*}
\forall \boldsymbol{x}\in X,\ \forall \boldsymbol{y}\in Y:\boldsymbol{a}\cdot \boldsymbol{x}\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}すなわち、\begin{equation*}
\forall \boldsymbol{x}\in X,\ \forall \boldsymbol{y}\in Y:\boldsymbol{a}\cdot \left( \boldsymbol{x}-\boldsymbol{y}\right) \leq 0
\end{equation*}を得ます。これは、非空かつ互いに素な2つの凸集合\(X,Y\)が与えられたとき、\(Y\)上の点から\(X\)上の点へ伸びる任意のベクトルとの角度が直角または鈍角になるような非ゼロベクトル\(\boldsymbol{a}\)が存在するという主張です。

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

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

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

分離超平面定理の逆の主張

ユークリッド空間上の集合\(X,Y\subset \mathbb{R} ^{n}\)がともに非空な凸集合であるとともに両者が互いに素である場合には、\(X\)と\(Y\)を分離する超平面\(H\left( \boldsymbol{a},c\right) \)が存在することが明らかになりましたが、その逆の主張は成り立つとは限りません。つまり、\(X,Y\)がともに非空な凸集合であるとともに両者を分離する超平面\(H\left( \boldsymbol{a},c\right) \)が存在する状況において、\(X\)と\(Y\)は互いに素であるとは限りません。以下の例より明らかです。

支持関数を用いた分離超平面定理の解釈

分離超平面定理の結論\begin{equation*}
\forall \boldsymbol{x}\in X,\ \forall \boldsymbol{y}\in Y:\boldsymbol{a}\cdot \boldsymbol{x}\leq c\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}より、\begin{equation*}
\forall \boldsymbol{x}\in X,\ \forall \boldsymbol{y}\in Y:\boldsymbol{a}\cdot \boldsymbol{x}\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}が得られます。このとき、\(\boldsymbol{a}\cdot \boldsymbol{x}\)がとり得る値からなる集合は上に有界であるため、実数の連続性より、\begin{equation*}\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}
\end{equation*}が有限な実数として定まります。また、\(\boldsymbol{a}\cdot \boldsymbol{y}\)がとり得る値からなる集合は下に有界であるため、実数の連続性より、\begin{equation*}\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}が有限な実数として定まります。その上で、\begin{equation*}
\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\leq \inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}が成り立ちます。この意味を以下のように理解できます。

法線ベクトル\(\boldsymbol{a}\in \mathbb{R} ^{n}\backslash \left\{ \boldsymbol{0}\right\} \)とベクトル\(\boldsymbol{x}\in X\)が与えられたとき、\(\boldsymbol{x}\)の\(\boldsymbol{a}\)へのベクトル射影は、\begin{equation*}\mathrm{proj}_{\boldsymbol{a}}\boldsymbol{x}=\frac{\boldsymbol{a}\cdot \boldsymbol{x}}{\left\Vert \boldsymbol{a}\right\Vert ^{2}}\boldsymbol{a}
\end{equation*}として与えられるため、その大きさは、\begin{eqnarray*}
\left\Vert \mathrm{proj}_{\boldsymbol{a}}\boldsymbol{x}\right\Vert
&=&\left\Vert \frac{\boldsymbol{a}\cdot \boldsymbol{x}}{\left\Vert
\boldsymbol{a}\right\Vert ^{2}}\boldsymbol{a}\right\Vert \\
&=&\frac{\left\vert \boldsymbol{a}\cdot \boldsymbol{x}\right\vert }{\left\Vert \boldsymbol{a}\right\Vert ^{2}}\left\Vert \boldsymbol{a}\right\Vert \\
&=&\frac{\left\vert \boldsymbol{a}\cdot \boldsymbol{x}\right\vert }{\left\Vert \boldsymbol{a}\right\Vert }
\end{eqnarray*}となるため、\begin{equation*}
\left\vert \boldsymbol{a}\cdot \boldsymbol{x}\right\vert =\left\Vert
\boldsymbol{a}\right\Vert \cdot \left\Vert \mathrm{proj}_{\boldsymbol{a}}\boldsymbol{x}\right\Vert
\end{equation*}を得ます。特に、\(\boldsymbol{a}\)と\(\boldsymbol{x}\)のなす角が鋭角である場合には\(\boldsymbol{a}\cdot \boldsymbol{x}>0\)であるため、\begin{equation*}\boldsymbol{a}\cdot \boldsymbol{x}=\left\Vert \boldsymbol{a}\right\Vert
\cdot \left\Vert \mathrm{proj}_{\boldsymbol{a}}\boldsymbol{x}\right\Vert
\end{equation*}を得ます。つまり、内積\(\boldsymbol{a}\cdot \boldsymbol{x}\)の値は、\(X\)上のベクトル\(\boldsymbol{x}\)を法線ベクトル\(\boldsymbol{a}\)の方向に射影した場合の到達可能な長さを表しています。\(X\)上のすべてのベクトル\(\boldsymbol{x}\)について同様に\(\boldsymbol{a}\cdot \boldsymbol{x}\)を特定した上で、その中の上限\begin{equation*}\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}
\end{equation*}をとれば、これは、\(X\)に属するすべてのベクトルを法線ベクトル\(\boldsymbol{a}\)の方向に射影した場合の到達可能な長さの上限を表しています。同様の理由により、\begin{equation*}\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}をとることができますが、これは、\(Y\)に属するすべてのベクトルを法線ベクトル\(\boldsymbol{a}\)の方向に射影した場合の到達可能な長さの下限を表しています。そのような中で、\begin{equation}\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\leq \inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y} \quad \cdots (1)
\end{equation}が成り立つこととは、\(X\)に属するどのベクトルを\(\boldsymbol{a}\)の方向に射影しても、\(Y\)に属するベクトルを\(\boldsymbol{a}\)の方向に射影した場合の長さ以下であることを意味します。したがって、この場合には\(X\)と\(Y\)を分離する超平面が存在します。具体例として、以下の超平面\begin{equation}H\left( \boldsymbol{a},\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot
\boldsymbol{x}\right) \quad \cdots (2)
\end{equation}に注目します。\(\left( 1\right) \)より、\begin{equation*}\forall \boldsymbol{y}\in Y:\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot
\boldsymbol{x}\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}すなわち、\begin{equation*}
\forall \boldsymbol{y}\in Y:\boldsymbol{y}\in H^{+}\left( \boldsymbol{a},\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\right)
\end{equation*}すなわち、\begin{equation*}
Y\subset H^{+}\left( \boldsymbol{a},\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\right)
\end{equation*}が成り立ち、上限の定義より、\begin{equation*}
\forall \boldsymbol{x}\in X:\boldsymbol{a}\cdot \boldsymbol{x}\leq \sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}
\end{equation*}すなわち、\begin{equation*}
X\subset H^{-}\left( \boldsymbol{a},\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\right)
\end{equation*}が成り立つため、\(\left(2\right) \)は\(X\)と\(Y\)を分離する超平面の1つです。別の例として、以下の超平面\begin{equation}H\left( \boldsymbol{a},\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot
\boldsymbol{y}\right) \quad \cdots (3)
\end{equation}に注目します。\(\left( 1\right) \)より、\begin{equation*}\forall \boldsymbol{x}\in X:\boldsymbol{a}\cdot \boldsymbol{x}\leq \inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}すなわち、\begin{equation*}
\forall \boldsymbol{x}\in X:\boldsymbol{x}\in H^{-}\left( \boldsymbol{a},\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y}\right)
\end{equation*}が成り立ち、下限の定義より、\begin{equation*}
\forall \boldsymbol{y}\in Y:\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot
\boldsymbol{y}\leq \boldsymbol{a}\cdot \boldsymbol{y}
\end{equation*}すなわち、\begin{equation*}
Y\subset H^{+}\left( \boldsymbol{a},\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}\right)
\end{equation*}が成り立つため、\(\left(3\right) \)もまた\(X\)と\(Y\)を分離する超平面の1つです。

ちなみに、非空な凸集合\(X\subset \mathbb{R} ^{n}\)が与えられたとき、それぞれの非ゼロベクトル\(\boldsymbol{a}\in \mathbb{R} ^{n}\backslash \left\{ \boldsymbol{0}\right\} \)に対して、\begin{equation*}h_{X}\left( \boldsymbol{a}\right) =\sup_{\boldsymbol{x}\in X}\boldsymbol{a}\cdot \boldsymbol{x}
\end{equation*}を定める関数\begin{equation*}
h_{X}:\mathbb{R} ^{n}\backslash \left\{ 0\right\} \rightarrow \mathbb{R} \end{equation*}を支持関数と呼びます。さらに、\begin{eqnarray*}
\inf_{\boldsymbol{y}\in Y}\boldsymbol{a}\cdot \boldsymbol{y} &=&-\sup_{\boldsymbol{y}\in Y}\left( -\left( \boldsymbol{a}\cdot \boldsymbol{x}\right)
\right) \quad \because \text{上限と下限の関係} \\
&=&-\sup_{\boldsymbol{y}\in Y}\left( \left( -\boldsymbol{a}\right) \cdot
\boldsymbol{x}\right) \\
&=&-h_{Y}\left( -\boldsymbol{a}\right) \quad \because \text{支持関数の定義}
\end{eqnarray*}が成り立つことを踏まえると、先の命題\(\left( 1\right) \)を、\begin{equation*}h_{X}\left( \boldsymbol{a}\right) \leq -h_{Y}\left( -\boldsymbol{a}\right)
\end{equation*}すなわち、\begin{equation*}
h_{X}\left( \boldsymbol{a}\right) +h_{Y}\left( -\boldsymbol{a}\right) \leq 0
\end{equation*}と表現できますが、その直感的意味は先述の通りです。

狭義分離超平面定理

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

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

2つの集合\(X,Y\subset \mathbb{R} ^{n}\)がともに非空な凸集合であるとともに両者が互いに素であるならば、分離超平面定理より、\(X\)と\(Y\)を分離する超平面\(H\left( \boldsymbol{a},c\right) \)が存在します。しかし、この超平面\(H\left( \boldsymbol{a},c\right) \)は\(X\)と\(Y\)を狭義分離するとは限りません。以下の例より明らかです。

2つの集合\(X,Y\subset \mathbb{R} ^{n}\)を狭義分離する超平面の存在を保証するためには、\(X,Y\)が互いに素な非空の凸集合であるという条件に加えて、\(X\)と\(Y\)の間の距離が正であるという条件、すなわち、\begin{equation*}d\left( X,Y\right) >0
\end{equation*}が必要です。

演習問題