OR 学会誌 (1997 年 1 号): ＯＲ研究の最前線
離散凸解析: 組合せ最適化における凸性
京都大学

数理解析研究所

室田一雄

1: 歴史 (マトロイド性と凸性)
1935 年頃 Whitney
マトロイドの公理
表1.

はじめに| 凸関. そ数の理論 | がその理論的なコアとなっているの一番簡単で有用な例が，線形計画 (LP) の双対定理である. もっとも，凸解析を深く理解しないと非線形計画の交換公理

連続変数に関する最適化の分野では，凸解析[3;5]1965 年頃 Edmonds, 劣モジュラ性ポリマトロイド
多面体的方法アルゴリズム設計ができないかというと，実はそうでも劣モジュラ関数ないらしいが，７０年代に凸解析の枠組みに則って考案

交叉定理

1975 年頃

された乗数法などは，個人的には，とても美しく感じら.

れた（もう１５年以上昔の感激である）,他方 離散変数に関する最適化（組合せ最適化）の分野,を見てみると 凸解析のような統一的な視点は存在しな. しかし，マトロイド的な構造 | ネットワークフロー問題や最小木問題に共通する組合せ構造 | が良い性質と. さらに，次の２点で，マトロイド性認知されているは凸性と似ている.
 局所最適条件が大域的最適性を特徴づける. したがって, 局所的な降下法によって最適化が達成される.
 最大・最小定理のような双対性が成り立つ. これによって, 双対変数を利用した算法が構成できる.
マトロイド性と凸性のこのような類似性は既に 60 年代の終わりには注目され, 80 年代はじめには A. Frank, S.
Fujishige, L. Lovasz らの研究によってその関係が明らかになった. その結果，現在では, 「マトロイドの双対性 =い

1982 年頃. 1

重み分割の存在
凸性との関係双共役拡張

適化の世界に双対理論の枠組みを与えようとする試みで+ 整数性」という図式が広く受けある. 理論展開のシナリオは通常の凸解析の真似をし，数学的側面はネットワーク・マトロイド理論を拡張する,入れられている 表 に，マトロイド研究の歴史のなかで凸性と関係する出来事を抜きだして示してあるポテンシャルの存在

Frank
離散分離定理Fujishige
Fenchel 双対定理
LovaszLovasz 拡張
1990 年頃 Dress-Wenzel 付値マトロイド
公理, 貪欲算法
1995 年頃 Murota
付値付き交叉問題
分離定理 (M-, L-)
Fenchel 双対定理

[2;4]

凸解析における双対性

Edmonds
Lawler
Iri-TomizawaFrank

重み付き交叉問題. 最右欄ので，標語的には時間スケールだけを眺めて頂きたい.
ここで解説する「離散凸解析」は, 上の図式を拡張する= マトロイド理論＋凸解析 」となる. 通常の凸解析では, 集合の凸性と関数の凸性が議ことによって，整数計画や組合せ最適化のような離散最論されるが，「離散凸解析」の立場から見ると，従来ののキーワードは当面無視して，この分野が進展してきた「離散凸解析マトロイド（および劣モジュラ関数）の理論は離散世界. では，凸関数のむろた かずお 京都大学数理解析研究所の凸集合の話であると位置づけられる〒概念はどうなっているのか？それが「離散凸解析」の主606-01 京都市左京区北白川追分町

題であって，答は1M 凸関数と L 凸関数の概念である.

さて，

y = f (x){ 最大流 { マトロイド { 劣モジュラ関数
凸関数 { 最小費用流 { M 凸関数 { L 凸関数の対応関係を予告して， OR らしい話題へと進もう.
凸集合2.

y = 3 + hp 3 ; x i

最大流から最小費用流へ. つまり，通常のネットワークフローの問題を考える
有向グラフ

G = (V; A) の枝に容量制約が与えられていyるときに，どのような整数フローが可能かを考える問題である. よく知られた最大流問題もこの種の問題である.

6

ここでは，より具体的に，各頂点での供給量を表すベクトルy = g(x)-xx 2 Z を実現する整数フローが存在するかどうかV

図1: 分離定理

を問題とし，ある整数フローによって実現可能な供給量x 2 Z の全体を B  Z とする.
この集合 B はいろいろな性質をもっている. 例えば，B に属する x の成分の和はつねに 0 に等しいとか， B には「穴」が空いていないとか，などなど. B のもついろベクトルVV(M-EXC) として抽出し，この種の関数を M 凸関数と呼ぶことになる. さらに， M 凸関数と裏腹の概念として L 凸関数の概念が定義される（なお，以後，裏腹のことを共役と呼ぶ）.の性質を交換公理

いろな組合せ的な性質の中で最も大切なものを公理とし以上，雑な議論で恐縮であるが，要するに，従来のマて抽象化したものが，マトロイドとか基多面体とか呼ば.
4.1 節で，整基集合の公理 (B-EXC) という形できちんと説明するが，ここトロイド・劣モジュラ関数の理論が最大流問題の抽象化れる概念である これについては，第では，集合と位置づけられるのに対し，「離散凸解析」は最小費用.

B は離散凸集合と呼ぶにふさわしい良い性質

流問題の抽象化に対応するということである.

3.

をもっている，ということだけを知って欲しい

最大流・最小カットの定理というのがあることは，ご存知の通りである. くわしい内容は覚えていなくて結構

3.1 連続世界の双対性であるが，この定理の主張は，フローとカットは表裏一.

.

する 双対性の表現にはいろいろあるが，一番わかり易い

B がよい性質をもっているとすると，.のは，分離定理の形であろう

凸関数

れを抽象化したものが，劣モジュラ関数という概念であ. 劣モジュラ関数の定義は第 4.1 節で説明するが，こ.

iin

ネットワークフローの問題では，フローの流量だけで. 各枝に，容nなく，フローのコストも考えることが多い

量制約の他に，単位流量あたりのコストが与えられていnx を最小コストで実現するようなフローを求める問題が，最小費用流問題と呼. x を実現するフローの最小コストをf (x) と書くと，これは B を定義域とする関数である. この関数はどんな性質をもっているのだろうか.
ばれるものである

nf は離散凸関数と呼ぶにふさわしい良い性質をもっているのである

ni=1る，ということだけを記憶して欲しい

結論を述べると，この関数

nn

こでは，劣モジュラ関数は離散凸集合と裏腹の概念である状況を設定し，供給量ベクトル. f : R ! R [ f+1g を, g : R ! R [ f01g を凹関数とするとき，分離定理は, 図 1のように, f と g を分離するような１次関数
P p3x である.の存在を主張する. なお, hp3 ; xi =定理 1 (分離定理) f を凸関数, g を凹関数とし, 適当な仮定をおく. g (x)  f (x) (8 x 2 R ) ならば, ある3 2 R, p3 2 R が存在して,g(x)  3 + hp3 ; xi  f (x) (8 x 2 R ):双対性の別の表現として， Fenchel 双対定理がある.
関数 f に対し,f  (p) = supfhp; xi 0 f (x) j x 2 R g (p 2 R )(1)で定義される関数 f  : R ! R [ f+1g を f の (凸) 共役関数と呼ぶ. 共役関数の意味は図形的にも理解しやす

カットの全体も何かよい性質をもっているに相違ない こる,

まず 通常の凸解析における双対性について簡単に復習

体，ということであった さて，フローで実現できる供給量ベクトルの全体双対定理とはn. われわれはそ2n,

さて，われわれの目標は この定理が成り立つような関y = f (x)y6,.

, R 上の凸関数に拡張可能なn極く自然な考えとして

f : Z ! Z [ f+1g を「凸関数」と定義してみたくな()0f  p.

nる しかし，この定義の下では，離散分離定理は成り立た.

4.

有限集合,.と凸性には似ているところがある. 例えば, 一般の集合関
asz 拡張と呼ばれる数  : 2 ! Z [ f+1g に対して Lov
正斉次な 関数 ^ : R ! R [ f+1g が定義され,「 が劣モジュラ () ^ が凸」が成り立つ. また, 劣モジュラ関数に関してある種の離散分離定理が成り立つ.
一方, 整数格子点の (非空) 集合 B  Z は, 交換公理
VV1V(B-EXC) 任意の x; y 2 B と任意の u 2supp (x 0 y) に対して, ある v 2 supp0(x 0 y)が存在して x 0  +  2 B かつ y +  0  2+が凸計画問題に対する主問題と双対問題の間の双対性を. 例えば, FenchelB

双対定理において 左辺が主問題 右辺が双対問題に対応.

(X;Y  V )を満たすとき 劣モジュラ関数と呼ばれる 劣モジュラ性n,V(X ) + (Y )  (X [ Y ) + (X \ Y )nn

V の上の集合関数  : 2 ! Z [f+1g は, 不等式

nn

離散世界の凸性

4.1 離散凸集合としてのマトロイド, n = 1 の場合, 0f  (p) は, y = f (x) の傾き p の接線が y 軸と交わる点の y 座標である (図 2参照). 同様に, gの (凹) 共役関数 g  : R ! R [ f01g をg (p) = inf fhp;xi 0 g(x) j x 2 R g (p 2 R ) (2)と定義するとき, Fenchel 双対定理は次のように述べられる.
定理 2 (Fenchel 双対定理) f を凸関数, g を凹関数とし, 適当な仮定をおくと,inf ff (x)0g(x) j x 2 R g = supfg(p)0f (p) j p 2 R g:分離定理や Fenchel 双対定理の形に表現される双対性
,

uvu,

Vu+,

離散世界の分離定理としては １次関数が整数ベクトル,v.
 2 f0; 1gは u 2 V の特性ベクトルを表わし, supp (x 0 y ) = fu 2V j x(u) > y(u)g, supp0 (x 0 y) = fv 2 V j x(v) <y(v)g である. 条件 (B-EXC) の趣旨は, B が 2 点 x, y を含めば, より近い 2 点 x 0  +  , y +  0  を含むということであり, 通常の凸集合の条件に似ている.
を満たすとき 整基集合と呼ばれる ここで3.2 離散世界の双対性)

けでは話は済まないということである

く,(離散最適化問題を単に連続問題に埋め込む 緩和する だ

2: 共役関数 (Fenchel-Legendre 変換)

導くことは 想像に難くないであろう.

ない よく考えてみればこれは当然であって，つまりは，xy = hp; xi 0 f (p)する,

し さらに 離散最適化の算法を体系的に構成することである

図,数のクラスを見出し それを離散世界の凸関数概念と認識で定義されることを要請して[離散分離定理] f が「凸関数」, g が「凹関数」で,g(x)  f (x) (8 x 2 Z ) ならば, ある 3 2 Z, p3 2 Zが存在して,g(x)  3 + hp3 ; xi  f (x) (8 x 2 Z )を考えよう. ここで，「何故，この形の分離定理を考えnunvuv

マトロイド理論においては，整基集合と劣モジュラ関.

数の間に１対１対応があることが知られている これは，n第２節に述べた供給量ベクトルとカットの対応関係にあたるが，この事を凸解析の立場から見るとどう位置づけ.

られるかを考えてみようるのか」と問われれば，「ネットワーク・マトロイド理論をやっていると，この形が感覚的に最も自然に思える1.

から」と答えたい3^ が正斉次とは, 任意の  > 0 と p 2^(p) が成り立つことを言う.

Rn に対して ^(p) =,, f を M 凸関数と定義する (dom f 6= ; は前提). 条件 (M-EXC) の趣旨は, 2 点 x, y における関数値の和は, より近い 2 点 x 0  +  , y +  0  に移ると減る方向にあるということであり, 通常の凸関数の条件に似ている. 次の (i), (ii) が成り立つことから, (M-EXC)
は (B-EXC) の定量的拡張と見なすことができる:(i) M 凸関数の実効定義域は整基集合,(ii) B  Z が整基集合() B の標示関数 (の Z への制限) が M 凸関数.
既に述べたように最小費用流問題に関連して M 凸関数が現れるが，この他にも，離散システムには, M 凸関数
や L 凸関数が自然な形で現れる.

通常の凸解析では 集合の凸性と関数の凸性が登場する

D の凸性は標示関数  の凸性に帰着される.
すなわち，集合 D  R に対し, 標示関数  : R !
R [ f+1g を  (x) = 0 (x 2 D), = +1 (x 62 D) で定義するとき，「D が凸集合 ()  が凸関数」が成り立つ. 標示関数  の共役関数   は正斉次な凸関数であり, D の支持関数と呼ばれる.
が，集合DnnDuD

DDD,凸集合Lovasz 拡張 = 支持関数 (3)という対応関係である. この意味で, 従来のマトロイド理論が対象としていたものは, 離散世界の凸集合（とその支持関数）であると言える. 劣モジュラ関数という集合関整基集合
劣モジュラ関数の5.

. したがって，離散世界の「凸関数」としては，もっと一般的な対象を導入する必要がある

4.2 L 凸関数と M 凸関数

V. 格子点

離散世界の「凸関数」の概念を導入しよう

p;q 2 Z に対して, 成分毎に最大値, 最小値をとって得られる格子点を p _ q , p ^ q と表す. すなわち, v 2 Z にVVV

対し，(p_q)(v) = max(p(v); q(v)); (p^q)(v) = min(p(v); q(v))
である. 関数 g : Z ! Z [ f+1g が, 2 条件
[劣モジュラ性]g(p) + g(q)  g(p _ q) + g(p ^ q) (p; q 2 Z ) ,[1 方向の線形性]
9r 2 Z; 8p 2 Z : g (p + 1) = g (p) + r(ただし 1 = (1; 1; : : : ; 1) 2 Z )を満た すとき, g を L 凸 関数と定 義する.
ここ で,
dom g = fx 2 Z j g(x) < +1g (実効定義域) は空asz 拡張のもつ性質でないとする. 劣モジュラ関数の Lovのうち，正斉次性を捨て去ったものが L 凸関数である.
一方, 関数 f : Z ! Z [ f+1g が, 交換公理(M-EXC) 任意の x; y 2 dom f と任意の u 2supp (x 0 y) に対して, ある v 2 supp0(x 0 y)VV

して，離散世界では，２種類の凸性が区別され，それらVがf 7! f  によって移り合うという状況になっている.
最後に双対定理を与える. (M, L) 凹関数 g : Z !
VZ [ f01g に対して,Vdom g = fx 2 Z j g(x) > 01g;g (p) = inf fhp; xi 0 g(x) j x 2 Z gと定義する. なお, g が (M, L) 凹関数とは, 0g が (M, L)
凸関数のことである.
VVV+が存在して2f (x)+ f (y)  f (x 0  +  )+ f (y +  0  )
uV

[9]Vv

離散凸解析の諸定理

[9].

uv

M 凸関数, L 凸関数に関する諸定理を示そう. まず最初の定理は， M 凸関数, L 凸関数が確かに凸関数と呼ぶにふさわしいものであることを示している.
定理 3 (拡張定理 ) M 凸関数, L 凸関数は凸関数に拡張可能である.
離散世界での共役関数 f  : Z ! Z [ f+1g を, 式(1) に倣って,f  (p) = supfhp; xi 0 f (x) j x 2 Z g (p 2 Z )(4)と定義する. 次の定理は, M 凸関数と L 凸関数の間の共役関係を示しており, 交換公理と劣モジュラ性の同等性 (3)の一般化である.
定理 4 (共役性定理 ) 対応 (写像) f 7! g = f  , g 7!
f = g は, M 凸関数 f と L 凸関数 g の間の１対１対応を与える. さらに， f  = f , g  = g が成り立つ.
通常の連続世界では，凸関数の概念に M とか L とかの区別はなく，凸関数の共役は再び凸関数である. これに対数は，正斉次凸関数の仮の姿であり，関数ではなくむしろ集合に対応しているのである

uV数の対応関係の本質は，凸集合とその支持関数の間の共.

vV

このような立場からみると，整基集合と劣モジュラ関役関係である すなわち

2を満たすときv4

dom f  f0; 1gV のときが Dress{Wenzel[1] の付値マトロイドに対応する.

定理

5 (M 分離定理 ) f を M 凸関数, g を M 凹関数[8;9]

M 分離定理f (x)  g(x), dom f \ dom g 6= ; または dom f  \ dom g 6= ;が成り立つと仮定する. g (x)  f (x) (8 x 2 Z ) ならば,ある 3 2 Z, p3 2 Z が存在して,g(x)  3 + hp3 ; xi  f (x) (8 x 2 Z ):定理 6 (L 分離定理 ) f を L 凸関数, g を L 凹関数とし, dom f \ dom g 6= ; または dom f  \ dom g 6= ;が成り立つと仮定する. g (p)  f (p) (8 p 2 Z ) ならば,ある 3 2 Z, x3 2 Z が存在して,g(p)  3 + hp; x3 i  f (p) (8 p 2 Z ):) f を M 凸関数, g を定理 7 (Fenchel 型双対定理
M 凹関数とし, dom f \ dom g 6= ; または dom f  \dom g 6= ; が成り立つと仮定すると,inf ff (x)0g(x) j x 2 Z g = supfg (p)0f (p) j p 2 Z gが成り立つ. さらに，この値が有限値のときは，左辺の下限 (inf) と右辺の上限 (sup) を達成する x 2 dom f \dom g と p 2 dom f  \ dom g が存在する.
この Fenchel 型双対定理は，とても簡潔な形をしているとし

VmVVFenchel 双対性
inf ff 0 gg= supfg 0 f g[9]VV>> () 劣モジュラ関数の><分離定理 (Frank)>> (P2)>> () 付値付き交叉問題>:
最適規準 (Murota)

m+L 分離定理f  (p)  g (p)

V

[8;9]

VFenchel 双対性 (Fujishige)
8> (P1)交叉定理 (Edmonds)m>

図V

重み付き交叉問題
最適規準(Edmonds, FrankIri-Tomizawa)

3: 双対定理の関係 (f は M 凸関数， g は M 凹関数).
(理 3) と通常の分離定理 (定理 1) や Fenchel 双対定理 (定理 2) を合わせても上の離散双対定理は導かれない. 離散世界の双対性は，連続世界の双対性とは別物である.
本質は組合せ論的に深い内容を含んでいる 拡張定理 定ので，一見するとインパクトがないかも知れないけれ. LP の双対定理の主張にも，定性的な部分 P1 と定量的な部分 P2 があったことを思いだして欲しい.
P1(実行可能性) dom f  \ dom g 6= ; かつ supfg(p) 0f  (p) j p 2 Z g が有限値ならば， dom f \ dom g 6=;. [すなわち，双対問題が実行可能で有界ならば，主問題は実行可能である.]
P2(最適値) dom f \ dom g 6= ; かつ inf ff (x) 0 g(x) jx 2 Z g が有限値ならば， f (x3 ) 0 g(x3 ) =g (p3 ) 0 f  (p3 ) を満たす x3 と p3 が存在する. [す6.

ど，実は次の二つの主張を含んでいる,前節の諸定理を基礎として 劣勾配や双共役関数などの,離散版が定義され さらに離散最適化に対するLagrange. 算法的側面や実際的有効性については，まだ未知数という状況である. 将来の動双対理論が展開される [9]V

向についても何か書くように編集委員から言われたのであるが，これは難問であって，書きにくい. 1997 年 8月にスイスのローザンヌで開催される数理計画シンポジ

organized session （題は valuated matroid）が A. Dress 氏と著者によって計画されていることだけに触れておく.
ウムで，この種の話題のV

なわち，主問題が実行可能で有界ならば，主問題の.]「離散凸解析」については，文献 [10] にも解説を書く.

最適値と双対問題の最適値は等しい

3

おわりに機会を与えられた できるだけ相補的な内容にしたつもり. M 分離定理と L 分離定理は互いに共役関係にあり, Fenchel 型双対定理は自己共役である. また, Fenchel 型双対定理の定性的な部分 P1 が劣モジュラ関数に関する離散分離定理に相当し，定量的な部分 P2 が重み付き交叉問題に関する最適規準の一般化である. これらの離散双対定理は, 見かけは通常の凸解析における双対定理と同じであるが, その離散双対定理の間の関係を図 に示しておく.

なので，併せて読んで頂ければ幸いである 本稿では，最小費用流問題を研究の動機として取り上げたが，実は，これはOR 誌向きの脚色である. 本当の動機は，１０年ほど前に，工学システムの離散構造を調べる枠組みを模索している間に考え始めた多項式行列の問題 [6] である
これについては，文献[10;11].

.に解説した編集委員の水野真治氏（統計数理研究所）には本研究

5

の意義を認めて頂き，解説記事を書く機会を与えて頂い. また匿名の編集委員の方には，原稿を読み易くするためのコメントを頂いた. 最後になったが，両氏に感謝の意を表したい.
た

参考文献[1] A. W. M. Dress and W. Wenzel: Valuated matroids, Advances in Mathematics, 93 (1992) 214{250.
[2] S. Fujishige: Submodular Functions and Optimization, North-Holland, Amsterdam, 1991.
[3] 福島雅夫 : 非線形最適化の理論, 産業図書, 1980.
[4] 伊理正夫, 藤重悟, 大山達雄 : グラフ・ネットワー
ク・マトロイド, 産業図書, 東京, 1986.
[5] 今野浩，山下浩 : 非線形計画法, 日科技連, 1978.
[6] K. Murota: Use of the concept of physical dimensions in the structural approach to systems analysis, Japan J. Appl. Math., 2 (1985), 471{494.
[7] K. Murota: Valuated matroid intersection, I: optimality criteria, II: algorithms, SIAM Journal on
Discrete Mathematics, 9 (1996), No. 4.
[8] K. Murota: Convexity and Steinitz's exchange
property, Advances in Mathematics, 掲載予定. Integer Programming and Combinatorial Optimization (W. H. Cunningham, S. T. McCormick, andM. Queyranne, eds.), Lecture Notes in Computer
Science 1084, Springer-Verlag, 1996, pp.260-274に extended abstract あり.
[9] K. Murota: Discrete convex analysis, RIMS
Preprint No. 1065, 京都大学数理解析研究所, 1996.
[10] 室田一雄 : 離散凸解析, 応用数理， 6 (1996), No. 4.
[11] K. Murota: Structural approach in systems analysis by mixed matrices | An exposition for indexof DAE, ICIAM 95 (K. Kirchgassner, O. Mahrenholtz, and R. Mennicken, eds.), Mathematical Research 87, Akademie Verlag, 1996, pp. 257{279.

6