日本数学会 2004 年度年会，企画特別招待講演，筑波大学，2004-03-28/31, pp. 99–109.

離散凸解析への誘い
東京大学大学院 情報理工学系研究科

室田 一雄「離散凸解析」は，「組合せ構造を兼ね備えた凸関数」あるいは「凸集合と類似した離散構造」を数学的に研究することによって離散最適化の世界に新しい枠組み与えようとする試みである. 理論展開の大枠は通常の凸解析に倣い, 数学的側面はネットワーク・マトロイド理論を拡張するので，標語的には,離散凸解析 = 凸解析 ＋ マトロイド理論となる. M 凸関数，L 凸関数の概念，両者の共役関係および離散双対性がその骨格であり，種々の問題に対してアルゴリズムが開発されている．離散最適化の他にも，オペレーションズ・リサーチ，システム解析，数理経済学，ゲーム理論などへの応用がある．

1

凸解析と最適化

非線形計画問題は通常「Minimize f (x) subject to x ∈ D」の形に書かれるが，これは, 目的関数 f : Rn → R を実行可能領域 D ⊆ Rn の上で最小化する問題である．とくに, D が凸集合, f が凸関数のときは凸計画問題と呼ばれ, 理論的にも実際的にも扱い易い対象である.
凸関数の性質のうち, 最適化の立場から最も基本的なものを挙げるとすれば次の二つであろう.

1. 局所最適条件が大域的最適性を特徴づける. したがって, 降下法に基づく算法によって最適化が達成される.
2. 凸関数と凹関数の間に分離定理や Fenchel 双対定理のような双対性が成り立
つ. これから Lagrange 双対理論が導かれ, 双対変数を用いた算法などが構成される. 線形計画法における双対性もこの特殊ケースと見なせる.
双対性について具体的に述べよう. f : Rn → R ∪ {+∞} を凸関数, h : Rn →R ∪ {−∞} を凹関数とする. 分離定理は, 図 1 のように, f と h を分離するようなP１次関数の存在を主張する. なお, hp∗ , xi = ni=1 p∗i xi である.
定理 1 (分離定理) f を凸関数, h を凹関数とし, 適当な仮定をおく. f (x) ≥ h(x)(∀x ∈ Rn ) ならば, ある α∗ ∈ R, p∗ ∈ Rn が存在して,f (x) ≥ α∗ + hp∗ , xi ≥ h(x) (∀x ∈ Rn ).

y = f (x)y = α∗ + hp∗ , xi

y 6y = h(x)-x図 1: 凸関数と凹関数の分離定理

y 6y = f (x)−f • (p)y = hp, xi − f • (p)-x

図 2: 共役関数 (Legendre 変換)

Fenchel 双対定理を述べるには, 共役関数の概念が必要である. 関数 f に対し,f • (p) = sup{hp, xi − f (x) | x ∈ Rn }(p ∈ Rn )(1)で定義される関数 f • : Rn → R ∪ {+∞} を f の (凸) 共役関数と呼ぶ. f • は１次関数の最大値として定義されているから凸関数である. 写像 f 7→ f • は, 理工学のあらゆる分野に登場する Legendre 変換に他ならない. 実際, f が滑らかな凸関数
で各 p に対して sup を達成する x = x(p) が存在する場合には, x = x(p) は方程式
f 0 (x) = p の解として定まり, f • (p) = hp, x(p)i − f (x(p)) と表現される. 共役関数の意味は図形的にも理解しやすく, n = 1 の場合, −f • (p) は, y = f (x) の傾き p の接線が y 軸と交わる点の y 座標である（図 2）.
同様に, h の (凹) 共役関数 h◦ : Rn → R ∪ {−∞} をh◦ (p) = inf{hp, xi − h(x) | x ∈ Rn }(p ∈ Rn )と定義するとき, Fenchel 双対定理は次のように述べられる.

(2)

定理 2 (Fenchel 双対定理) f を凸関数, h を凹関数とし, 適当な仮定をおくと,inf{f (x) − h(x) | x ∈ Rn } = sup{h◦ (p) − f • (p) | p ∈ Rn }.
分離定理や Fenchel 双対定理の形に表現される双対性が凸計画問題に対する主問題と双対問題の間の双対性を導くことは, その詳細を知らなくとも, 想像に難くないであろう. 例えば, Fenchel 双対定理において, 左辺が主問題, 右辺が双対問題に対応する. しかし, 凸解析の諸定理が非凸計画問題に対する双対理論の枠組みの基礎にもなっていることは, 必ずしも広く認識されていない. 例えば, 拡張
Lagrange 関数による乗数法などは, 摂動方向に凸性をもった摂動関数の中に原問題を埋め込むことによって導かれている．このように, 凸解析は非線形計画法全体の基礎を成しているのである.
他方, 離散最適化の分野を見てみると, 凸解析のような統一的な視点はまだ存在しない. 離散最適化と非線形最適化は, 本質的に異なる部分も多いことは確かである. しかし, 凸解析の離散版 — 上記の議論で R を Z で置き換えた理論 — ができれば, 離散最適化全体の役に立つに違いない. 例えば, 離散最適化問題に対しても拡張 Lagrange 関数による双対理論ができることになるので, 離散最適化の理論が整理されるだけでなく, 離散最適化を連続最適化に埋め込んで解くタイプのアルゴリズムが設計しやすくなるだろう. 節を改めて, 「離散凸解析」の可能性を探ってみよう.

2離散分離定理「離散凸解析」の一つの目標は, 整数格子点の上で定義された整数値関数 f :Z → Z ∪ {+∞} に対して, 「凸関数」の概念をうまく定義し, 通常の凸解析における諸定理の離散版を確立することである．1 例えば, 分離定理の離散版としては, １次関数が整数ベクトルで定義されることを要請して,n[離散分離定理] f が「凸関数」, h が「凹関数」で, f (x) ≥ h(x) (∀x ∈Zn ) ならば, ある α∗ ∈ Z, p∗ ∈ Zn が存在して,f (x) ≥ α∗ + hp∗ , xi ≥ h(x) (∀x ∈ Zn )を考えるのが自然であり, また最適化との関連で有用でもある. われわれの目標
は, この定理が成り立つような関数のクラスを見出し, それを離散世界の凸関数概念と認識し, さらに, 離散最適化の算法を体系的に構成することである.
極く自然な考えとして, Rn 上の凸関数に拡張可能な f : Zn → Z ∪ {+∞} を「凸関数」と定義してみよう．関数 f : Zn → Z ∪ {+∞} が凸関数に拡張可能とは,ある凸関数 f : Rn → R ∪ {+∞} が存在して f (x) = f (x) (x ∈ Zn ) が成り立つことである. １次元 (n = 1) の場合には, これはf (x − 1) + f (x + 1) ≥ 2f (x)1(∀x ∈ Z)(3)

離散凸解析では，実数値関数 f : Zn → R ∪ {+∞} も扱うが，本稿では整数値関数に限る．

図 3: 凸拡張可能な離散関数 と 凸拡張不可能な離散関数f (x)α∗ + hp∗ , xih(x)図 4: 離散分離定理と同値であり（図 3）, この定義の下で離散分離定理が成立する（図 4）. しかし,多次元 (n ≥ 2) になると, 事情はそう単純でない.
例 1 n = 2 として, f (x1 , x2 ) = max(0, x1 + x2 ), h(x1 , x2 ) = min(x1 , x2 ) を考えると，これらは Z2 上の整数値関数である．それぞれ, R2 上の凸関数 f (x1 , x2 ) =max(0, x1 + x2 ), 凹関数 h(x1 , x2 ) = min(x1 , x2 ) に拡張でき，さらに, f (x) ≥h(x) (∀x ∈ R2 ) である．通常の分離定理の主張どおり，p∗ = (1/2, 1/2) に対して
f (x) ≥ hp∗ , xi ≥ h(x) (∀x ∈ R2 ) が成立する (α∗ = 0 である)．したがって，当然，f (x) ≥ hp∗ , xi ≥ h(x) (∀x ∈ Z2 ) が成立し，この p∗ は f と h を分離する. しかし,f と h を分離する整数ベクトルは存在しない（図 5）.
この例の示すように, 凸拡張可能性による離散凸性の定義では上手くいかず，より深い組合せ論的な考察が必要である. これは, 離散最適化問題を単に連続問題に埋め込む (緩和する) だけでは済まないという当然の事実に対応している.

3

マトロイド性と凸性組合せ最適化の分野では, ネットワークフロー問題や最小木問題に共通する組合せ構造（マトロイド的な構造）が良い性質と認知されている. これを手がかりに離散凸性に迫ろう.
有限集合 V の上の集合関数 ρ : 2V → Z ∪ {+∞} は, 不等式

ρ(X) + ρ(Y ) ≥ ρ(X ∪ Y ) + ρ(X ∩ Y )(X, Y ⊆ V )図 5: 離散分離定理の不成立（例 1）を満たすとき, 劣モジュラ関数と呼ばれる (ρ(∅) = 0, ρ(V ) < +∞ を仮定する).
ネットワークフロー問題や最小木問題に共通するマトロイド的構造とは劣モジュラ性に他ならない.
劣モジュラ性と凸性には似ているところがある. 事実, 既に 60 年代終わりにはその類似性が着目され, 80 年代はじめには A. Frank, S. Fujishige, L. Lovász らの研究によってその関係が明らかになった．例えば, 一般の集合関数 ρ : 2V → Z ∪ {+∞}に対して Lovász 拡張と呼ばれる関数 ρ̂ : RV → R ∪ {+∞} が定義され, 「ρ が劣モジュラ ⇐⇒ ρ̂ が凸」が成り立つ. また, 劣モジュラ関数に関して, 次の形の離散分離定理が成り立つ.
定理 3 (Frank) ρ : 2V → Z ∪ {+∞} が劣モジュラ, µ : 2V → Z ∪ {−∞} が優モ
ジュラ2 で, ρ(X) ≥ µ(X) (∀X ⊆ V ) ならば, ある x∗ ∈ ZV が存在して,ρ(X) ≥ x∗ (X) ≥ µ(X)(∀X ⊆ V ).

これらの事実に基づき, 現在では, 「劣モジュラ関数の双対性 = 凸解析における双対性 + 整数性」という図式が広く受け入れられている.
一方, 整数格子点の (非空) 集合 B ⊆ ZV は, 交換公理(B-EXC) 任意の x, y ∈ B と任意の u ∈ supp+ (x − y) に対して, ある v ∈ supp− (x − y) が存在して x − χu + χv ∈ B かつ y + χu − χv ∈ Bを満たすとき, 整基集合と呼ばれる3 . ここで χu ∈ {0, 1}V は u ∈ V の特性ベクトル（単位ベクトル）を表わし, supp+ (x − y) = {u ∈ V | x(u) > y(u)},2−µ が劣モジュラのとき, µ は優モジュラであるという. ここで, ρ(∅) = µ(∅) = 0, ρ(V ) < +∞,µ(V ) > −∞ は暗黙の仮定である.
3B ⊆ {0, 1}V のとき, マトロイドの基族に対応する.

supp− (x − y) = {v ∈ V | x(v) < y(v)} である. 条件 (B-EXC) の趣旨は, B が 2 点x, y を含めば, より近い 2 点 x − χu + χv , y + χu − χv を含むということであり,通常の凸集合の条件に似ている.
交換公理と劣モジュラ性は次の意味で同等である. x ∈ ZV , X ⊆ V に対して,
Px(X) = v∈X x(v) とおく.
定理 4 対応 (写像)B 7→ ρ : ρ(X) = sup{x(X) | x ∈ B} (X ⊆ V ),
ρ 7→ B = {x ∈ ZV | x(X) ≤ ρ(X) (∀X ⊂ V ), x(V ) = ρ(V )}は, 整基集合 B と劣モジュラ関数 ρ の間の１対１対応を与える.
通常の凸解析では, 集合の凸性と関数の凸性が登場する. 集合 D ⊆ Rn に対し,標示関数 δD : Rn → R ∪ {+∞} を δD (x) = 0 (x ∈ D), = +∞ (x 6∈ D) で定義す
ると, 「D が凸集合 ⇐⇒ δD が凸関数」が成り立つ. 標示関数 δD の共役関数 δD •は正斉次な凸関数であり, D の支持関数と呼ばれる.
このことを思い出しながら「離散凸解析」の立場から定理 4 を見直すと, その本質が凸集合とその支持関数の間の共役関係であることに気づく. すなわち, 「整基集合 : 劣モジュラ関数の Lovász 拡張 = 凸集合 : 支持関数」という対応関係である. この意味で, 従来のマトロイド理論が対象としていたものは, 離散世界の凸集合であると言える. これを拡張して「凸関数」の概念を導入しよう.

4離散世界の凸関数

格子点 p, q ∈ ZV に対して, 成分毎に最大値, 最小値をとって得られる格子点をp∨q, p∧q と表す (すなわち (p∨q)(v) = max(p(v), q(v)), (p∧q)(v) = min(p(v), q(v))(v ∈ V ) である). 関数 g : ZV → Z ∪ {+∞} が, 2 条件

[劣モジュラ性] g(p) + g(q) ≥ g(p ∨ q) + g(p ∧ q) (p, q ∈ ZV ) ,[1 方向の線形性] ∃r ∈ Z, ∀p ∈ ZV : g(p + 1) = g(p) + r(ただし 1 = (1, 1, . . . , 1) ∈ ZV )を満たすとき, g を L 凸関数と定義する. ここで, dom g = {x ∈ ZV | g(x) < +∞}(実効定義域) は空でないとする. 劣モジュラ関数の Lovász 拡張を格子点上に制限したものは正斉次な L 凸関数であり, この逆も成り立つ.
一方, 関数 f : ZV → Z ∪ {+∞} が, 交換公理(M-EXC) 任意の x, y ∈ dom f と任意の u ∈ supp+ (x − y) に対して, ある v ∈ supp− (x − y) が存在して
f (x) + f (y) ≥ f (x − χu + χv ) + f (y + χu − χv )を満たすとき, f を M 凸関数と定義する (dom f 6= ∅ は前提). 条件 (M-EXC) の趣旨は, 2 点 x, y における関数値の和は, より近い 2 点 x − χu + χv , y + χu − χv に移ると減る方向にあるということであり, 通常の凸関数の条件に似ている. 次の(i), (ii) が成り立つことから, (M-EXC) は (B-EXC) の定量的拡張と見なすことができる:(i) M 凸関数の実効定義域は整基集合,(ii) B ⊆ ZV が整基集合 ⇐⇒ B の標示関数 (の ZV への制限) が M 凸関数.
離散システムには, M 凸関数や L 凸関数が自然な形で現れる.
例 2 (行列式の次数) 変数 s に関する多項式を要素とするような行列 A(s) を考える. A(s) は階数が m の m × n 行列であるとし, その列番号の集合を V と表す. 例
えば,
12 3 4s+1 s 1 0A(s) =,1
1 1 1m = 2, n = 4, V = {1, 2, 3, 4} である. A(s) の列ベクトルの基底に対応する V の部分集合の族を B (⊆ 2V ), B の元の特性ベクトルの全体を B (⊆ {0, 1}V ) とする.
すなわち, B = {χJ | J ∈ B} である (χJ は J の特性ベクトル). B が整基集合の公理 (B-EXC) を満たすことは, よく知られた事実である. 上の例では, A(s) のどの２列も A(s) の基底であるから,
B = {(1, 1, 0, 0), (0, 0, 1, 1), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1)}である. J ∈ B に対応する A(s) の部分行列 (m 次正方行列) を A[J] と表すとき, その行列式 det A[J] は s に関する (0 でない) 多項式であり, その次数 degs det A[J]を考えることができる.
(f (x) =− degs det A[J] (x = χJ , J ∈ B)+∞(otherwise)で定義される関数 f : ZV → Z ∪ {+∞} は M 凸関数である (証明は, GrassmannPlücker の関係式を利用する). 上の例では, B0 = {(1, 1, 0, 0), (0, 0, 1, 1)} として,f (x) = 0 (x ∈ B0 ), = −1 (x ∈ B \ B0 ), = +∞ (x ∈ ZV \ B) となる.
L 凸関数も多項式行列から生ずる. p ∈ ZV に対して, spv (v ∈ V ) を対角要素とする n 次対角行列を D(p) と表し, A と D(p) の行列積の部分行列で J に対応する列からなるものを (A · D(p))[J] と書き表す. 関数 g : ZV → Z をg(p) = max{degs det(A · D(p))[J] | J ∈ B}と定義すると, これは L 凸関数である. 上の例では,g(p) = max(p1 + p2 , p3 + p4 , p1 + p3 + 1, p1 + p4 + 1, p2 + p3 + 1, p2 + p4 + 1)となる.

5

離散凸解析の基本諸定理

M 凸性, L 凸性の概念の重要性は, 以下の諸定理に示されている. まず最初の定理は，M 凸関数, L 凸関数が確かに凸関数と呼ぶにふさわしいものであることを示している.
定理 5 (拡張定理) M 凸関数, L 凸関数は凸関数に拡張可能である.
離散世界での共役関数 f • : ZV → Z ∪ {+∞} を, 式 (1) に倣って,f • (p) = sup{hp, xi − f (x) | x ∈ ZV }(p ∈ ZV )(4)と定義する. 次の定理は, M 凸関数と L 凸関数の間の共役関係を示しており, 定理4 (交換公理と劣モジュラ性の同等性) の一般化である. 例 2 の f と g は, この意味の共役関係にある.
定理 6 対応 (写像) f 7→ g = f • , g 7→ f = g • は, M 凸関数 f と L 凸関数 g の間の１対１対応を与える．さらに，f •• = f , g •• = g が成り立つ.
通常の連続世界では，凸関数の概念に M とか L とかの区別はなく，凸関数の共役は再び凸関数である．これに対して，離散世界では，２種類の凸性が区別され，それらが f 7→ f • によって移り合うという状況になっている．
最後に双対定理を与える. (M, L) 凹関数 h : ZV → Z ∪ {−∞} に対して,dom h = {x ∈ ZV | h(x) > −∞},h◦ (p) = inf{hp, xi − h(x) | x ∈ ZV }と定義する. なお, h が (M, L) 凹関数とは, −h が (M, L) 凸関数のことである.
定理 7 (M 分離定理) f を M 凸関数, h を M 凹関数とし, dom f ∩ dom h 6= ∅ ま
たは dom f • ∩ dom h◦ 6= ∅ が成り立つと仮定する. f (x) ≥ h(x) (∀x ∈ ZV ) ならば, ある α∗ ∈ Z, p∗ ∈ ZV が存在して,f (x) ≥ α∗ + hp∗ , xi ≥ h(x) (∀x ∈ ZV ).
定理 8 (L 分離定理) g を L 凸関数, k を L 凹関数とし, dom g ∩ dom k 6= ∅ または dom g • ∩ dom k ◦ 6= ∅ が成り立つと仮定する. g(p) ≥ k(p) (∀p ∈ ZV ) ならば,ある β ∗ ∈ Z, x∗ ∈ ZV が存在して,g(p) ≥ β ∗ + hp, x∗ i ≥ k(p) (∀p ∈ ZV ).
定理 9 (Fenchel 型双対定理) f を M 凸関数, h を M 凹関数とし, dom f ∩dom h 6=
∅ または dom f • ∩ dom h◦ 6= ∅ が成り立つと仮定すると,

inf{f (x) − h(x) | x ∈ ZV } = sup{h◦ (p) − f • (p) | p ∈ ZV }.

図 6: 簡単な力学系

M 分離定理と L 分離定理は共役関係にあり, Fenchel 型双対定理は自己共役である. また, L 分離定理は劣モジュラ関数に関する離散分離定理の一般化である.
これらの離散双対定理は, 見かけは通常の凸解析における双対定理と同じである
が, その本質は組合せ論的に深い内容を含んでいる. 拡張定理 (定理 5) と通常の分離定理 (定理 1) や Fenchel 双対定理 (定理 2) を合わせても上の離散双対定理は導かれない (例 1 参照). 事実，証明は真に組合せ論的であり，連続世界の双対定理の証明が解析的であるのと全く対照的である．
以上の諸定理を基礎として, 劣勾配や双共役関数などの離散版が定義され, さらに離散最適化に対する Lagrange 双対理論が展開される.

6

システム解析への応用

離散双対定理がどのような形で応用に現れるかを手短かに説明しよう．図 6 に示すような簡単な力学系を考える.
この力学系は質量が m1 , m2 であるような二つの箱（質点）, バネ定数 k1 , k2の二つのバネ（力 = ki × 変位）および一つのダンパー（力 = f × 速度）から成り立っている (外力は考えない).
このシステムを記述する変数の選び方はいろいろありうるが, 例えば,

x1 :
x2 :
x3 :
x4 :
x5 :
x6 :

質点 m1 の釣合い位置からの (下向き) 変位
質点 m2 の釣合い位置からの (下向き) 変位
質点 m1 の (下向き) 速度
質点 m2 の (下向き) 速度
ダンパーによる力二つの質点の相対速度の６変数をとって, (周波数領域で) A(s)x = b の形に書くことができる (右辺ベクトル b は初期条件で決まる). ただし,A(s) =x1x2x3x4x5 x6−s0100 00−s010 0−k1 0 −sm10−1 00 −k20−sm2 1 00000−1 f−ss000 1であり, 変数 s は時間微分に対応する. いま, われわれは６個の変数を用いてこのシステムを記述したが, 最低限必要な変数の個数（標準形に書き直したときの変数の個数）は, 実は４個である（x1 ∼ x4 でよい）. 一般に, A(s)x = b を標準形に書き直したときの変数の個数は, 係数行列 A(s) の行列式 det A の s についての次数 degs det A に等しい. 意外なことに, この量 degs det A を計算する際に, 「離散凸解析」の結果が役に立つのである.
まず, 行列 A(s) から物理パラメータを含む部分を分離して,A(s) = Q(s) + T (s)と表現する. ここで,Q(s) =x1 x2 x3 x4 x5−s 0 1 0 00 −s 0 1 00 0 0 0 −10 0 0 0 10 0 0 0 −1−s s 0 0 0x6000 , T (s) =001x1 x2 x3x4 x50 00000 0000−k1 0 −sm1 000 −k2 0 −sm2 00 00000 0000x60000f0である. 物理パラメータ {m1 , m2 , k1 , k2 , f } を独立変数と仮定すると,

degs det A = max {degs det Q[I, J] + degs det T [R \ I, C \ J]}|I|=|J|I⊆R,J⊆C(5)が成立する (R, C は行番号, 列番号全体の集合を表す). ここでfQ (I, J) = degs det Q[I, J],fT (I, J) = degs det T [I, J],f (I, J) = fQ (I, J) + fT (R \ I, C \ J)
とおくと, 式 (5) の右辺は, 行集合と列集合の組 (I, J) の中で目的関数 f (I, J) を最大化するものを見つけるという, 組合せ最適化問題である.
この組合せ最適化問題を解くのに「離散凸解析」の結果が利用できる. 二つの関数 fQ , fT は, 例 2 に説明した事実により, 本質的に M 凹関数である. したがって, 付値マトロイド交差問題に対する算法（[1] 参照）を利用して式 (5) の右辺を効率的に計算できる. 算法の詳細に立ち入る余裕はないが, この算法が次の定理(M 分離定理の特殊ケース) に立脚していることを注意しておく.

定理 10 ある整数ベクトル p ∈ ZR と q ∈ ZC が存在して,Ãij = s−pi +qj Aij ,Q̃ij = s−pi +qj Qij ,T̃ij = s−pi +qj Tij

で定義される行列 Ã = Q̃ + T̃ に対してdegs det Ã = max degs det Q̃[I, J] + max degs det T̃ [R \ I, C \ J]
|I|=|J|I⊆R,J⊆C|I|=|J|
I⊆R,J⊆Cが成立する.
上の定理のベクトル (p, q) は, M 分離定理における分離ベクトル p∗ に対応する.
ベクトル (p, q) によって, 式 (5) の最大化が Q(s) と T (s) の部分に文字通り分離されている.

7

おわりに最後に，M 凸関数，L 凸関数に至る離散凸関数概念の歴史を簡単に述べる．マトロイドの概念は H. Whitney によって 1935 年に導入された．1960 年代の終わりに J. Edmonds によってポリマトロイド交わり定理が発見されたのを契機として劣モジュラ集合関数の研究が盛んになり，劣モジュラ関数と凸関数との類似性が漠然とした形で議論された．1980 年代はじめ， 藤重悟, A. Frank, L. Lovász らの研究により，劣モジュラ集合関数のもつ凸性と離散性が明確になった． 1990 年
代にはいって，A. Dress と W. Wenzel により，付値マトロイドの概念が導入された. 数年後，筆者によりその双対定理が示され，離散凸性との関連が認識された．これらとは独立に，P. Favati と F. Tardella により，整凸関数の概念が考察された. 「離散凸解析」の枠組みは，1980 年代の議論を背景としながら，1996 年頃に認識された．

参考文献[1] K. Murota: Matrices and Matroids for Systems Analysis, Springer-Verlag,
Berlin, 2000.
[2] 室田一雄: 離散凸解析, 共立出版, 2001.
[3] K. Murota: Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, Vol. 10, SIAM, Philadelphia, 2003.