《離散凸解析》

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

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

　整数格子点上で定義され整数値をとる関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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\,$ と任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i \in {{\rm supp}^{+}}(x-y)\, } に対して, ある 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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凸関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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) という．ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p \vee q, p \wedge q\, } は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (p \vee q)_{i} = \max(p_{i}, q_{i})\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (p \wedge q)_{i} = \min(p_{i}, q_{i}))\, } を表し，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathbf 1}=(1,1,\ldots,1) \in {\mathbf Z}^{V}\, } である．L凸関数$g\,$の実効定義域${\rm {dom\,}}g\,$は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \vee\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \wedge\, } に関して${\mathbf {Z} }^{V}\,$の部分束を成す．また，正斉次L凸関数は，劣モジュラ集合関数と同一視することができる．

　一般に関数$h:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{\pm \infty \}\,$ の凸共役構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h^{\bullet}\, } ，凹共役構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h^{\circ}\, } を

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} \, }

と定義する．ここで，$\textstyle \langle p,x\rangle =\sum _{i\in V}p_{i}x_{i}\,$である．この対応構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h \mapsto h^{\bullet}\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h \mapsto h^{\circ}\, } を(凸，凹)離散フェンシェル・ルジャンドル(Fenchel-Legendre)変換と呼ぶ．M凸関数とL凸関数は離散フェンシェル・ルジャンドル変換に関して共役関係にあり，対応構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f \mapsto f^{\bullet}\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g \mapsto g^{\bullet}\, } はM凸関数$f\,$とL凸関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } の間の１対１対応を与える．すなわち，M凸関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } とL凸関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } に対して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^{\bullet}\, } はL凸関数, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g^{\bullet}\, } はM凸関数で，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (f^{\bullet})^{\bullet}=f\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (g^{\bullet})^{\bullet}=g\, } が成り立つ(共役性定理)．

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

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

[M分離定理] 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, } をM凸関数，$g:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{-\infty \}\,$をM凹関数とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {{\rm dom\,}} f \cap {{\rm dom\,}} g \not= \emptyset\, } または構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {{\rm dom\,}} f^{\bullet} \cap {{\rm dom\,}} g^{\circ} \not= \emptyset\, } であると仮定する．このとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) \geq g(x)\, } 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\forall \ x \in {\mathbf Z}^{V})\, } ならば, ある構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha \in {\mathbf Z}\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p \in {\mathbf Z}^{V}\, } が存在して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) \geq \alpha + \langle p, x \rangle \geq g(x) \qquad (\forall \ x \in {\mathbf Z}^{V})\, }

　が成り立つ(構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } がM凹関数とは$-g\,$がM凸関数のことである)．

ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p\, } が整数ベクトルに選べることが離散性の反映である．上の主張で，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } をL凸関数，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } をL凹関数に置き換えたものも成立する(L分離定理)．L分離定理は，その特殊ケースとして，劣モジュラ集合関数に関するA. Frankの離散分離定理 ([1] 参照) を含んでいる．

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

[フェンシェル型双対定理] 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, } をM凸関数，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ -\infty \}\, } をM凹関数とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {{\rm dom\,}} f \cap {{\rm dom\,}} g \not= \emptyset\, } または構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {{\rm dom\,}} f^{\bullet} \cap {{\rm dom\,}} g^{\circ} \not= \emptyset\, } であると仮定する．このとき,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \inf\{ f(x) - g(x) \mid x \in {\mathbf Z}^{V} \} = \sup\{ g^{\circ}(p) - f^{\bullet}(p) \mid p \in {\mathbf Z}^{V} \}\, }

　が成り立つ．さらに，この両辺が有限値なら，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \inf\, } を達成する構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x \in {{\rm dom\,}} f \cap {{\rm dom\,}} g} と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sup\, } を達成する構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p \in {{\rm dom\,}} f^{\bullet} \cap {{\rm dom\,}} g^{\circ}\, } が存在する．

上の定理は，非線形整数計画に関する強双対性を主張しており，その本質的な部分は，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \inf\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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.