分離ぶんり超ちょう平面へいめん定理ていり

分離ぶんり超ちょう平面へいめん定理ていり（ぶんりちょうへいめんていり、英えい: separating hyperplane theorem, hyperplane separation theorem）は $n$ 次元じげんユークリッド空間くうかん上うえの互たがいに素もとな凸とつ集合しゅうごうに関かんする幾何きか学がくにおける 2 つの定理ていりを指さす。

一ひとつ目めの定理ていりは、互たがいに素そな凸とつ集合しゅうごうの両方りょうほうが閉集合しゅうごうであってかつ少すくなくともいずれか 1 つの凸とつ集合しゅうごうがコンパクト集合しゅうごうである場合ばあい、2 つの閉凸集合しゅうごうの間あいだに 1 つの超ちょう平面へいめんが存在そんざいでき、また閉凸集合しゅうごうの間あいだに 2 つの平行へいこうな超ちょう平面へいめんを隙間すきまを作つくって置おくことができることを示しめす。

二ふたつ目めの定理ていりは、互たがいに素そな凸とつ集合しゅうごうがあり両者りょうしゃが開ひらけ集合しゅうごうである場合ばあい、2 つの開ひらき凸とつ集合しゅうごうの間あいだに 1 つの超ちょう平面へいめんをはさむことができるが、2 つの開ひらき凸とつ集合しゅうごうの間あいだには必かならずしも隙間すきまが存在そんざいするわけではないことを示しめす（従したがって第だい一いちの定理ていりと異ことなり、複数ふくすうの超ちょう平面へいめんを重かさねずに挟はさむことができない状況じょうきょうが存在そんざいする）。

分離ぶんり超ちょう平面へいめんに対たいして直交ちょっこうする軸じくを分離ぶんり軸じく (separating axis) と呼よぶ。これは、2 つの凸とつ体たい（英語えいご版ばん）の分離ぶんり軸じくへの直交ちょっこう写像しゃぞうが互たがいに素そであることによる。

分離ぶんり超ちょう平面へいめん定理ていりはヘルマン・ミンコフスキーの寄与きよによって発見はっけんされた。ハーン＝バナッハの分離ぶんり定理ていりはミンコフスキーの結果けっかを線型せんけい位相いそう空間くうかんへ一般いっぱん化かしたものである。

関連かんれんする結果けっかとして支持しじ超ちょう平面へいめん定理ていり（英語えいご版ばん）がある。マージン最大さいだい化か超ちょう平面へいめん (maximum-margin hyperplane) は空間くうかん上じょうにある点てんの集あつまりを 2 つのクラスタに分離ぶんりする超ちょう平面へいめんの中なかで、両者りょうしゃのクラスタからの距離きょりが等ひとしいようなものである。このとき、それぞれのクラスタと分離ぶんり超ちょう平面へいめんの間あいだのマージンは最大さいだい化かされる。この事実じじつはサポートベクターマシンなどに応用おうようされる。

ステートメントと証明しょうめい

分離ぶんり超ちょう平面へいめん定理ていり^[1] ― $A$ と $B$ をそれぞれ $R n$ の互たがいに素もとな空そらでない凸とつ部分ぶぶん集合しゅうごうであるとする。そのような集合しゅうごうについて、すべての $A$ の元もと $x \in A$ と $B$ の元もと $y \in B$ の組くみに対たいして

\langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c

を満みたす零れいでないベクトル $v$ と実数じっすう $c$ が存在そんざいする。つまり、 $v$ を法線ほうせんベクトルとする超ちょう平面へいめん $〈\cdot, v 〉 = c$ によって $A$ と $B$ を分離ぶんりできる。

証明しょうめいは以下いかの補題ほだいに基もとづく：

補題ほだい ― $K$ を $R n$ の空そらでない閉凸部分ぶぶん集合しゅうごうとする。集合しゅうごう $K$ について、 $K$ 上うえの最小さいしょうノルムを持もつベクトルが一意いちいに存在そんざいする。

補題ほだいの証明しょうめい：

$K$ 上うえのベクトル $x$ のノルムの下限かげんを $δ でるた = inf{| x | | x \in K}$ とする。 $| x j | \to δ でるた$ となるような $K$ 上うえの数列すうれつ $x j$ について、 $K$ の凸とつ性せいより $| x i + x j |/2 \in K$ が成なり立たつ。また、

\left|{\frac {x_{i}+x_{j}}{2}}\right|\geq \inf\{|x|\}=\delta

であることから

|x_{i}-x_{j}|^{2}=2|x_{i}|^{2}+2|x_{j}|^{2}-|x_{i}+x_{j}|^{2}\leq 2|x_{i}|^{2}+2|x_{j}|^{2}-4\delta ^{2}

が得えられる。上記じょうきの関係かんけいについて極限きょくげんを取とれば右辺うへんは 0 となり、従したがって

|x_{i}-x_{j}|\leq 0

を満みたす。すなわち $x i$ はコーシー列れつであり、Kは完備かんびであるからその極限きょくげん値ちは $K$ に含ふくまれるので、 $δ でるた$ はベクトル $x \in K$ の最小さいしょうノルムとなる。最小さいしょうノルムを持もつベクトルの一意いちい性せいについて、ベクトル $y \in K$ が最小さいしょうノルム $δ でるた$ を持もつならば、

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

となるから $x = y$ である。□

定理ていりの証明しょうめい：

互たがいに素そな空そらでない凸とつ集合しゅうごう $A, B$ が与あたえられるとして、次つぎのようなミンコフスキー和わ（英語えいご版ばん）を考かんがえる。

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

$B$ は凸とつなので $- B$ もまた凸とつである。 $A$ と $- B$ の（したがって $B$ の）凸とつ性せいから上記じょうきのミンコフスキー和わ $K$ は凸とつである。

$K$ の閉包へいほう $K$ は凸とつなので、先さきに示しめした補題ほだいより $K$ について最小さいしょうノルムを持もつベクトル $v$ が一意いちいに定さだまる。 $K$ の凸とつ性せいから、任意にんいのベクトル $u \in K$ について、線分せんぶん

v+t(u-v),\,0\leq t\leq 1

上うえの点てんはすべて $K$ に含ふくまれるため、閉包へいほう $K$ のベクトルのノルムについて以下いかの関係かんけいが成なり立たつ。

|v|^{2}\leq |v+t(u-v)|^{2}=|v|^{2}+2t\langle v,u-v\rangle +t^{2}|u-v|^{2},\quad (0\leq t\leq 1).

この関係かんけいより直ただちに次つぎの結果けっかが得えられる：

0\leq 2\langle v,u\rangle -2|v|^{2}+t|u-v|^{2},\quad (0<t\leq 1).

更さらに、 $t$ について $t \to 0$ の極限きょくげんを取とれば上記じょうきの関係かんけいは

\langle v,u\rangle \geq |v|^{2}

と書かき換かえられる。従したがって、任意にんいの $x \in A$ および $y \in B$ について、

\langle v,x-y\rangle \geq |v|^{2}

が成なり立たつ。

ベクトル $v$ が零れいベクトルでないならば、この関係かんけいより

\inf _{x\in A}\langle x,v\rangle \geq |v|^{2}+\sup _{y\in B}\langle y,v\rangle

を得えて証明しょうめいを終おわる。

反例はんれいと一意いちい性せい

$A$ または $B$ の一方いっぽうが凸とつ集合しゅうごうでない場合ばあい、「分離ぶんり定理ていり」に対たいしては様々さまざまな反例はんれいが挙あげられる。例たとえば $A$ と $B$ は同心円どうしんえん状じょうにとることができる。

より微妙びみょうな反例はんれいとして、 $A$ と $B$ の両方りょうほうが閉凸集合しゅうごうだがいずれもコンパクトでない場合ばあいが挙あげられる。例れいとして、 $A$ が閉半平面へいめんで $B$ が双曲線そうきょくせんの分ぶん枝えだの一方いっぽうであるとすれば、この場合ばあいには分離ぶんり超ちょう平面へいめんは厳密げんみつには存在そんざいしない（しかしながら、開ひらき凸とつ集合しゅうごうに関かんする分離ぶんり定理ていりがあるために $A$ および $B$ の内部ないぶを分離ぶんりする超ちょう平面へいめんが 1 つ存在そんざいする）：

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

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

他たのタイプの反例はんれいとして $A$ がコンパクトな閉凸集合しゅうごうであり $B$ が開ひらけ凸とつ集合しゅうごうである場合ばあいがある。例たとえば、 $A$ を正方形せいほうけいの閉集合しゅうごう、 $B$ を正方形せいほうけいの開ひらき集合しゅうごうとして $A$ と $B$ が接せっしている状況じょうきょうがこれに当あてはまる。

閉凸集合しゅうごうに関かんする分離ぶんり定理ていりでは分離ぶんり超ちょう平面へいめんを一意いちいに決きめることができないことは明あきらかである。開ひらき集合しゅうごうバージョンの分離ぶんり定理ていりでは、超ちょう平面へいめんが一意いちいに定さだまる場合ばあいもあるしそうでない場合ばあいもあり得える。技術ぎじゅつ的てきなことだがこれらのことは分離ぶんり軸じくについてい換いかえられる。閉凸集合しゅうごうの分離ぶんり定理ていりでは分離ぶんり軸じくを一意いちいに決きめられないが、開ひらき凸とつ集合しゅうごうの分離ぶんり定理ていりでは分離ぶんり軸じくを一意いちいに決定けっていできる。

衝突しょうとつ判定はんていへの応用おうよう

脚注きゃくちゅう

^ Boyd & Vandenberghe 2004, Exercise 2.22..

参考さんこう文献ぶんけん

Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3
Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9
Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1

外部がいぶリンク

Collision detection and response

[FOOTNOTEBoydVandenberghe2004Exercise_2.22.-1] Boyd & Vandenberghe 2004, Exercise 2.22..

[1]