分離定理・講義ノート
金
子
太
郎
．は じ め に
金 子（ ）で 双 対 定 理 を ミ ン コ フ ス キ ー・フ ァ ル カ ス の 補 題 （Minkowski-Farkas lemma）を前提に示したが，この補題の証明には分離 定理（separation theorem）を用いると書いただけで，分離定理については 説明を一切省略した。ただ，この定理は非常に重要な定理で，応用範囲も 非常に広いので，ここに法学部生でも読めるように，読み切りの形で説明 して，金子（ ）の証明を完結させておこう。．用語の定義
まず，以下で使う概念，記号の意味を説明することから始めよう。 ノルム： エル "次元ユークリッド空間（"" ）の点 $に対して $$$! ! #!! " $#& " をノルムと言う。 ""の つ の 点$!"$ !!%%!$"#%!"%!!%%!%"#に 対 し て，$と %の図 ( (# 図 ) )# ( (# (" (" )" 間の距離を"%(!)&と書き，これを "%(!)&#,(!),# ! &#" #
%(&!)&&#
# とする（,(!),が (と )の間の距離であることは証明を要することだが 省略）。 次元で考えてみれば容易にわかるように，(#%("!(#&に対して ,(,# (""#"(##（# )(!(*" ，内積を用いて表せば） というのはベクトル (の長さである（図 を参照）。 ,(!),# %(" "!)"&#"%(#!)#&# というのはベクトル (!)の長さである（図 を参照）。 ノルムを 乗すると， ,(!),##! &#" #
%(&!)&&#
と - が外れて，計算し易くなる。 開 球：$'%(&#')$%#+"%(!)&!'(を (を 中 心 と す る 半 径 が 'の 開 球 （open ball）と言う。 次元の場合，$'%(&は開区間 %(!'!("'& 次元の場合，$'%(&は (を中心とし，半径が 'の円の内部（円周は含 まない）
図 + ( +" , 次元の場合，%)%+&は +を中心とし，半径が )の球の内部（表面は含 まない） である。
閉包：&を '!の部分集合とするとき，&を含む最小の閉集合を &の閉包 と言い，&と書く。 %)%+&と書くと 次元の場合円周まで含む円， 次元の場合表面まで含む 球を表すことになる。 直線：'!の 点 +，,に対して '%#!*&+"*,+*$'( を，+と ,を通る直線と言う。 直線はこのように通る 点がわかれば描けるが，通過点と法線ベクトル がわかれば描ける。 '+$'$+)(!+!+"*#"( は「+"を通り，(と直交する +の全体」（ただし (は ベクトルではない ものとする）という意味だから， 次元で描けば，+"を通り，(と直交す る直線である（図 を参照）。 平面，超平面： この後者の方法で平面，超平面を定義しよう。
&&%$#*(%!&!&")""' は「&"を通り，%と直交する &の全体（ただし %は ベクトルではないも のとする）」という意味だから， 次元で描けば，&"を通り，%と直交す る平面である（図 を参照）。 次元以上の場合は絵には描けないが， &&%$"*(%!&!&")""' を "次元ユークリッド空間における超平面（hyperplane）と言う。 (%!&!&")""は (%!&)"(%!&")"!と変形できるから，超平面は &&%$"*(%!&)"!' と表すこともできる。
&&%$"*(%!&!&")$"'，&&%$"*(%!&)$!'を 上 半 空 間（upper
half-space）と言い，H＋と表す。(%!&!&")$"ということは，%と &!&"のな
す角が鋭角ということであり，"次元空間を超平面で つに分けたときに %と &は同じ側にあるということであり，H＋とはそうした &の全体である。
&&%$"*(%!&!&")#"'，&&%$"*(%!&)#!'を 下 半 空 間（lower
half-space）と言い，H−と表す。(%!&!&")#"ということは，%と &!&"のな
す角が鈍角ということであり，"次元空間を超平面で つに分けたときに %と &は違う側にあるということであり，H−とはそうした &の全体である。 図 % & &" &+
図 凸集合 凸集合でない . - -. -. . -図 ( ' *" *! * 凸集合：)を +!の非空な部分集合とする。)に属する任意の 点を結 ぶ線分が完全に )に含まれているとき，つまり，任意の -!.#)に対し て$#!,%-",.#)，,#&"!#'が成り立っているとき，)は凸集合である と言う（図 を参照）。 分離定理（separation theorem）とは，+$で言えば， つの共通部分を持 たない凸集合 'と (を考えたとき，それらを両側にふり分ける直線が存 在するということである（図 を参照）。+%ならば 'と (を両側にふり 分ける平面，+&以上ならば 'と (を両側にふり分ける超平面が存在する ということである。
．補
題
まず，分離定理を証明するのに重要なステップとなる次の補題を証明しよう。補題 #$&!，#を !次元ユークリッド空間の非空，閉凸集合（閉集合 で凸集合）とする。このとき，任意の +%&!に対して次の命題が成り立つ。 ⑴ +''+(!++"%() '%#+'!++を満たす点 ''+(%#が存在する。 ⑵ 任意の '%#に対して )+!''+(!'!''+(*#" ⑶ ''+(は一意（unique）に定まる。 ⑴の証明 つの場合がある。まず，+%#ならば，''+("+である。+が #の中 に入っているなら，#との最短距離を与える点''+(は +自身である。こ れは自明。 もう つの場合，+&%# +は #に含まれないならば， +を中心に #と交わるように半径 *の球（ 次元で描くと円）を描く。# の中から 点 ',を取り出し，*"++!',+とすればよい。球（円）は閉包 図 # $ * ', +
をとって境界も含むものとしよう（&*',(）。 &*',(と %の共通部分を 'とする。 &*',(%%#' (+は %に入っているし，&*',(にも入っているのだから，'は空集合で はない。この 'の上で以下の関数を定義する。 )'((#)(!,) 今は ,を つ固定し，(を変数とする。この関数は 'の中からある点 (が 与えられると，(と ,の距離を与える関数である。 %はコンパクト集合（有界・閉集合），&*',(もコンパクト集合（有界・ 閉集合）だから，その共通部分の 'はコンパクト集合になる。 この)'((という関数は連続関数だから，Bolzano-Weierstrass の定理か ら，この関数を最小にする点(',(が存在する。 このことを示すのに %は閉集合という仮定は使っているが，まだ凸集 合という仮定は使っていない。⑴の主張だけを言うのだったら，%の凸性 は必要なく，%は閉集合でありさえすればいい。 ⑵の証明 %の中の点 (と (',(の中間の点を表すと，(',(と (!(',(の凸結合に なる。%は凸集合だから，この凸結合も %の中に入る。 (',("+'(!(',((&% +&'"!#* '"!+$#( (',(は ,との最短距離を与える %の点だったのだから，(',(と ,の距離 は (と(',(の中間の点と ,との距離よりも短い（図 を参照）。 ),!(',()$),!(',(!+'(!(',(() 乗しても不等号の向きは変わらない。 ),!(',()$$),!(',(!+'(!(',(()$ 右辺から左辺を引き，ベクトルの差のノルムの 乗は各座標の差の 乗の 和だったので，
*+!&&+'!*&&!&&+''*$!*+!&&+'*$%"
!
'## "
++'!&'&+'!*&&'!&'&+'',$!! '##
"
&+'!&'&+''$%"
!
'## "
+&+'!&'&+''$!$*&+'!&'&+''&&'!&'&+''"*$&&'!&'&+''$,
!!
'## "
&+'!&'&+''$%"
*$! '##
"
&&'!&'&+''$!$*! '##
"
+&+'!&'&+''&&'!&'&+'',%"
*$*&!&&+'*$!$*(+!&&+'!&!&&+')%" 両辺を*&!"'で割って **&!&&+'*$!$(+!&&+'!&!&&+')%" *を に近づけていくと，(') *- "の極限において !$(+!&&+'!&!&&+')%" (+!&&+'!&!&&+')$" これは，+!&&+'というベクトルと &!&&+'というベクトルが鈍角をな しているという意味である（図 を参照）。 （証了） 図 & &&+'"*&&!&&+'' % &&+' +
図 " % ⑶の証明は省略するが，"が凸集合でないと，"と %#""との最短距離 を与える点が複数存在してしまうことを図 のような例から理解して欲 しい。$$%%が一意に定まるために "の凸性は crucial な仮定なのである。
．分 離 定 理
分離定理は以下の つの形で表される。 ⑴ "を #!の閉凸集合とし，%!#""とする。このとき，先の補題で示し た %!との最短距離を与える "の点$$%!%を通り %!!$$%!%を法線ベク トルとする超平面は %!と "を分離する。 ⑵ "を #!の凸集合とし（必ずしも閉集合ではない），%!#""とする。こ 図 $ " 鈍角 $$%% %のとき )"を通り #をその半空間に含む超平面が存在する。 ⑶ #!$を &#の互いに共通部分を持たない凸集合（#$$""）とすれ ば，それらを分離する超平面が存在する。 ⑴の証明 補題より，)"と #との最短距離を与える点'')"(%#が一意（unique）に 決まる。 )"!'')"("(ととれば，)"&'')" "(なので，(は ベクトルではない。 この (を法線ベクトルする超平面 %"))%&#-+(!)!'')"(,""* を描けば，#は %の下半空間 H−に入っている。なぜかと言うと，すべて の '%#に対して +(!'!'')"(,"+)"!'')"(!'!'')"(,#" (の↑定義 補 ↑ 題⑵ だからである。一方，)"は +(!)"!'')"(,"+(!(,!" 図 ' # '')"( ( )" %
だから，$の上半空間 H＋に入っている。 こうして，超平面 $は +"と #をふり分ける，分離することができた （図 を参照）。 ⑵の証明 つの場合に分けられる。 +"$##，+"が #の閉包に入らない場合 #が凸集合なのだから，#の閉包も凸集合である。 だから，+"$##が与えられたとき， ,'%+"&!+","%() '##,'!+",
となる'%+"&##が一意に定まり，'%+"&を通って +"!'%+"&を法線ベクト
ル *とする超平面$"'+#&!+)*!+!'%+"&*""(が +"と#とを分離する ことはすでに⑴からわかっている。 この超平面を +"を含む位置まで平行移動した超平面 $-"'+#&!+)*!+!+"*""( は +"を通り，#を下半空間に含んでいる（図 を参照）。 図 # '%+"& +" #
1"%$!$の場合 1"は $には入っていないが，$の閉包には入っているというのは，1" は $の境界にあるということだから（1"%"$と記す），&$'&の点列(1,) を適当に選んで 1"に収束させることができる（&$'&，$の補集合とは (# から$を除いた部分のことである）。 1,./ 1" )0 ,./ $ 1"が $の境界にあるということは，1"を中心とするどんな大きさの開球 %/&1"'を描いても，$と &$'&と同 時 に 交 わ り を 持 つ。開 球%/&1"'と
&$'& の交わりから 点を取り出す。その開球の半径 /をだんだん小さく していき，開球と&$'&の交わりから 点を取り出すことをくり返してい けば，最終的にこれらの点から成る点列(1,)は 1"に収束する。 その点列(1,)の各点に対して，以下のように超平面を定義する。(1,) の各点は $の閉包に含まれていないから，⑴と同様の議論をくり返せば， (1,)の各点に対応して (.,)という法線ベクトルの点列が存在し，以下の ような超平面が存在する。 ',"(1%(#,*.,!1!1,+"") このように超平面を描くと，$は下半空間に含まれているから，$も下半 空間に含まれている。 *.,!)!1,+#" *-/)++)%$ 点列(1,)はもともと 1"に収束する点列であるから，十分に大きな ,を 選べば，どのように部分列を取っても，それは 1"に収束する。 法線ベクトルの点列(.,)は長さは問題ではないので，一般性を失うこ となく -.,-"# とできる。つまり，(.,)とは原点を中心とする半径が の球の表面上を 動く点列である。原点を中心とする半径が の球の表面はコンパクト集合 （有界・閉集合）だから，収束部分列を取ることができ，その極限も原点 を中心の半径が の球の表面上にあるようにできる。
'1-('/-(からこのように取った収束部分列 '1-,('/-,(に対しても， )/-,!(!1-,*#" +.0(,,(%# が成り立ち，'/-,(が収束する点を /"とすると，内積は連続関数だから， 極限においても )/"!(!1"*#" +.0(,,(%# が成り立つ。 そこで超平面を &"'1%'"+)/"!1!1"*""( とすれば，#を下半空間に含み，1"は超平面上にあることになる。 ⑶の証明 #$$"!なのだから， そのベクトル差の集合を %とすると（%"#!$），この集合は原点 を 含まない。なぜなら，もし，#と $に共通部分，交わりがあるとすれば， その交わっている点に対して，そのベクトル差は になり，%は原点を含 むことになってしまうはずだからである。 凸集合に−（マイナス）を付けてもやはり凸集合で， 凸集合と凸集合のベクトル和は凸集合だから，%"#!$は凸集合， そして，この %の中に原点 は含まれていない。 すると，原点 を通って，適当な超平面を描くと，その半空間に %を 含み，もう一方の半空間に原点 を含むようにすることができる。 具体的には，ある適当な "&/%'" "が存在して， )/!*!"*#" +.0(,,*%% とすることができる。 ここで超平面とは)/!1!"*""（原点 を通り，/に直行するような 1 の集合）である。 *というベクトルは *"(!)なのだから， )/!(!)*#" +.0(,,(%#!)%$
+0!',$+0!(, )/1',,'&#!(&$ +0!',の値は 'を #の中で様々に動かしても +0!(,で上から押さえられ ているから必ず有限な値になる。その上限を "とする。 "#230 '&#+0!', （#は必ずしも閉集合ではないから，この上限が #の中に入っている とは限らないため，-'4ではなく 230と書く） ここで超平面を %#)4&&#-+0!4,#"* と定義すると， +0!',$" )/1',,'&# つまり，#は %の下半空間 H−に入っていて， "$+0!(, )/1',,(&$ $は %の上半空間 H＋に入っている。 よって，この超平面は #と $を分離することができた。 （証了）
．ミンコフスキー・ファルカスの補題の証明
最 後 に，分 離 定 理 を 使 っ て，ミ ン コ フ ス キ ー・フ ァ ル カ ス の 補 題 （Minkowski-Farkas lemma）を証明しよう。 ミンコフスキー・ファルカスの補題（Minkowski-Farkas lemma） ##''*+(を -!.（-行 .列）の行列，(&&-（- 次元ベクトル）， 4&&. （.次元ベクトル），0&&.（.次元ベクトル）とする。 このとき次の つの命題のうち，いずれか一方のみが必ず成り立つ。 ⑴ #4#(が非負解 4"を持つ。 ⑵ #.0%"!+0!(,!"は解 0"を有する。 （#.は #の転置行列を表す。以下同様に .で転置を表す。）証明 ⑴と⑵が背反的であることを背理法で示そう。 ⑴を満たす解 +"，⑵を満たす解 *"が同時に存在したとしよう。つまり， ⑴から，%+#(を満たす +"$"が存在したとする。 ⑵から，%.*$"!,*!(-!"を満たす *"が存在したとする。 %+"#(の両辺に *"を転置して掛ける。 *".%+"#*".( 左辺について，*"%は行（ヨコ）ベクトル，%.*"は列（タテ）ベクトル という違いだけで，成分は同じで，⑵から %.*"$"なのだから *"%$"， それに非負ベクトル +"$"が掛かっているのだから， *"%+"$" 左辺は非負になる。 しかし，右辺は*"(#,*"!(-!"と負になってしまう。これは矛盾。 よって，⑴と⑵が同時に成立することはあり得ない。 ⑴か⑵のいずれか一方のみが必ず成り立つことを示すには，⑴が成り 立っていないときに，必ず⑵が成り立っていることを示せば十分である。 ⑴%+#(が非負解を持つということは，与えられた (が %の列ベクト ル*'#!'$!/!')+が生成する凸錐に入っているということである。左辺 の %+#+#'#!+$'$!/!+)')は %の列ベクトル*'#!'$!/!')+に非負の 係数(+#!+$!/!+))を掛けてつくった 次結合の全体，つまり凸多面錐 である。これを &としよう。 &#'*'#!'$!/!')+（'は凸多面錐の意味，凸多面錐とは凸錐の中 でも有限個のベクトルによって生成されたもののこと。凸多面錐 へり は縁を含んでいるので閉集合（証明は省略）） ⑴が成り立つとは (%&ということである（図 を参照）。⑴が成り立 たないとは (&%&ということである。
⑴が成り立たない，つまり，+%$'であるとき，分離定理⑶により，' と +を分離する超平面が存在する。 つまり，原点を始点とするベクトル 1!$)/が存在し，原点を通り 1!に 直交するように超平面を描けば（("'3$)/+)1!!3*""(）， )1!!*-*#" ,02*..-"#!$!,!/ （1!は &のすべての列ベクトルと鋭角をなし，つまり， 'は上半空間 H＋に含まれ） )1!!+*!" （1!は +とは鈍角をなす。つまり，+は下半空間 H−に含まれる） とすることができる。この 1!は⑵の解である（図 を参照）。 （証了） 図 '"&'*#!*$!*%( *# + *$ *%
参 考 文 献
Gale, D., The Theory of Linear Economic Models, New York, McGraw-Hill, Nikaido, H. Convex structures and Economic Theory, New York, Acdemic Press, 岡田章『経済学・経営学のための数学』（東洋経済新報社 年） 二階堂副包『現代経済学の数学的方法』（岩波書店 年） 丸山徹『経済数学講義』（慶応通信 年） 丸山徹『経済数学』（知泉書館 年） 金子太郎「企業買収と双対性」『香川法学』第 巻第 ・ 号 年 （かねこ・たろう 法学部教授） 図 %! %" '! %# & $
