分離超平面定理

分離超平面定理の概略図。

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

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

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

分離超平面に対して直交する軸を分離軸 テンプレート:En と呼ぶ。これは、2 つのテンプレート:仮リンクの分離軸への直交写像が互いに素であることによる。

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

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

ステートメントと証明

証明は以下の補題に基づく： テンプレート:Math theorem

補題の証明テンプレート:Anchors：

テンプレート:Mvar 上のベクトル テンプレート:Mvar のノルムの下限を テンプレート:Math とする。テンプレート:Math となるような テンプレート:Mvar 上の数列 テンプレート:Mvar について、テンプレート:Mvar の凸性より テンプレート:Math が成り立つ。また、

$\left|\frac{x_i+x_j}{2}\right|\ge \inf \{|x|\}=\delta$

であることから

$|x_i-x_j{|}^2=2|x_i{|}^2+2|x_j{|}^2-|x_i+x_j{|}^2\le 2|x_i{|}^2+2|x_j{|}^2-4{\delta }^2$

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

$|x_i-x_j|\le 0$

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

$|x-y{|}^2\le 2|x{|}^2+2|y{|}^2-4{\delta }^2=0$

となるから テンプレート:Math である。□

定理の証明：

互いに素な空でない凸集合 テンプレート:Math が与えられるとして、次のようなテンプレート:仮リンクを考える。

$K=A+(-B)=\{x-y\mid x\in A,y\in B\}.$

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

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

$v+t(u-v),0\le t\le 1$

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

$|v{|}^2\le |v+t(u-v){|}^2=|v{|}^2+2t⟨v,u-v⟩+t^2|u-v{|}^2,(0\le t\le 1).$

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

$0\le 2⟨v,u⟩-2|v{|}^2+t|u-v{|}^2,(0<t\le 1).$

更に、テンプレート:Mvar について テンプレート:Math の極限を取れば上記の関係は

$⟨v,u⟩\ge |v{|}^2$

と書き換えられる。従って、任意の テンプレート:Math および テンプレート:Math について、

$⟨v,x-y⟩\ge |v{|}^2$

が成り立つ。

ベクトル テンプレート:Mvar が零ベクトルでないならば、この関係より

$\underset{x\in A}{\inf }⟨x,v⟩\ge |v{|}^2+\underset{y\in B}{\sup }⟨y,v⟩$

を得て証明を終わる。

反例と一意性

定理の適用できないケース：一方（または両方）の集合が凸でない

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

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

$A=\{(x,y):x\le 0\}$

$B=\{(x,y):x>0,y\ge 1/x\}.$

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

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

関連項目

• 双対錐
• テンプレート:仮リンク

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book

外部リンク

• Collision detection and response