凸集合（Convex Sets）
序
凸集合の基礎
凸多面錐
凸多面体
ヘリーの定理
参考書
[ 序 ]
凸性は数学のいろんなところに顔を出す基本的な概念である。
凸集合に関するいろんな話題をまとめることにしよう。
[ 凸集合の基礎 ]
以下では Rn は標準的な内積 ＜x,y＞ = xTy によるユークリッド空間とする。
２点 x， y の距離 d(x, y) はノルム により定まる標準的な距離 ‖x - y‖= ＜x - y, x - y＞ とする。
Rn の有限部分集合 M = {x1, x2, ... , xk} の１次結合 Σaixi は
無条件のとき 一般１次結合
Σai = 1 のとき アフィン結合
∀ai ≧ 0 のとき 非負（１次）結合
アフィンかつ非負な結合のとき 凸結合
とよぶ。
Rn の部分集合を 図形（figure）ともよぶ。
図形 S⊂Rn に対してこれらの４つのタイプの１次結合により
線形包（linear hull, linear closure） span S
アフィン包（affine hull, affine closure） aff S
凸錐包（convex conical hull） cc S
凸包（convex hull） co S
が定まる。 例えば aff S = { Σaixi| Σaixi は有限和， xi∈S, Σai = 1 }．
とくに
span S = S ⇔ 部分空間
aff S = S ⇔ アフィン集合
cc S = S ⇔ 凸錐
co S = S ⇔ 凸集合
である。 これらを図形 S の 結合的タイプ とよぶ。
ただし、図形 K は任意の α≧0 に対して αK ⊂ K のとき 錐（cone）とよばれる。
図形 S の 錐包（conical closure） cone S を cone S = { ax | x∈S， a≧0 } で定義すれば
cone S = S ⇔ S は錐
錐も含めて 図形 S の タイプ とよぶ。
特徴付けとしては、結合的タイプはいずれも２元の1次結合 a1x1 + a2x2 で閉じてればＯＫ．
定理 演算 ∩， +， スカラー乗法 に関して次が成り立つ。
（１） Si （i∈I） がタイプτ ⇒ 共通部分 ∩i∈I Si もタイプτ
（２） S1， S2 がタイプτ ⇒ １次結合 λS1 + μS2 もタイプτ
とくに、１点 a はアフィンかつ凸なので
S がアフィンまたは凸 ⇒ a による平行移動 a + S もそれぞれアフィンまたは凸
定理 S がタイプ τ ⇒ 線形写像 f：Rn → Rm による像および原像もタイプτ
次の定理は有名である。（たとえば [2] 参照）
定理 図形 S ⊂ Rn の 凸包 co S のどの点も S の n+1 個以下の点の凸結合
として表示することができる。（カラテオドリーの定理）
凸錐 K に対して
lin K = K ∩ (- K)
とおき、K の 線形性空間（linearity space）とよぶ。
定理 lin K は K に含まれる最大の部分空間である。
（∵） スカラー倍で閉じてることは容易。
x ，y ∈ lin K ⇒ x + y = 2((1/2)x + (1/2)y) ∈ lin K
最大でないとすると K の部分空間で lin K を真に含むのがありそのうちのひとつを W とする。
W - lin K の要素 x をとる。- x ∈ lin K だと x ∈ lin K となってしまうから - x ∈ K - lin K．
これは - x ∈ K と矛盾する。 //
図形 S ⊂ Rn にたいして
S* = { z∈Rn| ∀x∈S，＜z, x＞≦0 }
とおき、S の 極錐（polar cone）とよぶ。
定理 Rn の部分空間 L に対しては L* = L⊥ である。
定理 極錐は次の性質をもつ。
（@） かってな図形 S に対して S* は閉凸錐である。
（A） S1 ⊂ S2 ⇒ S1* ⊃ S2*
（B） S* = (cl co S)* （cl は閉包作用素）
定理 Rn の空でない錐 K1， K2 に対して、
( K1 + K2 )* = K1* ∩ K2* = ( K1∪ K2 )*
次の３つの定理は線形代数の定理の一般化である。
定理 K が空でない閉凸錐 ⇒ K** = K （双対定理）
＜証明＞ より一般に K を空でない錐として K** = cl co K を示せばよい。
K ⊂ K** は同語反復的に成立し、K** が閉凸錐であることから cl co K ⊂ K**．
次に逆の包含を示す。x ∈ Rn - cl co K とする。
点集合論の定理（「凸集合の分離定理」）から
∀z ∈ cl co K ， ＜z, p＞ ≦ 0 ， ＜x, p＞ ＞ 0
をみたすベクトル p が存在する。K* = (cl co K)* と ∀z ∈ cl co K ， ＜z, p＞ ≦ 0 から p ∈ K*
なので ＜x, p＞ ＞ 0 より x ∈ Rn - K**． //
定理 錐 K ⊂ Rn に対して、 dim span K + dim lin K* = n （次元定理）
定理 K がRn の空でない閉凸錐であれば、任意の x∈Rn に対して
x = y + z ， ＜y，z＞ = 0
となる y ∈ K， z ∈ K* が存在する。（直交分解定理）
＜証明＞ 点集合論の定理から
‖x - y‖ = min { ‖x - y'‖ | y' ∈ K }
をみたす y ∈ K が一意的に存在する。z = x - y とすると任意の x' ∈ K に対して ＜x' - y, z＞ ≦ 0．
x' = 0 とすると ＜y, z＞ ≧ 0 ， x' = 2y とすると ＜y, z＞ ≦ 0 ∴ ＜y, z＞ = 0．
よって、任意の x' ∈ K に対して ＜x' , z＞ ≦ 0 で z ∈ K*． //
[ 凸多面錐 ]
空でないアフィン集合 A はある部分空間 L を A の１点 a で平行移動した図形 a + L となっている。
この L は A に対して一意的で L = A - A である。L を A の 親空間 とよぶ。
＜注＞ 上記の A - A は { x - y| x, y ∈ A } の意味。このように記号を２重の意味で使うこともある。
そこで空でないアフィン集合 A の 次元 dim A は A に平行な部分空間 L の次元 dim L で定義する。
とくに Rn の n-1 次元アフィン集合を 超平面（hyperplane）とよぶ。
定理 Rn のゼロでないベクトル p と実数 γ に対して
H = { x| ＜p, x＞ = γ }
は超平面であり、逆にどんな超平面もこのように表示され p と γ は non 0 倍を除いて一意に定まる。
＜証明＞ [前半] H がアフィン集合であることは容易に示される。
＜p, (γ/＜p, p＞)p＞ = γ ゆえ H ≠ φ で H の元 a がとれる。H - a = p⊥ となるので H は超平面。
[後半] H を超平面とする。H に平行な n-1 次元部分空間の直交補空間はある non 0 ベクトル p
で張られる部分空間 span {p} である。x0 ∈ H をひとつ選び ＜p, x0＞ = γ とすると
H = x0 + p⊥ = { x0 + x| ＜p, x＞ = 0 } = { x| ＜p, x＞ = γ } となる。
もしも H = { x|＜p, x＞ = γ } = { x|＜q, x＞ = δ } であれば H の親空間 L は L = p⊥ = q⊥
となり p と q は non 0 倍だけの違いである。
また、 q = λp （ λ ≠ 0 ） とすると δ = ＜λp, x＞ = λγ となる。 //
超平面 H = { x| ＜p, x＞ = γ } が決める２つの領域
H+ = { x| ＜p, x＞ ≧ γ }
H- = { x| ＜p, x＞ ≦ γ }
を H が決める 閉半空間 とよぶ。閉半空間は凸錐である。
有限個の原点を通る超平面で定まる閉半空間 H-i = { x∈Rn| ＜ai, x＞≦0 } （ i=1, ... , m ）
の交わりとなる Rn の図形 K を 凸多面錐（convex polyhedral cone）とよぶ。
K = {a1, ... , am}* であるが ai⊥ （ i=1, ... , m ） を行ベクトルにした m×n 行列 A により
K = { x∈Rn| ＜ai, x＞≦0 （ i=1, ... , m ）} = { x∈Rn| Ax ≦ 0 }
とも表示できるので、凸多面錐は同次線形不等式の解集合になりうる集合といえる。
凸多面錐は閉凸錐で有限個の凸多面錐の共通部分も凸多面錐になることはすぐわかる。
有限個の n 次元ベクトル b1, ... , bm で生成される凸錐となる図形Γ⊂Rn
を 有限生成錐（finitely generated cone）とよぶ。
n×m 行列 B = [ b1, ... , bm ] を使えば
Γ = cc{b1, ... , bm} = { x∈Rn| x = By， y∈Rm， y ≧ 0 }
と表示できる。
定理（Weyl） 有限生成錐 ⇒ 凸多面錐
系 有限生成錐 K に対して、 K** = K
（∵） 有限生成錐 ⇒ 凸多面錐 ⇒ 閉凸錐 ゆえ。 //
定理 n×m 行列 B に対して { By| y ≧ 0, y ∈ Rm }* = { x ∈ Rn| BTx ≦ 0 }
系 m×n 行列 A に対して { x ∈ Rn| Ax ≦ 0 }* = { ATy| y ≧ 0, y ∈ Rm }
これらを使うと Weyl の定理の逆が導ける。
定理（Minkowski） 凸多面錐 ⇒ 有限生成錐
系 凸多面錐（resp. 有限生成錐）の極錐も凸多面錐（resp. 有限生成錐）
定理 K1， K2 が凸多面錐のとき、
（@） K1 ∩ K2 および K1 + K2 も凸多面錐
（A） ( K1 + K2 )* = K1* ∩ K2*
（B） ( K1 ∩ K2 )* = K1* + K2*
定理 凸多面錐の線形像および線形原像も凸多面錐。
（∵） 凸多面錐 K = { By| y≧0 } の線形写像 f(x) = Ax による像 f(K) は { ABy| y≧0 } で凸多面錐。
凸多面錐 K' = { x| Cx≦0 } の原像 f-1(K') は { z| Az∈K' } = { z| CAz≦0 } で凸多面錐。 //
[ 凸多面体 ]
有限個の閉半空間の交わりとなる図形を 凸多面体（convex polyhedral set, convex polyhedron）という。
Rn の凸多面体 D は適当な m×n 行列 A とm 次元ベクトル b により
D = { x ∈ Rn| Ax ≦ b }
と表される図形、つまり適当な非同次線形不等式の解集合である。凸多面体は凸集合である。
定理 m×n 行列 A と m 次元ベクトル b に対する非同次線形不等式
Ax ≦ b
が解を持つとき、かってな解は Ax≦0 のいくつかの解 u1, ... , up
および Ax≦b のいくつかの解 v1, ... , vq により
x = Σi=1p αiui + Σj=1q βjvj ， αi≧0， Σ αi = 1 ， βj≧0
で与えられる。
この定理により Minkowski の定理は凸多面体に次のように拡張される。
定理 Rn の凸多面体 D は、いくつかの点 u1, ... , up および v1, ... , vq によって、
D = { Σi=1p αiui + Σj=1q βjvj| αi≧0， Σ αi = 1 ， βj≧0 }
と表示される。すなわち、
D = co { u1, ... , up } + cc { v1, ... , vq } （ 凸多面体の 有限基底表示 ）
この定理の逆も成り立つ。（ Weyl の定理の凸多面体への拡張 ）
定理 Rn のいくつかの点 u1, ... , up および v1, ... , vq によって D⊂Rn が
D = co { u1, ... , up } + cc { v1, ... , vq }
となっているならば、D は凸多面体である。
定理
（１） 凸多面体の線形像および線形原像も凸多面体。
（２） D1，D2 がそれぞれ Rm，Rn における凸多面体 ⇒ D1×D2 は Rm + n における凸多面体。
系 D1，D2 が Rn における凸多面体 ⇒ D1 + D2 も Rn における凸多面体。
（∵） f：(x1, x2) ├→ x1 + x2 は線形。 //
有限個の点からなる図形の凸包 co{x0, x1, ... , xk} となる図形 D を ポリトープ（polytope）とよぶ。
また、x0, x1, ... , xk がアフィン独立、すなわち { x1 - x0, x2 - x0, ... , xk - x0 }
が１次独立であるとき D は k 次元単体 とよばれる。
一般に Rn の部分集合 S に対してはその 次元 dim S を
dim S = dim (aff S)
で定義する。 これは単体の次元の拡張となっている。
定理 Rn の凸集合Cに対して、 dim C = max { dim D| D は C に含まれる単体 }．
定理 有界な凸多面体 ⇔ ポリトープ
Rn の凸集合 C の空でない凸部分集合 E が C の 端集合（extreme set）
というのは次を満たすときとする：
x, y ∈ C で (x, y) ∩ E ≠ φ ならば x, y ∈ E
点 x は {x} が C の端集合であるとき C の 端点（extreme point）とよばれる。
定理 凸集合 C の端集合 E に対して、 (aff E) ∩ C = E． （逆はいえない）
x0 ∈ S ∈ Rn とする。ある p ∈ Rn に対して
∀x ∈ S ， ＜p, x - x0＞ ≦ 0
が成り立つとき、超平面 H = { x∈ Rn| ＜p, x - x0＞ = 0 } を x0 における S の
支持超平面 という。 閉凸図形 S のかってな境界点において S の支持超平面が存在する。
凸多面体 D とその支持超平面との共通部分を D の 面（face）という。
点 x に対して {x} が D の面であるとき、x を D の 頂点（vertex）という。
凸多面体においては、面は端集合で、いくつかの面の共通部分も端集合。頂点が端点。
[ ヘリーの定理 ]
定理（ラドンの定理） Rd 内のどんな d+2 個以上の点からなる集合 S にも
ある分割 S = A∪B が存在して co(A)∩co(B)≠φ．
＜証明＞ S = {x1, ... , xn} とする。
n - 1 ≧ d + 1 ゆえ ベクトル x1x2, ... , x1xn は１次従属で非自明な関係式
λ2(x1x2) + . . . + λn(x1xn) = 0
が成り立つ。λ1 = - (λ2 + ... + λn) とおけば
λ1 + λ2 + . . . + λn = 0
λ1x1 + λ2x2 + . . . + λnxn = 0
係数 λi には正のと負のとが必ずあるのでインデックスを付け替えて、
λ1, ... , λk ＞ 0 ，λk+1, ... , λn ≦ 0
と仮定できる。μj = - λj （ k+1≦j≦n ） とおくと、
λ1 + ... + λk = μk+1 + ... + μn （= α とする）
λ1x1 + . . . + λkxk = μk+1xk+1 + . . . + μnxn
最後の式の両辺をαで割ると、(x1, ... , xk の凸結合) = (xk+1, ... , xn の凸結合) のカタチの式をえる。
よって、A = { x1, ... , xk } ，B = { xk+1, ... , xn } とすれば co(A) ∩ co(B) ≠φ となる。 //
ラドンの定理から次のヘリーの定理を導くことができる。
定理（ヘリーの定理） Rd 上の n 個の凸集合 X1 ，. . . ，Xn において
どの d + 1 個の共通部分も空でないならば全部の共通部分も空ではない。
＜証明＞ n に関する帰納法で示す。n=1,2, ... , d+1 ならあきらか。
n = k （k≧d+1）で成り立つとして n = k+1 個の凸集合 X1 ，. . . ，Xk+1 に対しては
定理の仮定が満たされているとする。
帰納法の仮定から k 個の凸集合の交わりは空でないので
∃xj ，xj ∈ X1 ∩ ... ∩ Xj-1 ∩ Xj+1 ∩ ... ∩ Xk+1 （ 1 ≦ j ≦ k+1 ）
S = { x1, ... ,xk+1 } とおくと，k+1 ≧ d+2 なので、ラドンの定理により S の２分割 S = A∪B
で co(A)∩co(B)≠φ であるのが存在する。
インデックスを付け替えて A={ x1, ... ,xh } ，B = { xh+1, ... ,xk+1 } と仮定してよい。このとき
co(B) ⊂ X1 ∩ ... ∩ Xh
co(A) ⊂ xh+1 ∩ ... ∩ xk+1
よって、X1 ∩ ... ∩ Xk+1 ≠φ である。 //
例 Rd において四面体の４面はどの３個の交わりも空でない、が全部の交わりは空。
系 Rd の有限部分集合 X のどの d+1 点も半径 R の d 次元球体で
カバーできるならば、X も半径 R の d 次元球体でカバーすることができる。
（∵） 点 x を中心とする半径 R の d 次元球体を Bx とおく。
{ Bx| x∈X } に属するどの d+1 個の球体も必ず共通点を持つ。（∵ X の d+1 点は半径 R の
ある d 次元球体でカバーされるから、この球体の中心 y とすると、y からそれら d+1 点までの
距離はどれについても R 以下。よって、点 y はそれら d+1 点を中心とする半径 R の d 次元球体
たちの共通部分に入る。）
よって、ヘリーの定理により、∩x∈X Bx ≠φ で、∩x∈X Bx の点のひとつを p とすると、
どの x∈X に対しても p と x の距離は R 以下である。
したがって、X は p を中心とする半径 R の d 次元球体でカバーすることができる。 //
《 参考書 》
[1] 布川-中山-谷野 , 線形代数と凸解析 , コロナ社 , 1991
[2] Peter Frankl , 幾何学の散歩道 , 共立出版 , 1991
[3] 石田 正典 , トーリック多様体入門 , 朝倉書店 , 2000
[4] 日比 孝之 , 可換代数と組合せ論 , シュプリンガー東京 , 1995
← 数学ノートに戻る
