離散凸解析とは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

離散凸解析

読み方：りさんとつかいせき
【英】：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\,$ に対してその特性ベクトルを $\chi_{i} \ (\in \{ 0,1 \}^{n})\,$ と表わす，すなわち

$\chi_i(v) = \left\{ \begin{array}{ll} 1 & (v=i) \\ 0 & (v \neq 1) \end{array} \right.\,$

とする．ベクトル $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\,$ は整基多面体(に含まれる整数格子点)である ([3, 4]参照)．

　関数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} \,$

と定義する．ここで， $\textstyle \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凸関数の具体的な例，２次のM凸関数，L凸関数の特徴付け，M凸性，L凸性について閉じた基本的な演算については[4, 5, 6] を参照されたい．特に[5]では，線形代数，組合せ論，距離空間，確率論，オペレーションズリサーチなど，いろいろな文脈で離散凸解析が現れることが紹介されている．　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.

「OR事典」の他の用語

グラフ･ネットワーク：

辺連結度連結度連結度増大問題配送計画問題階数関数離散凸解析離散分離定理

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

凸解析

(離散凸解析から転送)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/24 04:57 UTC 版)

この項目の現在の内容は百科事典というよりは辞書に適しています。 百科事典的な記事に加筆・修正するか、姉妹プロジェクトのウィクショナリーへの移動を検討してください（ウィクショナリーへの移動方法）。（2018年12月）

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）

翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。
万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
翻訳後、{{翻訳告知|en|Convex analysis|…}}をノートに追加することもできます。
Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

凸解析 (とつかいせき) は、凸関数および凸集合を研究する数学の一分野である。最適化理論の領域の中の凸最小化によく応用される。