《離散凸解析》

【りさんとつかいせき (discrete convex analysis) 】

　離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を，凸解析 ([6]) とマトロイド理論 ([1, 7, 8]) の両方の視点から考察する方法論を，離散凸解析 (discrete convex analysis) ([4, 5])と呼ぶ．より一般的には，解析的な視点と組合せ論的な視点の両方から「組合せ論的な凸性」という構造を考察する方法論を指す．離散最適化 ([2])，システム解析 ([3])，数理経済学などへの応用がある．

　整数格子点上で定義され整数値をとる関数$f:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{\pm \infty \}\,$を考える($V\,$は有限集合である)．${\rm {dom\,}}f=\{x\in {\mathbf {Z} }^{V}\mid -\infty <f(x)<+\infty \}\,$を$f\,$の実効定義域と呼び，以下では，${\rm {dom\,}}f\not =\emptyset \,$であるような関数だけを考える．$i\in V\,$に対してその特性ベクトルを$\chi _{i}\ (\in \{0,1\}^{V})\,$ と表わす．ベクトル$x\in {\mathbf {Z} }^{V}\,$に対して，${{\rm {supp}}^{+}}(x)=\{i\in V\mid x_{i}>0\}\,$, ${{\rm {supp}}^{-}}(x)=\{i\in V\mid x_{i}<0\}\,$とおく．関数$f:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{+\infty \}\,$が交換公理:

任意の $x,y\in {\rm {dom\,}}f\,$ と任意の $i\in {{\rm {supp}}^{+}}(x-y)\,$ に対して, ある $j\in {{\rm {supp}}^{-}}(x-y)\,$ が存在して

$f(x)+f(y)\geq f(x-\chi _{i}+\chi _{j})+f(y+\chi _{i}-\chi _{j})\,$

を満たすとき，M凸関数 (M-convex function) という．M凸関数$f\,$の実効定義域${\rm {dom\,}}f\,$は整基多面体(に含まれる整数格子点)である．

　関数g:${\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{+\infty \}\,$が2条件: 　

$g(p)+g(q)\geq g(p\vee q)+g(p\wedge q)\qquad (p,q\in {\mathbf {Z} }^{V}),\,$

$\exists r\in {\mathbf {Z} },\forall p\in {\mathbf {Z} }^{V}:\ g(p+{\mathbf {1} })=g(p)+r,\,$

を満たすとき，L凸関数 (L-convex function) という．ここで，$p\vee q,p\wedge q\,$は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，$(p\vee q)_{i}=\max(p_{i},q_{i})\,$, $(p\wedge q)_{i}=\min(p_{i},q_{i}))\,$を表し，${\mathbf {1} }=(1,1,\ldots ,1)\in {\mathbf {Z} }^{V}\,$である．L凸関数$g\,$の実効定義域${\rm {dom\,}}g\,$は$\vee \,$, $\wedge \,$に関して${\mathbf {Z} }^{V}\,$の部分束を成す．また，正斉次L凸関数は，劣モジュラ集合関数と同一視することができる．

　一般に関数$h:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{\pm \infty \}\,$ の凸共役$h^{\bullet }\,$，凹共役$h^{\circ }\,$を

${\begin{array}{lll}h^{\bullet }(p)&=&\sup\{\langle p,x\rangle -h(x)\mid x\in {\mathbf {Z} }^{V}\}\qquad (p\in {\mathbf {Z} }^{V}),\\h^{\circ }(p)&=&\inf\{\langle p,x\rangle -h(x)\mid x\in {\mathbf {Z} }^{V}\}\qquad (p\in {\mathbf {Z} }^{V})\end{array}}\,$

と定義する．ここで，$\langle p,x\rangle =\sum _{i\in V}p_{i}x_{i}\,$である．この対応$h\mapsto h^{\bullet }\,$, $h\mapsto h^{\circ }\,$ を(凸，凹)離散フェンシェル・ルジャンドル(Fenchel-Legendre)変換と呼ぶ．M凸関数とL凸関数は離散フェンシェル・ルジャンドル変換に関して共役関係にあり，対応$f\mapsto f^{\bullet }\,$, $g\mapsto g^{\bullet }\,$はM凸関数$f\,$とL凸関数$g\,$の間の１対１対応を与える．すなわち，M凸関数$f\,$とL凸関数$g\,$に対して，$f^{\bullet }\,$はL凸関数, $g^{\bullet }\,$はM凸関数で，$(f^{\bullet })^{\bullet }=f\,$, $(g^{\bullet })^{\bullet }=g\,$が成り立つ(共役性定理)．

　M凸関数やL凸関数に対して，離散分離定理 (discrete separation theorem) やフェンシェル型双対定理 (Fenchel-type duality theorem) に象徴されるような離散双対性が成り立つ．

　M凸関数に関する離散分離定理(M分離定理)を述べる:

[M分離定理] $f:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{+\infty \}\,$ をM凸関数，$g:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{-\infty \}\,$をM凹関数とし, ${\rm {dom\,}}f\cap {\rm {dom\,}}g\not =\emptyset \,$または${\rm {dom\,}}f^{\bullet }\cap {\rm {dom\,}}g^{\circ }\not =\emptyset \,$であると仮定する．このとき, $f(x)\geq g(x)\,$ $(\forall \ x\in {\mathbf {Z} }^{V})\,$ならば, ある$\alpha \in {\mathbf {Z} }\,$, $p\in {\mathbf {Z} }^{V}\,$が存在して

$f(x)\geq \alpha +\langle p,x\rangle \geq g(x)\qquad (\forall \ x\in {\mathbf {Z} }^{V})\,$

　が成り立つ($g\,$がM凹関数とは$-g\,$がM凸関数のことである)．

ここで，$p\,$が整数ベクトルに選べることが離散性の反映である．上の主張で，$f\,$をL凸関数，$g\,$をL凹関数に置き換えたものも成立する(L分離定理)．L分離定理は，その特殊ケースとして，劣モジュラ集合関数に関するA. Frankの離散分離定理 ([1] 参照) を含んでいる．

　M分離定理とL分離定理は互いに共役の関係にあるが，次に述べるフェンシェル(フェンケル)型双対定理は自己共役の形になっている．

[フェンシェル型双対定理] $f:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{+\infty \}\,$ をM凸関数，$g:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{-\infty \}\,$をM凹関数とし, ${\rm {dom\,}}f\cap {\rm {dom\,}}g\not =\emptyset \,$または${\rm {dom\,}}f^{\bullet }\cap {\rm {dom\,}}g^{\circ }\not =\emptyset \,$であると仮定する．このとき,

$\inf\{f(x)-g(x)\mid x\in {\mathbf {Z} }^{V}\}=\sup\{g^{\circ }(p)-f^{\bullet }(p)\mid p\in {\mathbf {Z} }^{V}\}\,$

　が成り立つ．さらに，この両辺が有限値なら，$\inf \,$を達成する$x\in {\rm {dom\,}}f\cap {\rm {dom\,}}g$と$\sup \,$を達成する$p\in {\rm {dom\,}}f^{\bullet }\cap {\rm {dom\,}}g^{\circ }\,$が存在する．

上の定理は，非線形整数計画に関する強双対性を主張しており，その本質的な部分は，$\inf \,$と$\sup \,$をとる範囲をそれぞれ整数ベクトルに限ってよいという主張にある．

　M凸関数，L凸関数に関する種々の問題に対して効率的なアルゴリズムが開発されている．これに関しては [5] の参考文献を参照されたい．

---

参考文献

[1] S. Fujishige, Submodular Functions and Optimization, North-Holland, 1991.

[2] N. Katoh and T. Ibaraki, "Resource allocation problems," in Handbook of Combinatorial Optimization, Vol.2, D. -Z. Du and P. M. Pardalos, eds., Kluwer, 159-260, 1998.

[3] 室田一雄, 「離散凸解析」, 『応用数理』，6 (1996), 259-269.

[4] K. Murota, Discrete convex analysis, Mathematical Programming, 83 (1998), 313-371.

[5] 室田一雄,「離散凸解析」, 藤重 悟 編『離散構造とアルゴリズムV』, 近代科学社, 第2章，51-100, 1998.

[6] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

[7] D. J. A. Welsh, Matroid Theory，Academic Press, 1976.

[8] N. White, ed., Theory of Matroids, Cambridge University Press, 1986.