分離超平面定理

分離超平面定理（ぶんりちょうへいめんていり、）は次元ユークリッド空間上の互いに素な凸集合に関する幾何学における 2 つの定理を指す。

一つ目の定理は、互いに素な凸集合の両方が閉集合であってかつ少なくともいずれか 1 つの凸集合がコンパクト集合である場合、2 つの閉凸集合の間に 1 つの超平面が存在でき、また閉凸集合の間に 2 つの平行な超平面を隙間を作って置くことができることを示す。

二つ目の定理は、互いに素な凸集合があり両者が開集合である場合、2 つの開凸集合の間に 1 つの超平面をはさむことができるが、2 つの開凸集合の間には必ずしも隙間が存在するわけではないことを示す（従って第一の定理と異なり、複数の超平面を重ねずに挟むことができない状況が存在する）。

分離超平面に対して直交する軸を分離軸と呼ぶ。これは、2 つのの分離軸への直交写像が互いに素であることによる。

分離超平面定理はヘルマン・ミンコフスキーの寄与によって発見された。ハーン＝バナッハの分離定理はミンコフスキーの結果を線型位相空間へ一般化したものである。

関連する結果としてがある。マージン最大化超平面は空間上にある点の集まりを 2 つのクラスタに分離する超平面の中で、両者のクラスタからの距離が等しいようなものである。このとき、それぞれのクラスタと分離超平面の間のマージンは最大化される。この事実はサポートベクターマシンなどに応用される。

ステートメントと証明

証明は以下の補題に基づく：

補題の証明：上のベクトルのノルムの下限をとする。となるような上の数列について、の凸性よりが成り立つ。また、

であることから

が得られる。上記の関係について極限を取れば右辺は 0 となり、従って

を満たす。すなわちはコーシー列であり、Kは完備であるからその極限値はに含まれるので、はベクトルの最小ノルムとなる。最小ノルムを持つベクトルの一意性について、ベクトルが最小ノルムを持つならば、

となるからである。□

定理の証明：互いに素な空でない凸集合が与えられるとして、次のようなを考える。

は凸なのでもまた凸である。との（したがっての）凸性から上記のミンコフスキー和は凸である。

の閉包は凸なので、先に示した補題よりについて最小ノルムを持つベクトルが一意に定まる。の凸性から、任意のベクトルについて、線分

上の点はすべてに含まれるため、閉包のベクトルのノルムについて以下の関係が成り立つ。

この関係より直ちに次の結果が得られる：

更に、についての極限を取れば上記の関係は

と書き換えられる。従って、任意のおよびについて、

が成り立つ。

ベクトルが零ベクトルでないならば、この関係より

を得て証明を終わる。 == 反例と一意性 ==

またはの一方が凸集合でない場合、「分離定理」に対しては様々な反例が挙げられる。例えばとは同心円状にとることができる。

より微妙な反例として、との両方が閉凸集合だがいずれもコンパクトでない場合が挙げられる。例として、が閉半平面でが双曲線の分枝の一方であるとすれば、この場合には分離超平面は厳密には存在しない（しかしながら、開凸集合に関する分離定理があるためにおよびの内部を分離する超平面が 1 つ存在する）：

他のタイプの反例としてがコンパクトな閉凸集合でありが開凸集合である場合がある。例えば、を正方形の閉集合、を正方形の開集合としてとが接している状況がこれに当てはまる。

閉凸集合に関する分離定理では分離超平面を一意に決めることができないことは明らかである。開集合バージョンの分離定理では、超平面が一意に定まる場合もあるしそうでない場合もあり得る。技術的なことだがこれらのことは分離軸について言い換えられる。閉凸集合の分離定理では分離軸を一意に決められないが、開凸集合の分離定理では分離軸を一意に決定できる。

衝突判定への応用

分離超平面定理

Źródło i licencja