PDFをダウンロード

『公共経済学講義：理論から政策へ』
数学付録：凸集合と分離定理1
須賀晃一［編］
c
⃝Koichi
Suga, 2014
発行所：有斐閣
2014 年 6 月 25 日初版第 1 刷発行
ISBN 978-4-641-16445-1
1
須賀晃一（編）『公共経済学講義：理論から政策へ』（有斐閣，2014 年）の【数学付録】を項目別に公開
しています。本書を読み進めて頂くに際してのご参考に，ぜひご利用下さい。
1
凸集合と分離定理
1
凸集合
経済学では，Rn の部分集合の中で凸集合と呼ばれる集合が，特に重要な役割を果たす．
Rn の任意の 2 点 x, y を端点とする線分は
{αx + (1 − α)y|α ∈ R, 0 ≤ α ≤ 1}
によって定義される．閉区間と同様に [x, y] で表す．
Rn の部分集合 A は，任意の x, y ∈ A に対して，x と y を端点とする線分がもとの A に
含まれるとき，すなわち
x, y ∈ A =⇒ [x, y] ⊂ A
ならば凸集合と呼ばれる．
αx + (1 − α)y は x と y の凸結合といわれ，２点 x，y の (1 − α) : α の内分点を表す (図 1
を参照せよ)．凸集合とは，その集合に属する任意の２点の凸結合が，再びもとの集合に属
するという性質をもった集合である．1 次元の場合，区間は凸集合である．２次元では，線
分，円や三角形の内部は凸集合である．だが凸の形をした集合は凸集合ではない (図 2 を参
照せよ)．上で述べた近傍は凸集合になっている．
x
αx + (1 − α)y
αx
y
(1 − α)y
図 1: 凸結合
任意個の凸集合 Aλ (λ ∈ Λ) が与えられたとき，それらの共通部分 ∩λ∈Λ Aλ は凸集合であ
るが，和集合 ∪λ∈Λ Aλ は一般に凸集合ではない．
Rn の部分集合 A が与えられたとき A が凸でないなら，最小限の点を加えて凸集合にす
る．次のような手続きを考えよう．与えられた集合を含むあらゆる凸集合 Aλ (λ ∈ Λ) を集
め，凸包と呼び，Cv[A] で表す．すなわち
Cv[A] = ∩λ∈Λ Aλ
2
y
x
αx + (1 − α)y
x
αx + (1 − α)y
αx + (1 − α)y
y
x
y
(a)
(b)
(c)
図 2: 凸集合
図 3: 凸包
3
である．
凸集合の別の例として，凸錐 (convex cone) と超平面 (hyperplane) を取り上げる．まず，
錐の定義を与える．Rn の任意の x に対して，{αx|α ∈ R+ } によって定義される集合を x
によって定まる射線 (ray) という．n = 2 のとき，射線は原点から引かれた x を通る半直線
になる．Rn の部分集合 A が，任意の x ∈ A に対して，x によって定まる射線がもとの A に
含まれるとき，A は錐 (cone) という．
Rn の部分集合 A は
α, β ∈ R+ , x, y ∈ A =⇒ αx ＋βy ∈ A
が成り立つとき，凸錐という．
2 つの集合 A, B ⊂ Rn に対して，
A + B = {x + y|x ∈ A, y ∈ A}
と定義する．
A，B が凸集合ならば A + B も凸集合である．
次に，a = (a1 , a2 , . . . ，an ) ∈ Rn , a ̸= 0 および B ∈ R に対して，
H = {x = (x1 , x2 , . . . ，xn ) ∈ R |a · x =
n
n
∑
ai xi = b}
i=1
を定義し，Rn 内の超平面と呼ぶ．そして，a = (a1 , a2 , . . . ，an ) を H の法線ベクトルとい
う．1 つの超平面 H は，Rn を 2 つの半空間 (half-space)
H+ = {x = (x1 , x2 , . . . ，xn ) ∈ Rn |a · x ≥ b}
H− = {x = (x1 , x2 , . . . ，xn ) ∈ Rn |a · x ≤ b}
に分け，H は H+ と H− の共通部分となる．図 4 は (a1 , a2 ) = (−1, 1)，b = 2 のケースを図
示したものである．超平面は −x1 + x2 = 2 で表される直線である．n = 2 の時平面内の直
線，n = 3 のとき空間内の平面となる．法線ベクトルは H と直交するベクトルである．図 4
より明らかなように，H+ , H− は凸集合であり，H = H+ ∩ H− も凸集合である．
もう 1 つ注意しておくべき点は，超平面が同じでも法線ベクトルの方向によって H+ と
H− が入れ替わることである．上の図 4 の例と同様で，(a1 , a2 ) = (1, −1), b = −2 としてみ
よう．これから同一の直線（超平面) の式が導かれるが，H+ と H− の位置は図とは逆にな
る．例えばそれらの式に原点を代入してみれば容易に確認できよう．つまり，超平面を挟ん
で法線ベクトル側（法線ベクトルが指し示す方向にある半空間) が H+ であり，逆側が H−
なのである．
∑
さて，2 つの非空集合 A, B ⊂ Rn に対して,1 つの超平面 H = {x|a · x = ni=1 ai xi = b}
が存在して，
x ∈ A =⇒ a · x ≥ b
x ∈ B =⇒ a · x ≤ b
が成り立つとき，超平面 H は A, B を分離するという．図 5 を見よ．
4
x2
(-1,1)
−x1 + x2 = 2
H+
2
H−
x1
-2
図 4: 超平面
図 5: 分離超平面
補助定理 1 集合 A ⊂ Rn は非空閉凸集合で原点を含まないとする．このとき超平面 H =
{x|a · x = b} が存在し，任意の x ∈ A に対して a · x > b が成り立つ．
補助定理 2 集合 A ⊂ Rn は非空凸集合で原点を含まないとする．このとき原点を通る超平
面 H = {x|a · x = 0} が存在して，任意の x ∈ A に対して a · x ≥ 0 が成り立つ．
これら 2 つの補助定理を用いて，分離定理が証明できる．
定理 1 （分離定理 I）
2 つの集合 A, B ⊂ Rn は非空凸集合であるとする．このとき，A ∩ B = ∅ ならば，これ
らを分離する超平面が存在する．
定理 2 （分離定理 II）
集合 A ⊂ Rn は非空凸集合であり，A ∩ Rn++ ̸= ϕ とする．このとき A と Rn+ を分離する
超平面が存在し，その法線ベクトル a ̸= 0 は
∀x ∈ A : a · x ≤ 0 かつa ≥ 0
を満たす．
5

Download Report