劣モジュラ最適化

【れつもじゅらさいてきか (submodular optimization)】

概要

劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に 対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.

詳説

　劣モジュラ最適化 (submodular optimization) とは, 劣モジュラ関数 (submodular function) を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ最適化は, 非線型最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.

　有限集合 $N\,$ の部分集合族 ${\mathcal {D}}\subseteq 2^{N}\,$ が, $\emptyset \,$ と $N\,$ を共に含み, 任意の $X,Y\in {\mathcal {D}}\,$ に対して $X\cup Y,X\cap Y\in {\mathcal {D}}\,$ を満たすものとする. このとき, ${\mathcal {D}}\,$ は分配束をなす. 関数 $f:{\mathcal {D}}\to \mathbf {R} \,$ が, 任意の $X,Y\in {\mathcal {D}}\,$ に対して

$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)\,$

を満たすとき, $f\,$ は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, $f\,$ をモジュラ関数という. 分配束 ${\mathcal {D}}\,$ と劣モジュラ関数 $f\,$ の組 $({\mathcal {D}},f)\,$ は, $f(\emptyset )=0\,$ のとき, 劣モジュラシステム (submodular system) と呼ばれる. さらに, ${\mathcal {D}}=2^{N}\,$ であり, $f\,$ が単調性を有するとき, すなわち任意の $X,Y\subseteq N\,$ に対して $X\subseteq Y\Rightarrow f(X)\leq f(Y)\,$ が成り立つとき, $(N,f)\,$ をポリマトロイド (polymatroid)という.

　オペレーションズ・リサーチにおいて重要な劣モジュラ関数の代表的な例を以下に挙げる.

カット容量関数　有向グラフ $G=(N,A)\,$ において, 各枝 $a\in A\,$ に非負の容量 $c(a)\,$ が与えられているとき, $\textstyle \kappa (X)=\sum \{c(a)\mid a\in \Delta ^{+}X\}\,$ で定義される容量関数 $\kappa :2^{N}\to \mathbf {R} \,$ は, 劣モジュラ関数となる. ここで, $\Delta ^{+}X\,$ は, $X\subseteq N\,$ から出る枝の集合を表す.

マトロイド階数関数　マトロイド ${\mathcal {M}}=(N,{\mathcal {I}})\,$ において, 階数関数 $\rho :2^{N}\to \mathbf {Z} \,$ を $\rho (X)=\max\{|I|\mid I\subseteq X,\,I\in {\mathcal {I}}\}\,$ で定めると, $(N,\rho )\,$ はポリマトロイドとなる.

エントロピー関数　有限アルファベットの離散確率変数の集合 $N\,$ に関して, 空でない部分集合 $X\subseteq N\,$ のエントロピーを $\eta (X)\,$ と書き, $\eta (\emptyset )=0\,$ と定めると, $(N,\eta )\,$ はポリマトロイドとなる.

　有限集合 $N\,$ 上の実数値関数全体のなす線型空間を $\mathbf {R} ^{N}\,$ と表す. ベクトル $x\in \mathbf {R} ^{N}\,$ は, 部分集合 $X\subseteq N\,$ に対して $\textstyle x(X)=\sum \{x(i)\mid i\in X\}\,$ と定義することによって, $x(\emptyset )=0\,$ であるようなモジュラ関数 $x\,$ と同一視される.劣モジュラシステム $({\mathcal {D}},f)\,$ は, $\mathbf {R} ^{N}\,$ 中の基多面体　(base polyhedron)

${\mbox{B}}(f)=\{x\mid x\in \mathbf {R} ^{N},\;x(N)=f(N),\;\forall X\in {\mathcal {D}}:x(X)\leq f(X)\}\,$

を定める. 基 $x\in {\mbox{B}}(f)\,$ と相異なる $i,j\in N\,$ に対して,

${\tilde {c}}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in {\mathcal {D}},j\notin X\}\,$

で定義される量を交換容量と呼ぶ.

　基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, 組合せ的な多項式時間アルゴリズムの開発が望まれている. (最近, Iwata-Fleischer-Fujishige[6]とSchrijver[7]によって独立に解決された. )

　有向グラフ $G=(N,A)\,$ と, $f(N)=0\,$ を満たす $N\,$ 上の劣モジュラシステム $({\mathcal {D}},f)\,$ を考える. 各枝 $a\,$ の始点を $\partial ^{+}a\,$, 終点を $\partial ^{-}a\,$ と書き, $X\subseteq N\,$ から出る枝の集合を $\Delta ^{+}X\,$, 入る枝の集合を $\Delta ^{-}X\,$ と表す. 任意の $\varphi \in \mathbf {R} ^{A}\,$ に対して, 境界 $\partial \varphi \in \mathbf {R} ^{N}\,$ を $\partial \varphi (X)=\varphi (\Delta ^{+}X)-\varphi (\Delta ^{-}X)\,$ で定める. 劣モジュラフロー問題 (submodular flow problem) とは, 枝流量の上下限 ${\bar {c}},{\underline {c}}\in \mathbf {R} ^{A}\,$ と費用 $d\in \mathbf {R} ^{A}\,$ が与えられたとき,

$\min\{\sum _{a\in A}d(a)\varphi (a)\mid \partial \varphi \in {\mbox{B}}(f),\;\forall a\in A:{\underline {c}}(a)\leq \varphi (a)\leq {\bar {c}}(a)\}\,$

を求める問題である [1] . 特に, $f\,$ がモジュラ関数の場合には, 最小費用フロー問題となることに注意する.

　劣モジュラフロー問題は, 任意の $X\in {\mathcal {D}}\,$ に対して${\underline {c}}(\Delta ^{+}X)-{\bar {c}}(\Delta ^{-}X)\leq f(X)\,$ が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, ${\bar {c}},{\underline {c}},f\,$ が整数値関数であれば, 整数実行可能解が存在する.

　実行可能解 $\varphi \,$ は, 以下の条件を満たす $p\in \mathbf {R} ^{N}\,$ が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝 $a\in A\,$ に対して$d_{p}(a)=d(a)+p(\partial ^{+}a)-p(\partial ^{-}a)\,$ と定める.

• 任意の $a\in A\,$ に対して, $d_{p}(a)>0\Rightarrow \varphi (a)={\underline {c}}(a)\,\,$, および$d_{p}(a)<0\Rightarrow \varphi (a)={\bar {c}}(a)\,$.

• 任意の相異なる $i,j\in N\,$ に対して, $p(j)<p(i)\Rightarrow {\tilde {c}}(\partial \varphi ,i,j)=0\,$.

さらに, $d\,$ が整数値関数の場合には, $p\,$ を整数値関数に限ることができる.

　最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム $({\mathcal {D}},f)\,$ に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない.

　劣モジュラ関数 $f\,$ の最小値を達成する $X\in {\mathcal {D}}\,$ の全体は, ${\mathcal {D}}\,$ の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は $N\,$ の適当な部分集合への分割と各成分間の半順序関係によって表すことができる. この原理に基づいて劣モジュラ関数で記述された離散システムを分解する手法を総称して基本分割 (principal partition) と呼ぶ.

---

参考文献

[1] J. Edmonds and R. Giles, "A min-max relation for submodular functions on graphs," in Studies in Integer Programming}, P. L. Hammer, E. L. Johnson, and B. H. Korte, eds., North-Holland, 185-204, 1977.

[2] S. Fujishige, Submodular Functions and Optimization, 2nd ed., Elsevier, 2005.

[3] M. Grötschel, L. Lov\'asz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.

[4] 伊理正夫, 藤重悟, 大山逹雄, 『グラフ・ネットワーク・マトロイド』, 産業図書, 1986.

[5] 岩田覚, 「劣モジュラ流問題」, 藤重悟 編　『離散構造とアルゴリズム Ⅵ』, 近代科学社, 第4章，127-170, 1999.

[6] S.Iwata, L.Fleischer and S.Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of ACM 48 (2001) , 761--777.

[7] A.Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Ser. B, 80 (2000) , 346--355.