支持超平面定理（超平面による凸集合の支持）

超平面による集合の支持

ユークリッド空間\(\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) \)に分割されますが、上半空間と下半空間は互いに素ではなく、両者の交わりは超平面と一致します。

ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)が与えられたとき、上半空間\(H^{+}\left( a,c\right) \)と下半空間\(H^{-}\left( a,c\right) \)のどちらか一方が集合\(X\)を部分集合として含むとともに、集合\(X\)の少なくとも1つの境界点\(y\)が超平面\(H\left( a,c\right) \)上にあるならば、すなわち、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ X\subset H^{+}\left( a,c\right) \wedge \exists y\in
X^{f}:y\in H\left( a,c\right) \\
&&\left( b\right) \ X\subset H^{-}\left( a,c\right) \wedge \exists y\in
X^{f}:y\in H\left( a,c\right)
\end{eqnarray*}のどちらか一方が成り立つ場合には、集合\(X\)は境界点\(y\)において超平面\(H\left( a,c\right) \)によって支持される（supported）と言います。またこのとき、超平面\(H\left(a,c\right) \)を境界点\(y\)における集合\(X\)の支持超平面（supporting hyperplane）と呼びます。半空間の定義より、上の2つの条件を、\begin{eqnarray*}&&\left( a\right) \ \left( \forall x\in X:a\cdot x\geq c\right) \wedge
\left( \exists y\in X^{f}:a\cdot x=c\right) \\
&&\left( b\right) \ \left( \forall x\in X:a\cdot x\leq c\right) \wedge
\left( \exists y\in X^{f}:a\cdot x=c\right)
\end{eqnarray*}とそれぞれ表現することもできます。ただし、\(X^{f}\)は集合\(X\)の境界です。

例（超平面によって支持される集合）

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

\(\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) \)の部分集合であるとともに\(X\)の点\(y\)が\(H\left( a,c\right) \)上にあります。この点\(y\)は\(X\)の境界点であるため、\(X\)は\(y\)において\(H\left( a,c\right) \)によって支持されていることが明らかになりました。

例（超平面によって支持される集合）

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

 

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。集合\(X\)は\(H^{+}\left( a,c\right) \)の部分集合です。\(H\left( a,c\right) \)上にある点\(y\)は\(X\)の要素ではありませんが\(X\)の境界点ではあるため、\(X\)は\(y\)において\(H\left( a,c\right) \)によって支持されていることが明らかになりました。

例（超平面によって支持される集合）

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

\(\mathbb{R} ^{2}\)における超平面は直線です。上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目します。集合\(X\)は\(H^{+}\left( a,c\right) \)の部分集合であるとともに\(X\)の点\(y\)が\(H\left( a,c\right) \)上にあります。この点\(y\)は\(X\)の境界点であるため、\(X\)は\(y\)において\(H\left( a,c\right) \)によって支持されていることが明らかになりました。

集合はその任意の境界点において超平面によって支持されるとは限りません。境界点によっては、集合を支持する超平面が存在しない状況が起こり得るということです。以下の例より明らかです。

例（超平面によって支持されない境界点を持つ集合）

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

\(\mathbb{R} ^{2}\)における超平面は直線です。点\(y\)は集合\(X\)の境界点ですが、この点\(y\)において集合\(X\)を支持する超平面は存在しません。具体例として、上図中の直線に相当する超平面\(H\left( a,c\right) \)に注目すると、点\(y\)は\(H\left( p,c\right) \)の要素ではあるものの、集合\(X\)は上半空間\(H^{+}\left( a,c\right) \)や下半空間\(H^{-}\left( a,c\right) \)の部分集合ではないため、この\(H\left( p,c\right) \)は\(y\)において\(X\)を支持していません。他の任意の超平面\(H\left( a,c\right) \)についても同様です。したがって、この集合\(X\)はその境界点\(y\)においていかなる超平面によっても支持することはできません。この例は、非凸集合の境界点の中には、その点においてその集合を支持する超平面が存在しない状況が起こり得ることが明らかになりました。

支持超平面定理

先の例が示唆するように、ユークリッド空間上の集合\(X\subset \mathbb{R} ^{n}\)が凸集合ではない場合には、その何らかの境界点\(y\)において、\(X\)を\(y\)において支持する超平面が存在しない状況は起こり得ます。では、逆に、集合\(X\)が凸集合である場合には、その境界点\(y\)を任意に選んだとき、\(X\)を\(y\)において支持する超平面が存在することを保証できるのでしょうか。この問いに答えるのが以下の命題です。これを支持超平面定理（supporting hyperplane theorem）と呼びます。

上の命題の結論\begin{equation*}
a\cdot y=c\wedge \left( \forall x\in X:a\cdot x\leq c\right)
\end{equation*}を1つにまとめると、\begin{equation*}
\forall x\in X:a\cdot x\leq a\cdot y
\end{equation*}すなわち、\begin{equation*}
\forall x\in X:a\cdot \left( x-y\right) \leq 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 \forall x\in X:-a\cdot x\geq -c
\end{equation*}すなわち、\begin{equation*}
a^{\prime }\cdot y=c^{\prime }\wedge \left( \forall x\in X:a^{\prime }\cdot
x\geq 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) \)もまた存在するため、先の命題を以下のように表現することもできます。