《離散凸解析》

【りさんとつかいせき (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: {\bf Z}\sp{V} \to {\bf Z} \cup \{ \pm\infty \}} $を考える($V$は有限集合である)．$構文解析に失敗 (不明な関数「\sp」): {\displaystyle {{\rm dom\,}} f = \{ x \in {\bf Z}\sp{V} \mid -\infty < f(x) < +\infty \}} $を$$f$$の実効定義域と呼び，以下では，$${\rm {dom\,}}f\not =\emptyset$$であるような関数だけを考える．$$i\in V$$に対してその特性ベクトルを$構文解析に失敗 (不明な関数「\sp」): {\displaystyle \chi_{i} \ (\in \{ 0,1 \}\sp{V})} $ と表わす．ベクトル$構文解析に失敗 (不明な関数「\sp」): {\displaystyle x \in {\bf Z}\sp{V}} $に対して，$構文解析に失敗 (不明な関数「\sp」): {\displaystyle {{\rm supp}\sp{+}}(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}\sp{-}}(x) = \{ i \in V \mid x_{i} < 0 \}} $とおく．関数$構文解析に失敗 (不明な関数「\sp」): {\displaystyle f: {\bf Z}\sp{V} \to {\bf Z} \cup \{ +\infty \}} $が交換公理:

任意の $$x,y\in {\rm {dom\,}}f$$ と任意の $構文解析に失敗 (不明な関数「\sp」): {\displaystyle i \in {{\rm supp}\sp{+}}(x-y)} $ に対して, ある $構文解析に失敗 (不明な関数「\sp」): {\displaystyle j \in {{\rm supp}\sp{-}}(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:構文解析に失敗 (不明な関数「\sp」): {\displaystyle {\bf Z}\sp{V} \to {\bf Z} \cup \{ +\infty \}} $が2条件: 　

構文解析に失敗 (不明な関数「\sp」): {\displaystyle g(p) + g(q) \geq g(p \vee q) + g(p \wedge q) \qquad ( p, q \in {\bf Z}\sp{V}) ,}

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \exists r \in {\bf Z}, \forall p \in {\bf Z}\sp{V}: \ g(p+{\bf 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})\$)$を表し，$構文解析に失敗 (不明な関数「\sp」): {\displaystyle {\bf 1}=(1,1,\ldots,1) \in {\bf Z}\sp{V}} $である．L凸関数$$g$$の実効定義域$${\rm {dom\,}}g$$は$$\vee$$, $$\wedge$$に関して$構文解析に失敗 (不明な関数「\sp」): {\displaystyle {\bf Z}\sp{V}} $の部分束を成す．また，正斉次L凸関数は，劣モジュラ集合関数と同一視することができる．

　一般に関数$構文解析に失敗 (不明な関数「\sp」): {\displaystyle h: {\bf Z}\sp{V} \to {\bf Z} \cup \{ \pm\infty \}} $ の凸共役$構文解析に失敗 (不明な関数「\sp」): {\displaystyle h\sp{\bullet}} $，凹共役$構文解析に失敗 (不明な関数「\sp」): {\displaystyle h\sp{\circ}} $を

構文解析に失敗 (不明な関数「\sp」): {\displaystyle \begin{array}{lll} h\sp{\bullet}(p) &=& \sup\{ \langle p, x \rangle - h(x) \mid x \in {\bf Z}\sp{V} \} \qquad ( p \in {\bf Z}\sp{V}) , \\ h\sp{\circ}(p) &=& \inf\{ \langle p, x \rangle - h(x) \mid x \in {\bf Z}\sp{V} \} \qquad ( p \in {\bf Z}\sp{V}) \end{array} }

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

構文解析に失敗 (不明な関数「\sp」): {\displaystyle f(x) \geq \alpha + \langle p, x \rangle \geq g(x) \qquad (\forall \ x \in {\bf Z}\sp{V})}

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

ここで，$$p$$が整数ベクトルに選べることが離散性の反映である．上の主張で，$$f\$$をL凸関数，$$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: {\bf Z}\sp{V} \to {\bf Z} \cup \{ +\infty \}} $ をM凸関数，$構文解析に失敗 (不明な関数「\sp」): {\displaystyle g: {\bf Z}\sp{V} \to {\bf 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\sp{\bullet} \cap {{\rm dom\,}} g\sp{\circ} \not= \emptyset} $であると仮定する．このとき,

構文解析に失敗 (不明な関数「\sp」): {\displaystyle \inf\{ f(x) - g(x) \mid x \in {\bf Z}\sp{V} \} = \sup\{ g\sp{\circ}(p) - f\sp{\bullet}(p) \mid p \in {\bf Z}\sp{V} \}}

　が成り立つ．さらに，この両辺が有限値なら，$$\inf$$を達成する$$x\in {\rm {dom\,}}f\cap {\rm {dom\,}}g$$と$$\sup$$を達成する$構文解析に失敗 (不明な関数「\sp」): {\displaystyle p \in {{\rm dom\,}} f\sp{\bullet} \cap {{\rm dom\,}} g\sp{\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.