平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

劣モジュラ構造と離散凸性
悟∗

藤重

はじめに

1.

これから, グラフやネットワークなどの離散システムに現れる劣モジュラ構造について論じる. 劣モジュラ構造は, 劣モジュラ関数と呼ばれるある種の集合関数とそれに付随して定義される多面体によって表現され, 効率よく解くことができる多くの組合せ最適化に顔をのぞかせる. 本講義では, いくつかの具体例を通して劣モジュラ構
造の本質とその面白さを伝え, 「劣モジュラ関数の理論」と, 近年, 室田一雄によって展開されてきた「離散凸解析」への入門のお話をする.

2.

マトロイドから劣モジュラシステムへ

2.1.

マトロイド

劣モジュラ構造は, 集合族のもつ構造としては, マトロイドと呼ばれる離散構造として多くの組合せ最適化問題に現れる.
まず, マトロイドの定義から始めよう.
非空有限集合 E とその部分集合の族 I の対 (E, I) が次の条件 (I0), (I1), (I2) を満足するとき, 対 (E, I) をマトロイドという.

(I0) ∅ ∈ I.
(I1) I ⊆ J ∈ I =⇒ I ∈ I.
(I2) I1 , I2 ∈ I, |I1 | < |I2 | =⇒ ∃e ∈ I2 \ I1 : I1 ∪ {e} ∈ I.

∗

数理解析研究所

fujishig@kurims.kyoto-u.ac.jp1平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

ここで, 集合族 I を独立集合族といい, 各 I ∈ I を独立集合という. 以下に述べるよ
うに, マトロイドは他の形でも等価に定義することができるので, 上のように定義されたマトロイド (E, I) を, 独立集合族 I によって定義された E 上のマトロイド, ともいう.
マトロイドは, 英語で matroid (= matrix + oid) と書かれるように, 行列のようなものという元々の意味を有するもので, 行列の列ベクトルの組のもつ線形独立, 線形従属性で定まる組合せ的構造を抽象化したものとして, 1935 年に Hassler Whitney によって導入された概念である. (同時期に B.L. van der Waerden や 中澤 らによって等価な概念が考えられている. ）マトロイドの例 ————————————————————————————–

1. 行列的マトロイド
M を 任意の体 (たとえば有理数体) 上の m × n 行列とし, 行列 M の列番号の集合
を E = {1, 2, · · · , n} とおく. 以下では, 列番号 i を M の第 i 列ベクトルと同一視する. そこで, M の線形独立な列ベクトルの組 I ⊆ E の全体を I(⊆ 2E ) とすると, 対(E, I) は, 独立集合族 I によって定義された E 上のマトロイドである. このようにして得られるマトロイドを行列的マトロイドあるいは線形マトロイドといい, 行列 M
によって表現されるという. 位数 2 の有限体 GF(2) 上の行列で表現されるとき 2 値
マトロイドといい, 任意の体上に表現可能なとき正則マトロイドという.
2. グラフ的マトロイド
点集合 V , 枝集合 E をもつグラフ G = (V, E) を考える. 閉路を含まない枝集合
I ⊆ E の族を I とすると, 対 (E, I) は, 独立集合族 I によって定義された E 上のマ
トロイドである. このようなマトロイドをグラフ的マトロイドという. グラフ的マト
ロイドは行列的であって, グラフの接続行列によって表現される正則マトロイドである. 連結なグラフ G によって表現されるマトロイドの基は, G の全域木の枝集合であり, グラフの木に関連する様々な問題がそのマトロイド構造と関わっている.

———————————————————————————————————–
独立集合族 I によって定義された E 上のマトロイド (E, I) に対して, 集合の包含関係に関して極大な独立集合を基といい, 基の全体を B と表す. また, 独立集合でな
い E の部分集合を従属集合といい, 極小な従属集合をサーキットという. サーキットの全体を C と表す. 容易に分るように, 独立集合族 I, 基族 B, サーキット族 C は互いに他を一意的に定める.
マトロイドの基族 B は, つぎの公理系で特徴づけられる.

(B0) B 6= ∅.

2

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)(B1) B1 , B2 ∈ B, b1 ∈ B1 \ B2 =⇒ ∃b2 ∈ B2 \ B1 : (B1 \ {b1 }) ∪ {b2 } ∈ B.
また, サーキット族 C は, つぎの公理系で特徴づけられる.

(C0) ∅ ∈/ C.
(C1) C1 , C2 ∈ C, C1 ⊆ C2 =⇒ C1 = C2 .
(C2) C1 , C2 ∈ C, C1 6= C2 =⇒ ∀e ∈ C1 ∩ C2 , ∃C3 ∈ C : C3 ⊆ (C1 ∪ C2 ) \ {e}.
さらに, マトロイドの階数関数 ρ : 2E → Z+ が, つぎのように定義される. 各 X ⊆ Eに対して，
ρ(X) = max{|I| | I ⊆ X, I ∈ I}.
(2.1)
階数関数 ρ から独立集合族 I がI = {I | I ⊆ E, ρ(I) = |I|}(2.2)

のように与えられる. また, 階数関数 ρ : 2E → Z+ は, つぎの公理系で特徴づけられる.

(ρ0) ∀X ⊆ E : 0 ≤ ρ(X) ≤ |X|.
(ρ1) X ⊆ Y ⊆ E =⇒ ρ(X) ≤ ρ(Y ).
(ρ2) ∀X, Y ⊆ E : ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y ).
一般に, (ρ2) を満たす集合関数を劣モジュラ関数という.
マトロイドは, 基族 B ，サーキット族 C, 階数関数 ρ によってそれぞれ等価に定義されるので，対 (E, B), (E, C), (E, ρ) によってそれぞれマトロイドを定義することができる.
基族 B によって定義されたマトロイド M = (E, B) から, 基の補集合の族 B̄ ={E \ B | B ∈ B} を考えると, M∗ = (E, B̄) は基族 B̄ によって定義されたマトロイドとなる. この M∗ をマトロイド M の双対マトロイドという.
注意：グラフ的マトロイドの双対マトロイドは一般にグラフ的ではない (グラフ的であるのは平面グラフであるときに限る). この事実によって, マトロイド的なグラフの問題を真にマトロイド的に考える有効性が生まれるのである.

3

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

2.2.

ポリマトロイド

マトロイドは集合族のもつ組合せ構造を定めるのであるが, 集合を {0, 1}-値の特性ベクトルと対応させて考えると, マトロイド構造の一般化として, Jack Edmonds による, 非負ベクトルの集合の上のマトロイド的な組合せ構造の概念であるポリマト
ロイド [3] に導かれる.
階数関数の公理系 (ρ0)∼(ρ2) を一般化して, つぎのように, ポリマトロイドの階数関数 ρ : 2E → R の公理系 (ρ0)∼(ρ2) を考える.

(ρ0) ρ(∅) = 0.
(ρ1) X ⊆ Y ⊆ E =⇒ ρ(X) ≤ ρ(Y ).
(ρ2) ∀X, Y ⊆ E : ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y ).
対 (E, ρ) を階数関数 ρ によって定義される E 上のポリマトロイドという. ポリマト
ロイドの階数関数は, 非負単調非減少劣モジュラ関数である.
ポリマトロイド (E, ρ) に関連して, 以下のような多面体を定義する. (任意の X ⊆ E∑と x ∈ RE に対して, x(X) =x(e) と定義する. )e∈X

P(+) (ρ) = {x | x ∈ RE
+ , ∀X ⊆ E : x(X) ≤ ρ(X)},(2.3)

B(ρ) = {x | x ∈ P(+) (ρ), x(E) = ρ(E)}.

(2.4)

P(+) (ρ) を独立多面体, B(ρ) を基多面体と呼ぶ. 基多面体は, 独立多面体の元 (独立ベクトルという) でベクトルの成分毎の大小関係で定まる半順序に関して極大なものの全体であって, 独立多面体の一つの面をなす (図１).
ポリマトロイドの例 ——————————————————————————–
1. 線形ポリマトロイド
任意の体上の行列 M の列集合の分割を E = {F1 , F2 , · · · , Fn } とする. 各 X ⊆ E に対して, X に対応する列の全体からなる M の部分行列の階数を ρ(X) と書くことにする. このとき, (E, ρ) は, ρ : 2E → R+ を階数関数としてもつポリマトロイドであり, 線形ポリマトロイドと呼ばれる. 線形ポリマトロイドは部分空間の間の組合せ的従属関係の構造を表現する. １次元部分空間の間の組合せ構造が線形マトロイドである.

2. 多端子フロー
入口 s+ と複数個の出口 S − ⊆ V をもつ容量付きフローネットワーク N = (G =(V, A), c, s+ , S − ) を考える (G は点集合 V , 枝集合 A をもつグラフ, c : A → R+ は非4

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

x(3)
x(2)
B(f )
B(f )
P(f )

O
x(2)

O
x(1)
x(1)
(b)

(a)

図 1: ポリマトロイド.
負の枝容量関数). このネットワーク中の入口 s+ から出口 S − への実行可能フローとは,
0 ≤ ϕ(a) ≤ c(a)(a ∈ A),(2.5)∂ϕ(v) ≡∑∑

ϕ(a) −a∈δ + vϕ(a) = 0(v ∈ V \ ({s+ } ∪ S − ))(2.6)

a∈δ − vを満たす枝集合上の関数 ϕ : A → R である (ここで, δ + v (δ − v) は v に始点 (終点) をもつ枝の集合). ネットワーク N 中の実行可能フロー ϕ の, 出口 s− ∈ S − から流出す
るフローの流出量 −∂ϕ(s− ) で定まる S − 上のベクトルの全体は, S − 上のポリマトロ
イドの独立多面体をなす. 言い換えると, 各 X ⊆ S − に対して, N 中の s+ から X へ−の最大流量を ρ(X) と定めることによって ρ : 2S → R+ を階数関数とする S − 上のポリマトロイドが得られる.

3. エントロピー関数
E = {x1 , x2 , · · · , xn } を n 個の確率変数 x1 , x2 , · · · , xn の集合とする. ここで, 各確率変数は 1 から K までの有限個の値をとると仮定する. このとき, 各 X ⊆ E に対して, h(X) を Shannon の意味での X のエントロピーとして定義する. すなわち,
X = {xi1 , xi2 , · · · , xip } として,
h(X) = −K ∑K∑
k1 =1 k2 =1

···

K
∑

P (xi1 = k1 , xi2 = k2 , · · · , xip = kp )kp =1

× log2 P (xi1 = k1 , xi2 = k2 , · · · , xip = kp )

5

(2.7)

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)と定義する (ここで, P (·) は確率を表す). すると, (E, h) は h を階数関数とするポリマトロイドである. h はエントロピー関数と呼ばれ, E 中の確率変数間の従属関係を表現する. とくに, h の劣モジュラ性は, Shannon の情報理論では条件付き相互情報量の非負性として認識されている.

4. 凸ゲーム
E = {1, 2, · · · , n} を n 人のプレイヤーとし, 各 X ⊆ E が結託して達成できる非負な利得を v(X) と表す. v : 2E → R+ が，v(∅) = 0 で,
v(X) + v(Y ) ≤ v(X ∪ Y ) + v(X ∩ Y )(X, Y ⊆ E)

(2.8)

を満たすとする. このとき, (E, v) は凸ゲームと呼ばれ, この凸ゲームのコア（“合理的な” 配分の全体）が{x | x ∈ RE , ∀X ⊂ E : x(X) ≥ v(X), x(E) = v(E)}(2.9)

で与えられる.

ρ(X) = v(E) − v(E \ X)

(X ⊆ E)(2.10)

によって関数 ρ : 2E → R+ を定義すると, (E, ρ) は ρ を階数関数とするポリマトロイ
ドとなり, コアは, その基多面体 B(ρ) に一致する.

5. 置換多面体
E = {1, 2, · · · , n} とする. E の置換 σ : E → E によって RE 中の点 (σ(1), σ(2), · · · , σ(n))
が定まる. そのようなすべての置換に対して得られる RE 中の点集合の凸包を置換
多面体という (図２).
一般に, g(0) = 0 を満たす１変数の単調非減少な凹関数 g : R → R によって,
ρ(X) = g(|X|)(X ⊆ E)(2.11)と定義される ρ : 2E → R+ は, ポリマトロイドの階数関数である. とくに,g(k) =k∑(n − i + 1)

(k = 1, 2, · · · , n)(2.12)

i=1

が成り立つとき, 基多面体 B(ρ) は上述の置換多面体に一致する.

————————————————————————————————————

6

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

4123

1423
1243

4132

1432
4213
2413
2143

1342

4312

1234

1324
4321

4231
2134

2431
3412
3142
3124
2341
3421

2314
3241

3214

図 2: 置換多面体.

2.3.

劣モジュラシステム

ポリマトロイドの階数関数は非負単調非減少劣モジュラ関数であるが, 非負性と単調非減少性は組合せ的には重要でなく, 劣モジュラ性が本質的である. そこで, ポリ
マトロイドに代わる一般化概念として, 劣モジュラシステムが導入される ([4]).
いま, 集合演算 ∪, ∩ に関して閉じた E の部分集合族 D を考える. この集合族 D は,∪, ∩ を束演算として分配束をなす. さらに, 分配束 D 上の実数値関数 f が, 不等式系

f (X) + f (Y ) ≥ f (X ∪ Y ) + f (X ∩ Y )(X, Y ∈ D)

(2.13)

を満たすとする. f は分配束 D 上の劣モジュラ関数と呼ばれる. ここで, ∅, E ∈ D,
f (∅) = 0 であると仮定する. このとき, 対 (D, f ) を E 上の劣モジュラシステム, f を
その階数関数という. そして, 多面体

P(f ) = {x | x ∈ RE , ∀X ∈ D : x(X) ≤ f (X)}

(2.14)

を劣モジュラ多面体,

B(f ) = {x | x ∈ P(f ), x(E) = f (E)}を基多面体という.

7(2.15)

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)−g が劣モジュラ関数であるとき, g を優モジュラ関数という. 優モジュラ関数は,R の通常の順序 ≤ に双対な順序 ≤∗ (すなわち e ≤∗ e0 ⇔ e ≥ e0 ) に関する劣モジュラ関数であるから, 優モジュラ関数 g に対して, 優モジュラ多面体 P(g), 基多面体 B(g)を（双対な順序に関する劣モジュラ多面体, 基多面体として）同様に定義する.
E 上の劣モジュラシステム (D, f ) から
f # (E \ X) = f (E) − f (X)(X ∈ D)(2.16)

によって定義される D̄ = {E \ X | X ∈ D} 上の優モジュラ関数 f # を, f に双対な優モジュラ関数という. 容易に分るように,

B(f # ) = B(f )(2.17)

が成り立つ (図３).

         

図 3: 双対性.

e0 ∈ E を一つ決めて, 基多面体 B(f ) を軸 e0 に平行に, 超平面（１次元下がった空間）x(e0 ) = 0 上に射影して得られる多面体を一般化ポリマトロイドという (図４).
(一般化ポリマトロイドは András Frank によって導入された概念で, 上記のような基多面体との対応は後に明らかとなった ([4]).)
注意：ある定数 α ∈ R で決まる RE の超平面 x(E) = α に含まれる一般化ポリマト
ロイドが RE 中の基多面体であるということもできる. また, RE 中の一般化ポリマ

8平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

 

 
  
図 4: 基多面体と一般化ポリマトロイド.
トロイドを, 適当な α ∈ R に対する超平面 x(E) = α で切った切片が非空であると
き, その切片は基多面体である.
劣モジュラシステムの例 ————————————————————————–

1. カット関数
ポリマトロイド的でない階数関数の典型的な例として, ネットワークのカット関数がある. いま, 有向グラフ G = (V, A) 上に各枝の容量上下限を定める二つの関数 c̄ : A →R ∪ {+∞}, c : A → R ∪ {−∞} が与えられたネットワーク N = (G = (V, A), c̄, c)を考える. 任意の X ⊆ V に対して, X から出る (入る) 枝の集合を ∆+ (X) (∆− (X))
と表し,∑∑
κ(X) =c̄(a) −
c(a)(2.18)a∈∆− (X)a∈∆+ (X)

によって, 関数 κ : 2V → R ∪ {+∞} を定義する. D = {X | X ⊆ V, κ(X) < +∞}とおき, κ を改めて D 上の関数と考えると, (D, κ) は, V 上の劣モジュラシステムとなる. κ は, ネットワーク N のカット関数と呼ばれ, 一般に単調非減少関数ではない.
一方, 各枝 a ∈ A に対して c(a) ≤ ϕ(a) ≤ c̄(a) を満たす任意の関数 ϕ : A → R を N
中のフローという. N 中のすべてのフロー ϕ の境界 ∂ϕ : V → R の全体を ∂Φ と表すと,∂Φ = B(κ),(2.19)

9平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

すなわち, ∂Φ はカット関数で定まる劣モジュラシステムの基多面体に一致する.
ポリマトロイドの例として挙げた置換多面体や多端子フローの基多面体は, 適当
なカット関数で定まる基多面体を平行移動したものとして表現可能である.

———————————————————————————————————
つぎの定理は, 基多面体をその辺ベクトルで特徴づけるものである. (辺ベクトルとは, １次元面である辺の方向ベクトルであって, 正スカラー倍の違いを無視して同一視する. なお, X ⊆ E に対し, χX は X の特性ベクトル (すなわち, χX (e) = 1 (e ∈ X),
χX (e) = 0 (e ∈ E \ X)) であり, e ∈ E に対し, χ{e} を χe とも書く.)
定理 2.1 (冨澤 [13]): RE 中の凸多面体 P が基多面体であるための必要十分条件は, Pの辺ベクトルがχ e − χ e0(e, e0 ∈ E, e 6= e0 )(2.20)の形で与えられることである.
一般に, |E| = n のとき, 基多面体は, 端点数が n! に, 極大面 (ファセット) 数が 2n − 2に達する可能性があるが, 辺ベクトルの数は O(n2 ) と少ないのが特徴的である. 辺ベ
クトルの数が次元の多項式で抑えられる多面体を, 辺多項式な (edge-polynomial) 多面体という.
(2.20) が, いわゆる A 型のルート系であるのは興味深い. これは, 劣モジュラ構造の理論が, 数学 (表現論) の奥深い部分と関わりをもつことを示唆しており, ごく最近
そのような接点での研究の展開も見られる ([1, 2]).

3.

貪欲アルゴリズムと劣モジュラ関数

劣モジュラ構造を表現する劣モジュラ関数とそれに付随する劣モジュラ多面体, 基多面体の離散構造を詳細に見て行こう.
以下では, E 上の劣モジュラシステム (D, f ) について考える. 簡単のため, 分配束
D の極大鎖の長さは n = |E| に等しいと仮定する. このとき, つぎの事実が知られている.
定理 3.1 (G. Birkhoff): ∅, E ∈ D であって極大鎖の長さが n = |E| に等しい分配束D(⊆ 2E ) は, ある ( 一意的に定まる ) E 上の半順序集合のイデアルの全体に等しい.
ここで, E 上の半順序集合 P = (E, ¹) のイデアル I とは, I ⊆ E であって, 「e ¹e0 ∈ I =⇒ e ∈ I 」が成り立つもののことである. このように D を表現する半順序集10

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

合を P(D) と表すことにする.
注意：多くの組合せ最適問題が劣モジュラ関数最小化問題に帰着されるが, 劣モジュラ関数の最小化元の全体は分配束をなす。この分配束 D の極大鎖の長さが台集合のサイズより一般に小さいので, D に対応して D の最大元と最小元の差集合の分割とその上の半順序が定まる。このような半順序構造が実際的な問題において問題の解の構造に関する有用な情報を与える.

3.1.

最大基問題

つぎのような線形関数の最大化問題を考えよう.

Pw :

∑

Maximizew(e)x(e)

e∈E

(3.1)

subject to x ∈ B(f ).
∑ここで, w : E → R は与えられた E 上の重み関数で, e∈E w(e)x(e) を基 x の重みといい, 上述の問題は重み最大な基を見つける問題 (最大基問題という) である.
問題 Pw の双対問題は, つぎのように与えられる.

Pw∗ :Minimize∑

λX f (X)X∈D

subject to∑

λX χX = w,

(3.2)

X∈D

λX ≥ 0(X ∈ D \ {E}).

補題 3.2: 問題 Pw が最適解をもつための必要十分条件は, 重み w : E → R が半順序
集合 P(D) = (E, ¹) 上の単調非増加関数であることである.
重み w : E → R が半順序集合 P(D) = (E, ¹) 上の単調非増加関数であるとき,P(D) の単調増加なイデアルの系列

Ŝ : ∅ = Ŝ0 ⊂ Ŝ1 ⊂ · · · ⊂ Ŝk = E(3.3)と正係数 λŜi (i = 1, 2, · · · k − 1) と符号制約のない係数 λŜk が一意的に存在して,

w=

k
∑

λŜi χŜi

(3.4)

i=1

と表現される. 実際, w(e) (e ∈ E) の相異なる値が w1 > w2 > · · · > wk で与えられる
とき,
Ŝi = {e | e ∈ E, w(e) ≥ wi }(i = 1, 2, · · · , k)
(3.5)

11

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)(Ŝ0 = ∅) とおくことによって, 上記の単調増加なイデアルの系列が得られ,
λŜi = wi − wi+1

(i = 1, 2, · · · , k − 1),

λŜk = wk

(3.6)
(3.7)

によって定まる λŜi (i = 1, 2, · · · , k) によって, 式 (3.4) が成立する (議論に現れない他の双対変数 χX はその値を 0 とおく). (これらが双対問題 Pw∗ の実行可能解であるから, 以上で, LP の双対定理より, 補題 3.2 の十分性の証明を与えたことになる. 必要性
は, 双対問題 Pw∗ が実行可能解をもてば w が P(D) 上の単調非増加関数であることか
ら示される. ）(3.3) のイデアルの系列 Ŝ を含む D の極大鎖

S : ∅ = S0 ⊂ S1 ⊂ · · · ⊂ Sn = E(3.8)

を任意に一つ選ぶ. この極大鎖から, Si \ Si−1 = {ei } (i = 1, 2, . . . , n) によって定まる E の順列 (e1 , e2 , · · · , en ) に対し,w(e1 ) ≥ w(e2 ) ≥ · · · ≥ w(en )(3.9)

が成り立つ. そこで,

x(ei ) = f (Si ) − f (Si−1 )(i = 1, 2, · · · , n)(3.10)と定義する. (主問題の x を求めるには, (3.9) を満たすような P(D) の線形拡大 (E の順列) を決めて, (3.8) を求めてもよい.)
補題 3.3: 式 (3.10) によって与えられる x は基多面体 B(f ) の元である.
この基 x に対する主問題 Pw の目的関数の値は,∑

w(e)x(e) =k∑wi (f (Ŝi ) − f (Ŝi−1 ))

i=1

e∈E

=
=

k−1
∑
i=1
k
∑

(wi − wi+1 )f (Ŝi ) + wk f (E)λŜi f (Ŝi )(3.11)

i=1と書き換えられ, 双対実行可能解 λŜi (i = 1, 2, · · · , k) に対する双対問題 Pw∗ の目的関数の値と一致する. よって, これらの主, 双対問題の実行可能解は, それぞれ, 主, 双対問題の最適解である.

12

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

以上を整理すると, χSi を第 i 行 (i = 1, 2, · · · , n) にもつ n × n 行列を用いて, 主問
題の最適解は,

un

un−1

un−2

···

u1

1

 0


 0

 ..
 .

0

1
1
0
..
.
0

1
1
1
..
.
0

···
···
···
..
.
···

f (Sn )1 f (Sn−1 ) 
1


 ∗
 f (S1n−2 ) 
b =


.. 
..


. 
.



1
f (S1 )









を右下から後退代入によって解くことにより求められる. その解の陽な表現が式 (3.10)である. この解の求め方を貪欲アルゴリズム (greedy algorithm (Edmonds による命名))という.
一方, 双対問題 Pw∗ の最適解の λSi (i = 1, 2, · · · , n) の値は, 上の同じ行列を用いて,

un

un−1

un−2

···

u1

1

 0


∗ 
λ  0
 ..
 .

0

1
1
0
..
.
0

1
1
1
..
.
0

···
···
···
...
···

1

1


1
=w
.. 
. 

1





を左上から後退代入によって解くことにより求められる (ただし, λ∗ = (λSi | i =1, 2, · · · , n), w は n 次元横ベクトルとして考える). 双対最適解のこのような求め方を双対貪欲アルゴリズムという.
劣モジュラ構造よりさらに一般の離散構造上の双対貪欲アルゴリズムの研究が最近展開されている (たとえば [7] 参照).

3.2.

Lovász 拡大

以下では, 話を簡単にするため, D = 2E であると仮定する.
任意の重みベクトル w ∈ [0, 1]E に対して, 式 (3.4) によって w を表現する E の部分
集合列 (3.3) が一意に決まる. そこで, 任意の集合関数 f : 2E → R に対して,

fˆ(w) =k∑

λŜi f (Ŝi )(3.12)

i=1と定義することによって, f の [0, 1]E 上への区分線形な拡大が定まる (これを Lovász
拡大という).

13

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

定理 3.4 (Lovász [8]): 集合関数 f : 2E → R に対して, f が劣モジュラ関数であるための必要十分条件は, f の Lovász 拡大 fˆ が凸関数であることである.
注意：単位超立方体 [0, 1]E は, ブール束 2E の極大鎖 (3.8) によって定まる単体 σS ={χSi | i = 1, 2, · · · , n}（の凸包）の全体によって単体分割される. この単体分割による集合関数 f の拡大が, fˆ である. 与えられた空間の単体分割とその上の凸関数という枠組みが, 離散的な凸関数を考えるとき, 基本的かつ重要である (図５).

 

 

 

 

  



 





  

図 5: Lovász 拡大.

4.

凸解析の基礎「離散凸解析」の話に入る前に, Fenchel や Rockafellar によって展開された連続な,
いわゆる凸関数に対する「凸解析」の基礎の話をしよう (詳細は [11], [6] を参照).

4.1.

凸共役関数

凸関数 f : RE → R ∪ {+∞} が与えられているとする (f (x), f (y) < +∞ である
任意の２点 x, y ∈ RE と 0 ≤ α ≤ 1 を満たす任意の α に対して, f (αx + (1 − α)y) ≤αf (x) + (1 − α)f (y) が成り立つとき, f を凸関数という). f (x) が有限値であるよう

14平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

な点 x の全体を f の有効定義域といい, domf と書く. 以下で考えるすべての凸関数
は非空な有効定義域をもつと仮定する.
f のエピグラフ epi(f ) は,epi(f ) = {(x, α) | x ∈ domf, α ≥ f (x)}(4.1)

と定義される.
また, 凸関数 f の凸共役関数 f • : (RE )∗ → R ∪ {+∞} が, つぎのように定義される.

f • (p) = sup{hp, xi − f (x) | x ∈ RE }(p ∈ (RE )∗ ).

(4.2)

∑

ここで, hp, xi = e∈E p(e)x(e) である. 式 (4.2) による f から f • への変換は,Legendre 変換あるいは Fenchel-Legendre 変換と呼ばれる.

———————————————————————————————————–
例１： つぎのような最も簡単な凸関数を考えよう. x0 ∈ RE は与えられた点であり, f はその点でのみ有限な値をとる関数である.
 αf (x) = 0+∞x = x0 のとき
その他のとき.

(4.3)

この f の凸共役関数 f • は,f • (p) = hp, x0 i − α0(p ∈ (RE )∗ )(4.4)

の形のアフィン関数となる.
例２： f が多面体的な凸関数で, その有効定義域が有界な場合を考えよう. そのエ
ピグラフのすべての端点が, (xi , αi ) (i = 1, 2, · · · , n) で与えられるとき, f の凸共役関
数 f • は,f • (p) = max{hp, xi i − αi | i = 1, 2, · · · , n}(p ∈ (RE )∗ )(4.5)

のように n 個のアフィン関数の各点 p ∈ RE ) における最大値の形で与えられる多面
体的な凸関数である.

———————————————————————————————————–
適当な p ∈ (RE )∗ に対して,

argmin{f (x) − hp, xi | x ∈ RE }

15

(4.6)

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

が非空であるとき, この集合を f の線形定義域という (ここで, argmin{·} は括弧内の関数の最小化元の全体を表す). また, 与えられた x ∈ RE に対して∀y ∈ RE : f (x) + hp, y − xi ≤ f (y)(4.7)

が成り立つような p ∈ (RE )∗ は, 点 x における劣勾配と呼ばれる. 点 x における劣勾配の全体を劣微分といい, ∂f (x) と表す. 点 x における劣微分は,∂f (x) = argmin{f • (p) − hp, xi | p ∈ (RE )∗ }(4.8)

に等しく, f の凸共役関数 f • の一つの線形定義域をなす.
注意：劣モジュラ関数 f : 2E → R の Lovász 拡大 fˆ の線形定義域は, ブール束 2E のいくつかの極大鎖で定まる単体の合併で与えられる. さらに, 原点 O における fˆ の劣
微分が劣モジュラ多面体 P(f ) であり, 点 1(= χE ) における劣微分が双対な優モジュラ多面体 P(f # ) であり, 点 α1 (0 < α < 1) における劣微分は基多面体 B(f ) である.

なお, 凹関数 g の凹共役関数（双対順序に関する g の凸共役関数）を g ◦ と表し, 点x における優微分（双対順序に関する劣微分）を ∂g(x) と表す.

4.2.

Fenchel 双対定理

凸関数と凹関数の二つの関数に関する Fenchel 双対定理と呼ばれる, 凸解析において中心的な役割を果たすつぎの定理がある.
定理 4.1: 凸関数 f : RE → R ∪ {+∞} と凹関数 g : RE → R ∪ {−∞} が与えられ,domf ∩ domg 6= ∅ が成り立つと仮定する. このとき,

inf{f (x) − g(x) | x ∈ RE } = sup{g ◦ (p) − f • (p) | p ∈ (RE )∗ }(4.9)

が成り立つ. 左辺の値が −∞ に等しいとき, domg ◦ ∩ domf • = ∅ である.

f が多面体的凸関数で g が多面体的凹関数であって, 上式の左辺が（したがって右辺も）有限値をとるとき, その値を達成する左辺の最小化元を x̂, 右辺の最大化元をp̂ とすると,p̂ ∈ ∂f (x̂) ∩ ∂g(x̂),
x̂ ∈ ∂f • (p̂) ∩ ∂g ◦ (p̂),(4.10)f (x̂) − g(x̂) = g ◦ (p̂) − f • (p̂)
が成り立つ.

16(4.11)

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

5.

劣モジュラ関数から L\ 凸関数へ

集合関数としての劣モジュラ関数の自然な拡張としての離散的な凸関数として L\
凸関数がある.

5.1.

劣モジュラ関数

劣モジュラ関数 f : 2E → R は, 3.2 節で述べたように, その Lovász 拡大が凸関数であることと特徴付けられる. Lovász 拡大は, ブール束 2E の極大鎖（あるいは E の順列）に対応する単体による, 単位超立方体 [0, 1]E の単体分割によって定まる凸関数である. このような見方に立つと, 整数格子点 ZE 上の離散凸関数である L\ 凸関数
は自然に理解される.

5.2.

L\ 凸関数RE のすべての整数点 z とブール束 2E のすべての極大鎖 S : S0 (= ∅) ⊂ S1 ⊂ · · · ⊂Sn (= E) に対応する単体 σS = {z + χSi | i = 0, 1, · · · , n} からなる RE の単体分割を考える. この単体分割は Freudenthal 単体分割と呼ばれる (図６). 整数格子点上の関

x(2)

z

x(1)

O

図 6: R{1,2} の Freudenthal 単体分割.

17

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

数 f : ZE → R ∪ {+∞} の, Freudenthal 単体分割によって定まる RE 上の区分線形関数を f の Lovász-Freudenthal 拡大と呼び, fˆ と表す. fˆ が RE 上の凸関数となるような整数格子点上の関数 f : ZE → R ∪ {+∞} を L\ 凸関数という.

6.

基多面体 / 一般化ポリマトロイドから M / M\ 凸関数へ

関数 f : RE → R ∪ {+∞} は, そのすべての極大な線形定義域が有効定義域と同じ次元をもつ基多面体であるとき M 凸関数といい, そのすべての線形定義域が有効定義域と同じ次元をもつ一般化ポリマトロイドであるとき M\ 凸関数という (図７).
定義によって, M 凸関数は M\ 凸関数であるが, M\ 凸関数は, 定義域の空間の次元を一つ上げることによって, M 凸関数と同一視できる（一般化ポリマトロイドと１次元上がった空間の基多面体との対応に注意 (2.3 節)).
M\ 凸関数 f のすべての線形定義域が整数一般化ポリマトロイドであるとき, f は,それを整数格子点上に制限して得られる関数 fZ の凸拡大として一意的に定まる. そ
こで, そのような整数格子点上の関数も M\ 凸関数と呼ぶ (後者が元々の定義の M\ 凸関数である [9, 10]).

   
図 7: M\ 凹関数 g [4, Figure 17.4].

18

平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

7.

離散 Fenchel 双対定理

整数格子点上の整数値 L\ 凸関数 f : ZE → Z∪{+∞} は, その Lovász-Freudenthal 拡
大 fˆ : RE → R∪{+∞} と同一視され, その凸共役関数 fˆ• : (RE )∗ → R∪{+∞} と１対１に対応する. このとき, fˆ• のすべての線形定義域は整数一般化ポリマトロイドであって, fˆ• は, それを整数格子点上に制限して得られる M\ 凸関数 fˆZ• : ZE → Z∪{+∞}と同一視できる. この fˆZ• を整数値 L\ 凸関数 f の凸共役関数と呼び, f • と表すことにする. 以上の関係はつぎのようにまとめられる.
凸共役
凸拡大
制限
−→
−→ f ••
ˆˆff ←→ f
←−
←−
制限
凸拡大

(7.1)

ここで, f • が整数値関数であることは少し説明が必要であるが, 省略する.
(7.1) の両端を直接結ぶ離散版の凸共役対応がつぎのように与えられる.
定理 7.1 (室田 [9, 10]): 各整数点 p ∈ (ZE )∗ に対して,f • (p) = inf{hp, xi − f (x) | x ∈ ZE }(7.2)

が成り立つ. 逆に, 各整数点 x ∈ ZE に対して,

f (x) = inf{hp, xi − f • (p) | p ∈ (ZE )∗ }(7.3)

が成り立つ.
さらに, この離散版の凸共役対応に関して, つぎのような離散 Fenchel 双対定理が得られる.
定理 7.2 (離散 Fenchel 双対定理 (室田) [9, 10]): L\ 凸関数 f : ZE → Z ∪ {+∞} と L\
凹関数 g : ZE → Z ∪ {−∞} が domf ∩ domg 6= ∅ を満たすとする. このとき,

inf{f (x) − g(x) | x ∈ ZE } = sup{g ◦ (p) − f • (p) | p ∈ (ZE )∗ }(7.4)

が成り立つ.
この離散 Fenchel 双対定理を理解するには, 劣モジュラ構造の理論において組合せ
的により深い構造に踏み込んだ, 交わり定理 (intersection theorem) [3, 4, 9, 10] の話をしなければならない.

19平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)

8.

おわりに

劣モジュラ構造についてマトロイドから話を始めて, ポリマトロイド, 劣モジュラ
システムから, 室田による「離散凸解析」の入門までを駆け足で説明したが, より詳
しくは, 参考文献の [9, 10] あるいは近刊の拙著 [4] の第２版の VII 章を参照されたい.
また, より入門的には, 拙著 [5] において, 劣モジュラ構造の観点からグラフ・ネッ
トワークに関連する組合せ最適化問題が扱われているので参考にされるとよいであろう. さらに, 離散凸解析と数理経済学との接点に関する最近の展開について, 田村がサーベイ論文 [12] で詳しく論じている.
なお, 離散凸性に関して, より広い観点からの研究が V. I. Danilov と G. A. Koshevoy
によってなされている [1, 2].

参考文献[1] V. I. Danilov and G. A. Koshevoy: Discrete convexity and unimodularity—I. Advances in Mathematics 189 (2004) 301–324.
[2] V. I. Danilov and G. A. Koshevoy: Discrete convexity and Hermitian matrices (inRussian). Proc. V.A. Steklov Inst. Math. 241 (2003) 68–90.
[3] J. Edmonds: Submodular functions, matroids, and certain polyhedra. Proceedings of
the Calgary International Conference on Combinatorial Structures and Their Applications (R. Guy, H. Hanani, N. Sauer and J. Schönheim, eds., Gordon and Breach,
New York, 1970), pp. 69–87; also in: Combinatorial Optimization—Eureka, You
Shrink! (M. Jünger, G. Reinelt and G. Rinaldi, eds., Lecture Notes in Computer
Science 2570, Springer, Berlin, 2003), pp. 11–26.
[4] S. Fujishige: Submodular Functions and Optimization (Annals of Discrete Mathematics, Vol. 47) (North-Holland, 1991); also, the second edition (ibid. Vol. 58)(2005) (近刊).
[5] 藤重 悟：「グラフ・ネットワーク・組合せ論」, 共立出版, 2002.
[6] 福島 雅夫：「非線形最適化の基礎」, 朝倉書店, 2001.
[7] H. Hirai: Greedy fans: a geometric approach to dual greedy algorithms. Proceedings of the 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its
Applications (Budapest, June 3–6, 2005), pp. 99–105.

20平成17年度(第27回)数学入門公開講座テキスト(京都大学数理解析研究所，平成17年8月1日～8月4日開催)[8] L. Lovász: Submodular functions and convexity. In: Mathematical Programming—
The State of the Art (A. Bachem, M. Grötschel and B. Korte, eds., Springer, Berlin,1983), pp. 235–257.
[9] 室田 一雄：「離散凸解析」, 共立出版, 2001.
[10] K. Murota: Discrete Convex Analysis (SIAM Monographs on Discrete Mathematics
and Applications 10, SIAM, 2003).
[11] R. T. Rockafellar: Convex Analysis (Princeton University Press, Princeton, N.J.,
1970).
[12] A. Tamura: Applications of discrete convex analysis to mathematical economics.
Publications of the Research Institute for Mathematical Sciences, Kyoto University
40 (2004) 1015–1037.
[13] 冨澤信明：超空間論 (XVI)—ヘドロンの構造について. 電子通信学会「回路とシステム研究会」研究技報 CAS82-174 (1983) 21–26-3.

21