離散凸解析

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

概要

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

詳説

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

　整数格子点上で定義され整数値をとる関数$f:{\mathbf {Z} }^{n}\to {\mathbf {Z} }\cup \{\pm \infty \}\,$を考える．${\rm {dom\,}}f=\{x\in {\mathbf {Z} }^{n}\mid -\infty <f(x)<+\infty \}\,$を$f\,$の実効定義域と呼び，以下では，${\rm {dom\,}}f\not =\emptyset \,$であるような関数だけを考える．$i\in n\,$に対してその特性ベクトルを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \chi_{i} \ (\in \{ 0,1 \}^{n})\, } と表わす，すなわち構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \chi_i(v) = {1 (v=i) 0 (v \neq 1)} とする．．ベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x \in {\mathbf Z}^{V}\, } に対して，${{\rm {supp}}^{+}}(x)=\{i\in V\mid x_{i}>0\}\,$, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, } とおく．関数$f:{\mathbf {Z} }^{V}\to {\mathbf {Z} }\cup \{+\infty \}\,$が交換公理:

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

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

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

と定義する．ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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凸関数は離散フェンシェル・ルジャンドル変換に関して共役関係にあり，対応$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凸関数構文解析に失敗 (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\, } の間の１対１対応を与える．すなわち，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凸関数，構文解析に失敗 (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凹関数とし, ${\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\, } であると仮定する．このとき, $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凹関数とは構文解析に失敗 (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 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\, } または${\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\, } を達成する$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凸関数に関する種々の問題に対して効率的なアルゴリズムが開発されている．これに関しては [4, 6] を参照されたい．

---

参考文献

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

[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] K. Murota, "Discrete convex analysis", Mathematical Programming, 83 (1998), 313-371.

[4] 室田一雄, 『離散凸解析』, 共立出版，2001.

[5] 室田一雄, 『離散凸解析の考え方』, 共立出版，2007.

[6] K.Murota, Discrete Convex Analysis, SIAM, 2003.

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

[8] A.Tamura, "Applications of discrete convex analysis to mathmatical economics", Publ. RIMS, 40 (2004) , 1015-1037.

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

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