離散凸解析の理論とアルゴリズム
塩浦 昭義（東北大学 大学院情報科学研究科）
2010/07/02 Dehnセミナー（東北大 情報科学研究科）

発表の流れ 離散凸解析の概要
 基本概念（M凸関数，L凸関数）の定義
 M凸関数，L凸関数の性質
 M凸性，L凸性の一般化
 （アルゴリズム）
 幾何への応用

離散凸解析の概要

最適化問題（数理計画問題）
 与えられた解集合Sから与えられた関数 f を最小化（最大化）する解を求める

Ｍｉｎｉｍｉｚｅ （Ｍａｘｉｍｉｚｅ） ｆ（ｘ）
subject tox∈S
Sが実数ベクトル集合連続最適化
Sが整数ベクトル集合，離散的な集合
離散最適化

最適化問題の例
 連続最適化問題の例

 離散最適化問題の例

最適化問題と凸性
解きやすい
最小全域木問題
最短路問題
最大流問題
最小費用流問題

凹関数最小化
DC計画
非凸計画

ナップサック問題
安定集合問題
巡回セールスマン問題
2次割当問題
解きにくい

離散最適化

連続最適化

線形計画
凸2次計画
半正定値計画
2次錐計画
凸計画

共通する良い構造
解きやすい
「凸性」
線形計画
最小全域木問題
凸2次計画
最短路問題
半正定値計画最大流問題
2次錘計画
最小費用流問題
凸計画
凹関数最小化
DC計画
非凸計画

ナップサック問題
安定集合問題
巡回セールスマン問題
2次割当問題
解きにくい

離散最適化

統一的な枠組「凸解析」 連続最適化

最適化問題と凸性

共通する良い構造
解きやすい「マトロイド＋凸性？」
最小全域木問題
最短路問題
最大流問題
最小費用流問題

凹関数最小化
DC計画
非凸計画

ナップサック問題
安定集合問題
巡回セールスマン問題
2次割当問題
解きにくい

離散最適化

連続最適化

線形計画
凸2次計画
半正定値計画2次錘計画
凸計画

統一的な枠組は存在しなかった

最適化問題と凸性

離散凸解析の目指すところ
解きやすい離散最適化問題（貪欲に解ける，多項式時間で解ける）

組合せ論からの視点
マトロイド理論

統一的枠組

共通する構造：離散凸性

離散凸解析

解析的な視点凸解析

離散凸解析の目指すところ
 離散凸解析の目標
 「離散凸」にふさわしい概念を見いだす

交換公理 M凸性
 劣モジュラ集合関数劣モジュラ性L凸性
 （ポリ）マトロイド

 通常の凸解析における諸定理の離散版を確立する
 最小性基準，共役性，双対定理，など

 離散最適化のアルゴリズムを体系的に構成する
 関数最小化アルゴリズムなど

 様々な分野への応用を広げる オペレーションズ･リサーチ（在庫管理，スケジューリング），制御，ゲーム理論，組合せオークション，数理経済，数学

離散凸解析の歴史
1935 マトロイド
Whitney, 中澤
1965 劣モジュラ関数，ポリマトロイド
Edmonds
1975 マトロイドの応用
伊理，富澤，Recski
1983 劣モジュラ関数と凸性 Lovász, Frank, 藤重
1992 付値マトロイド
Dress, Wenzel
1996 離散凸解析の提唱，Ｍ凸／Ｌ凸性
室田
1996-2000 Ｍ凸／Ｌ凸性の拡張 室田，塩浦，藤重M凸関数とL凸関数の定義

凸関数
定義： f: RnR∪{+∞} が凸関数


非凸関数
凸関数

等価な定義： f のエピグラフ
epi f = {(x, α) | α≧f(x)} が凸集合

連続最適化における凸関数の意義
 局所最適性＝大域的最適性

降下アルゴリズム
 双対定理，分離定理
主双対アルゴリズム，感度分析
目的関数が凸関数，集合が凸集合
 連続最適化問題は「解きやすい」

離散最適化における「凸性」とは？
 f: ZnRに対する「凸性」
 望ましい性質 問題が「離散凸性」をもつ問題が「解きやすい」
 普通の凸関数への拡張可能性
 局所最適性＝大域的最適性
 双対定理，分離定理

凸拡張可能性と離散凸性
 定義：

f: ZnR が凸拡張可能

凸拡張可能

凸拡張可能

1次元の場合：これで十分2次元以上の場合：凸拡張可能性だけでは良い性質が得られない
 離散数学の成果を利用

劣モジュラ関数
 g:ZnR が劣モジュラ

X∪YXX∩YYN

劣モジュラ集合関数と離散凸性

 最小化／最大化アルゴリズム
 最小化は効率的に解ける， 最大化は計算困難

 凸拡張可能 (Lovász) 集合関数が劣モジュラLovász拡張が凸関数

 双対定理，分離定理 (Edmonds, Frank, 藤重)Ｌ凸関数の定義
g: ZnR∪{+∞}p∨q 成分ごとの最大値p∧q 成分ごとの最小値

定義[室田]： g がL凸関数
[劣モジュラ][並進不変]

L = latticeg: L凹  -g: L凸Ｌ凸集合の定義
D⊆Znp∨q 成分ごとの最大値p∧q 成分ごとの最小値

定義[室田]： D がL凸集合
[分配束][並進不変]

L = lattice

L凸関数の例
N: 有限集合， E⊆N×N
guv:RR ((u,v)∈E), 凸関数
はL凸関数ap(a)gda(p(a)－p(d))：凸bd p(d)p(b)cp(c)

Ｍ凸関数の定義
f: ZnR∪{+∞}
定義[室田]： f がM凸関数 (M-EXC)yｊ

M = matroidix

f: M凹  -f: M凸Ｍ凸集合の定義
B⊆Zn
定義： B がM凸集合 (B-EXC)

yｊix

M凸集合＝ポリマトロイド
0-1ベクトルからなるM凸集合＝マトロイドM凸関数の例：多項式行列
 A: n×m 実数行列
 N=列集合, 部分行列 A[I] = (aj | j∈I) (I⊆N)

={I | A[I] は正則}  G-P関係式より次を満たす

はマトロイドM凸関数の例：多項式行列
 A: n×m 行列, 各成分は変数 x を変数とする多項式
 N=列集合, 部分行列 A[I] = (aj | j∈I) (I⊆N)={I | A[I] は正則}
 G-P関係式より次を満たす

f はM凹関数(付値マトロイド)[Dress, 室田]離散凸解析の性質

M凸/L凸関数の性質
 M凸/L凸関数は離散凸関数としてふさわしい性質をもつ
 凸拡張可能性
 局所最適性＝大域的最適性
 （離散）分離定理
 共役性

凸拡張可能性 定義：

f: ZnR が凸拡張可能

定理[室田]：任意のM凸関数とL凸関数は凸拡張可能
注：{0,1}n 上で定義された任意の関数は凸拡張可能

局所最適性＝大域的最適性：
凸関数の場合定理： f:RnR∪{+∞}, 凸,x∈dom fxx の近傍をチェック
最適性のチェックが可能局所最適性＝大域的最適性：
M凸関数の場合
定理[室田]： f:ZnR∪{+∞}, M凸,x∈dom f

第 j 特性（単位）ベクトルx の近傍（n2個の点）をチェック xの最適性のチェックが可能局所最適性＝大域的最適性：
L凸関数の場合
定理[室田]： g:ZnR∪{+∞}, L凸,p∈dom g

集合Xの特性ベクトルpの近傍をチェック pの最適性のチェックが可能•2n個の方向のみ調べれば十分•効率的なチェックが可能

凸関数に対する分離定理
定理：

f(x)

f(x)

g(x)

g(x)

離散凸関数に対する分離：
望ましい主張成り立って欲しい主張：

離散凸関数に対する分離：
難しさ（１）

20

成り立たない例がある

f(x,y)=max{0, x+y} 凸関数
g(x,y)=min{x, y} 凹関数h(x)=(x+y)/215
1050-5-10-10-5-100-50

551010離散凸関数に対する分離：
難しさ（２）
成り立たない例がある
f(x,y)=|x+y-1| 凸関数
g(x,y)=1-|x-y| 凹関数
x, y 整数のとき f(x,y)≧g(x,y)
x=y=1/2のとき f(x,y)=0 < 1 = g(x,y)
5432
10-1-2-32 1.5

1 0.5

0 -0.5-1 -1.5-2-2-1.5-1-0.5

00.5

11.52

M凸/L凸関数に対する分離定理
定理[室田]：マトロイドや劣モジュラ集合関数に対する既存の双対定理
・分離定理の拡張

凸関数の共役性
定義：関数 f: RnR∪{+∞} の共役関数 f*:RnR∪{±∞}

f(x)定義： 凸関数 f は閉  f のエピグラフは閉集合真  dom f は非空, f >ｰ∞定理:• 任意の関数の共役は閉凸関数• f:閉真凸f*: 閉真凸, (f*)*=f- f*(p)傾き p の接線f(x) 閉真凸関数

f*(x)M凸/L凸関数の共役性
定義[室田]：整数値関数 f: ZnZ∪{+∞} の共役関数
f*:ZnZ∪{±∞}
定理[室田]:• 整数値M凸関数 f: ZnZ∪{+∞} の共役関数は整数値L凸関数• 整数値L凸関数 g: ZnZ∪{+∞} の共役関数は整数値M凸関数
f*(x)

f(x)

M凸関数
g*(x)

L凸関数
g(x)

実数空間上の関数への拡張

離散から連続へ：集合の場合
Edmonds (1965)：マトロイドからポリマトロイドへの一般化
 マトロイド(⊆{0,1}n)の凸包の多面体的構造に注目
 ある種の単調劣モジュラ集合関数により記述される
 ポリマトロイド(⊆Rn+)：一般の単調劣モジュラ集合関数により定義される多面体
 マトロイドの（整数性に依存しない）組合せ的性質が一般化できる 劣モジュラ集合関数の理論研究の発展
マトロイド{0,1}n離散ポリマトロイド
Rn+
連続離散から連続へ：関数の場合
 M凸性，L凸性は f: ZnR∪{+∞}に対する概念
 M凸関数，L凸関数の凸閉包はRn上で定義される多面体的凸関数 f: RnR∪{+∞}
 良い組合せ的性質をもつ
 M凸性，L凸性のf: RnR∪{+∞}への拡張
 M凸関数，L凸関数の整数性に依存しない組合せ的性質を明確に
 組合せ的な構造をもつ凸関数の導入
普通の凸関数
f: RnR∪{+∞}
連続M/L凸関数
f: ZnR∪{+∞}
離散連続的M/L凸関数
f: RnR∪{+∞}
連続連続的M凸/L凸関数の定義
 「閉真凸関数＋組合せ的な公理」により定義
 離散的M凸/L凸関数の公理を連続化

 連続的M凸/L凸関数の公理
 普通の凸関数に戻らないように注意が必要！

定義[室田-塩浦]：
閉真凸関数 f: RnR∪{+∞} がM凸関数

連続的M凸/L凸関数の定義
 「閉真凸関数＋組合せ的な公理」により定義
 離散的M凸/L凸関数の公理を連続化

 連続的M凸/L凸関数の公理
 普通の凸関数に戻らないように注意が必要！

定義[室田-塩浦]:
閉真凸関数 g: RnR∪{+∞} がL凸関数
[劣モジュラ][並進不変]

連続的M凸/L凸関数の性質
 連続的M凸/L凸関数は特殊な凸関数
 分離定理は自明に成立

 連続的M凸/L凸関数は良い組合せ構造をもつ
 局所最適性＝大域的最適性
 共役性
 （連続性） などなど 証明には組合せ論だけでなく解析的な手法も必要

局所最適性＝大域的最適性：
連続的M凸関数の場合
定理[室田-塩浦]： f:RnR∪{+∞},M凸, x∈dom fn2個の方向のみ調べれば十分

局所最適性＝大域的最適性：
連続的L凸関数の場合
定理[室田-塩浦]： g:RnR∪{+∞},L凸, p∈dom g•2n個の方向のみ調べれば十分•効率的なチェックが可能連続的M凸/L凸関数の共役性定理[室田-塩浦]:• 連続的M凸関数 f: RnR∪{+∞} の共役関数は連続的L凸関数• 連続的L凸関数 g: RnR∪{+∞} の共役関数は連続的M凸関数

f*(x)

f(x)

M凸関数
g*(x)

L凸関数
g(x)

連続的M凸/L凸関数の連続性
定理[室田-塩浦]:
連続的M凸関数および連続的L凸関数は定義域上で連続※閉真凸関数は連続とは限らない
f(x,y)= y2/x (x>0), 0 (x=y=0), +∞ (o.w.)※連続的M凸/L凸関数の定義域は閉集合とは限らない

幾何への応用

有限距離空間と離散凸性
 有限集合 V 上の距離(metric) d: V×VRd(i, i) = 0, d(i,j)≧0,d(i, j) = 0  i = j,d(i, j) = d(j, i),d(i, j) + d(j, k)≧d(i, k) （三角不等式）
 距離関数とM凸性，L凸性は深い関係をもつ「三角不等式を満たす関数 d: V×VR
 L凸集合  正斉次M凸関数」 が1対1対応
 木距離は特殊なM凹関数（付値マトロイド）三角不等式を満たす関数とL凸集合の1対1対応定理[室田]： d: V×VZ∪{+∞}に対し，三角不等式を満たす関数

1対1L凸集合三角不等式を満たす関数と正斉次M凸関数の1対1対応定理[室田]： d: V×VZ∪{+∞}に対し，三角不等式を満たす関数

1対1正斉次M凸関数

木距離と四点条件

系統樹への応用

定義：d: V×VR は木距離
頂点集合を V とする木 (V, E)と枝長関数 w: ER+により表現可能
d(a,g)
ehb=5+3+6827=1436ad(b,i)
cfg
w(a,c)=5=8+3+6+1
91=18ji

定理： d は木距離四点条件を満たす
d(i,j)+d(k,h)≦max{d(i,k)+d(j,h), d(i,h)+d(j,h)}木距離とM凹関数
定義：d: V×VR は木距離
頂点集合を V とする木 (V, E)と枝長関数 w: ER+により表現可能
定理： d は木距離四点条件を満たす
d(i,j)+d(k,h)≦max{d(i,k)+d(j,h), d(i,h)+d(j,h)}M凹関数の公理(M-EXC)
定理[Dress, Moulton, Terhalle96]:
d は木距離 f(χi+χj) = d(i,j) はM凹関数

木距離とT理論
 T理論(T-theory) 距離関数（とくに木距離）に関する理論 A. Dress らが提唱
 動機：系統樹の再構築
 「タイトスパン」を用いて距離関数を解析

 d: V×VR に関するタイトスパン

多面体的な視点から距離関数を洞察T理論：参考文献
A. Dress, V. Moulton and W. Terhalle, T-theory: an overview,Eur. J. Comb. 17 (1996), 161–175.
 J. R. Isbell, Six theorems about injective metric spaces,Comment. Math. Helv. 39 (1964), 65–76.
 B. Sturmfels and J. Yu, Classification of six-point metrics,
Electron. J. Combin. 11 (2004).
 H.-J. Bandelt and A. W. M. Dress, A canonical decomposition
theory for metrics on a finite set, Adv. Math. 92 (1992), 47–105.
 H. Hirai, Characterization of the distance between subtrees of atree by the associated tight span, Ann. Comb. 10 (2006), 111128.
 H. Hirai, Tight spans of distances and the dual fractionality of
undirected multiflow problems, J. Combinatorial Theory B 99
(2009), 843-868.
 L. L. Larmore and J. A. Oravec, T-theory applications to online
algorithms for the server problem, preprint, arXiv:cs/0611088(2006).
トロピカル幾何
 tropical semiring (=max-plus algebra): tropical linear space [Speyer]:線形空間のトロピカル版
 tropical linear space の組合せ構造を調べる

 tropical Plücker vector を利用Tropical Plücker Vector
定義[Speyer]

p の各成分は，要素数 d のN={1,…,n}の部分集合に対応
tropical PlückerrelationTropical Plücker Vector とM凸関数

f(S) = p(S) で定義される集合関数がM凸関数
 tropical linear space の組合せ構造を調べる際，
離散凸解析の結果が利用可能 (e.g., Rincón)トロピカル幾何: 参考文献
 D. E. Speyer, “Tropical linear space”, SIAM J. Discrete

Math. 22 (2008) 1527-1558.
 F. Rincón, “Isotropical linear space and valuateddelta-matroids”, preprint, arXiv:1004.4950 (2010).
 S. Herrmann, A. Jensen, M. Joswig, B. Sturmfels,“How to draw tropical planes”, Electronic J.
Combinatorics 16 (2009) R6.
 P. Brändán, “Discrete concavity and the half-planeproperty”, preprint, arXiv:0904.0363 (2009).

おわりに今後の研究の方向性
 理論

M凸性，L凸性の構造に対するより深い理解 より広いクラスの関数へ理論を拡張 アルゴリズム

効率的に解ける問題に対し，高速アルゴリズムの構築
 計算困難な問題に対し，高性能近似アルゴリズムの提案
 応用

応用の範囲を広げる（現在：オペレーションズ･リサーチ，制御，ゲーム理論，数理経済，数学など）
 離散凸解析の成果を応用分野へ適用
 応用分野からのフィードバック局所最適性＝大域的最適性：
M凸関数の場合
定理： f:ZnR∪{+∞}, M凸,x∈dom f

第 j 特性（単位）ベクトルx の近傍をチェック xの最適性のチェックが可能
関数値を n2 回評価すればOK

局所最適性＝大域的最適性：
L凸関数の場合
定理： g:ZnR∪{+∞}, L凸,pの近傍をチェック pの最適性のチェックが可能

p∈dom g

集合Xの特性ベクトルp の近傍チェックは 2n 回の関数値評価が必要？ --- No!
• pの近傍のチェックは劣モジュラ集合関数最小化に帰着可能• 劣モジュラ集合関数最小化は n の多項式時間で解ける 近傍チェックは n の多項式時間で可能