離散凸解析 - 版の履歴

2008年8月6日 (水) 04:33にImahoriによる

2008-08-06T04:33:42Z

2008年8月6日 (水) 04:32にImahoriによる

2008-08-06T04:32:03Z

2008年8月6日 (水) 04:27にImahoriによる

2008-08-06T04:27:29Z

2008年8月6日 (水) 04:26にImahoriによる

2008-08-06T04:26:02Z

2008年8月6日 (水) 04:23にImahoriによる

2008-08-06T04:23:24Z

2008年8月6日 (水) 04:20にImahoriによる

2008-08-06T04:20:40Z

Imahori: 基礎編と用語編のマージ

2008-03-13T14:12:19Z

基礎編と用語編のマージ

2007年8月8日 (水) 12:02にKanda.kによる

2007-08-08T12:02:27Z

Orsjwiki: "離散凸解析" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T01:07:51Z

"離散凸解析" を保護しました。 [edit=sysop:move=sysop]

122.17.2.240: 新しいページ: ''''【りさんとつかいせき (discrete convex analysis)】''' 離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を, 凸解析...'

2007-07-09T09:13:14Z

新しいページ: ''''【りさんとつかいせき (discrete convex analysis)】''' 離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を, 凸解析...'

新規ページ

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

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

@@ 49行目: / 49行目: @@
-を満たすとき，[[L凸関数]] (L-convex function) という．ここで，<math>p \vee q, p \wedge q\, </math>は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，<math>(p \vee q)_{i} = \max(p_{i}, q_{i})\, </math>, <math>(p \wedge q)_{i} = \min(p_{i}, q_{i}))\, </math>を表し，<math>{\mathbf 1}=(1,1,\ldots,1) \in {\mathbf Z}^{V}\, </math>である．L凸関数<math>g\, </math>の実効定義域<math>{{\rm dom\,}} g\, </math>は<math>\vee\, </math>, <math>\wedge\, </math>に関して<math>{\mathbf Z}^{V}\, </math>の部分束を成す．また，正斉次L凸関数は，[[劣モジュラ集合関数|劣モジュラ関数]]と同一視することができる．
+を満たすとき，[[L凸関数]] (L-convex function) という．ここで，<math>p \vee q, p \wedge q\, </math>は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，<math>(p \vee q)_{i} = \max(p_{i}, q_{i})\, </math>, <math>(p \wedge q)_{i} = \min(p_{i}, q_{i}))\, </math>を表し，<math>{\mathbf 1}=(1,1,\ldots,1) \in {\mathbf Z}^{V}\, </math>である．L凸関数<math>g\, </math>の実効定義域<math>{{\rm dom\,}} g\, </math>は<math>\vee\, </math>, <math>\wedge\, </math>に関して<math>{\mathbf Z}^{V}\, </math>の部分束を成す．また，正斉次L凸関数は，[[劣モジュラ関数|劣モジュラ集合関数]]と同一視することができる．
 　一般に関数<math>h: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math> の凸共役<math>h^{\bullet}\, </math>，凹共役<math>h^{\circ}\, </math>を
@@ 103行目: / 103行目: @@
 上の定理は，非線形整数計画に関する強双対性を主張しており，その本質的な部分は，<math>\inf\, </math>と<math>\sup\, </math>をとる範囲をそれぞれ整数ベクトルに限ってよいという主張にある．
 　M凸関数，L凸関数に関する種々の問題に対して効率的なアルゴリズムが開発されている．これに関しては [4, 6] を参照されたい．

@@ 30行目: / 30行目: @@
-を満たすとき，[[M凸関数]] (M-convex function) という．M凸関数<math>f\, </math>の実効定義域<math>{{\rm dom\,}} f\, </math>は整基多面体(に含まれる整数格子点)である．
+を満たすとき，[[M凸関数]] (M-convex function) という．M凸関数<math>f\, </math>の実効定義域<math>{{\rm dom\,}} f\, </math>は整基多面体(に含まれる整数格子点)である ([3, 4]参照)．
 　関数g:<math> {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が2条件:
@@ 43行目: / 43行目: @@
 <tr>
 <td><math>\exists r \in {\mathbf Z}, \forall p \in {\mathbf Z}^{V}: \
-  g(p+{\mathbf 1}) = g(p) + r  ,\, </math>
+  g(p+{\mathbf 1}) = g(p) + r  </math>
 </td>
 </tr>
@@ 49行目: / 49行目: @@
-を満たすとき，[[L凸関数]] (L-convex function) という．ここで，<math>p \vee q, p \wedge q\, </math>は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，<math>(p \vee q)_{i} = \max(p_{i}, q_{i})\, </math>, <math>(p \wedge q)_{i} = \min(p_{i}, q_{i}))\, </math>を表し，<math>{\mathbf 1}=(1,1,\ldots,1) \in {\mathbf Z}^{V}\, </math>である．L凸関数<math>g\, </math>の実効定義域<math>{{\rm dom\,}} g\, </math>は<math>\vee\, </math>, <math>\wedge\, </math>に関して<math>{\mathbf Z}^{V}\, </math>の部分束を成す．また，正斉次L凸関数は，劣モジュラ集合関数と同一視することができる．
+を満たすとき，[[L凸関数]] (L-convex function) という．ここで，<math>p \vee q, p \wedge q\, </math>は，それぞれ，成分毎に最大値, 最小値をとって得られるベクトル(すなわち，<math>(p \vee q)_{i} = \max(p_{i}, q_{i})\, </math>, <math>(p \wedge q)_{i} = \min(p_{i}, q_{i}))\, </math>を表し，<math>{\mathbf 1}=(1,1,\ldots,1) \in {\mathbf Z}^{V}\, </math>である．L凸関数<math>g\, </math>の実効定義域<math>{{\rm dom\,}} g\, </math>は<math>\vee\, </math>, <math>\wedge\, </math>に関して<math>{\mathbf Z}^{V}\, </math>の部分束を成す．また，正斉次L凸関数は，[[劣モジュラ集合関数|劣モジュラ関数]]と同一視することができる．
 　一般に関数<math>h: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math> の凸共役<math>h^{\bullet}\, </math>，凹共役<math>h^{\circ}\, </math>を

@@ 8行目: / 8行目: @@
 ネットワークフローとの密接な関係も知られている[4, 5, 6]．
-　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{n} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in n\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{n})\, </math> と表わす，すなわち<math>\chi_i(v) = \left\{ \begin{array}{ll}
+　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{n} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in n\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{n})\, </math> と表わす，すなわち
 & (v=i) \\ 0 & (v \neq 1) \end{array} \right.\, </math>
-とする．．ベクトル<math>x \in {\mathbf Z}^{V}\, </math>に対して，<math>{{\rm supp}^{+}}(x) = \{ i \in V \mid x_{i} > 0 \}\, </math>, <math>{{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, </math>とおく．関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が交換公理:
+</center>
 <table align="center">

@@ 8行目: / 8行目: @@
 ネットワークフローとの密接な関係も知られている[4, 5, 6]．
-　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{n} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in n\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{n})\, </math> と表わす，すなわち<math>\chi_i(v) = {1  (v=i)
+　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{n} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in n\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{n})\, </math> と表わす，すなわち<math>\chi_i(v) = \left\{ \begin{array}{ll}
-(v \neq 1)</math>
+& (v=i) \\ 0 & (v \neq 1) \end{array} \right.\, </math>
 とする．．ベクトル<math>x \in {\mathbf Z}^{V}\, </math>に対して，<math>{{\rm supp}^{+}}(x) = \{ i \in V \mid x_{i} > 0 \}\, </math>, <math>{{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, </math>とおく．関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が交換公理:

@@ 8行目: / 8行目: @@
 ネットワークフローとの密接な関係も知られている[4, 5, 6]．
-　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{V} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in V\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{V})\, </math> と表わす．ベクトル<math>x \in {\mathbf Z}^{V}\, </math>に対して，<math>{{\rm supp}^{+}}(x) = \{ i \in V \mid x_{i} > 0 \}\, </math>, <math>{{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, </math>とおく．関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が交換公理:
+　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{n} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in n\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{n})\, </math> と表わす，すなわち<math>\chi_i(v) = {1  (v=i)
 <table align="center">

@@ 5行目: / 5行目: @@
 === 詳説 ===
-　離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を，凸解析 ([6]) とマトロイド理論 ([1, 7, 8]) の両方の視点から考察する方法論を，[[離散凸解析]] (discrete convex analysis) ([1, 3, 4, 5])と呼ぶ．より一般的には，解析的な視点と組合せ論的な視点の両方から「組合せ論的な凸性」という構造を考察する方法論を指す．離散最適化 ([2])，システム解析 ([5])，数理経済学 ([5, 7]) などへの応用がある．
+　離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を，凸解析 ([7]) とマトロイド理論 ([1, 8, 9]) の両方の視点から考察する方法論を，[[離散凸解析]] (discrete convex analysis) ([1, 3, 4, 5, 6])と呼ぶ．より一般的には，解析的な視点と組合せ論的な視点の両方から「組合せ論的な凸性」という構造を考察する方法論を指す．離散最適化 ([2, 5])，システム解析 ([6])，数理経済学・ゲーム理論 ([5, 6, 8])，確率過程（[5]）などへの応用がある．
-　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える(<math>V\, </math>は有限集合である)．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{V} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in V\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{V})\, </math> と表わす．ベクトル<math>x \in {\mathbf Z}^{V}\, </math>に対して，<math>{{\rm supp}^{+}}(x) = \{ i \in V \mid x_{i} > 0 \}\, </math>, <math>{{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, </math>とおく．関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が交換公理:
+　整数格子点上で定義され整数値をとる関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ \pm\infty \}\, </math>を考える．<math>{{\rm dom\,}} f = \{ x \in {\mathbf Z}^{V} \mid -\infty < f(x) < +\infty \}\, </math>を<math>f\, </math>の実効定義域と呼び，以下では，<math>{{\rm dom\,}} f \not= \emptyset\, </math>であるような関数だけを考える．<math>i \in V\, </math>に対してその特性ベクトルを<math>\chi_{i} \ (\in \{ 0,1 \}^{V})\, </math> と表わす．ベクトル<math>x \in {\mathbf Z}^{V}\, </math>に対して，<math>{{\rm supp}^{+}}(x) = \{ i \in V \mid x_{i} > 0 \}\, </math>, <math>{{\rm supp}^{-}}(x) = \{ i \in V \mid x_{i} < 0 \}\, </math>とおく．関数<math>f: {\mathbf Z}^{V} \to {\mathbf Z} \cup \{ +\infty \}\, </math>が交換公理:
 <table align="center">
@@ 95行目: / 96行目: @@
 上の定理は，非線形整数計画に関する強双対性を主張しており，その本質的な部分は，<math>\inf\, </math>と<math>\sup\, </math>をとる範囲をそれぞれ整数ベクトルに限ってよいという主張にある．
-　M凸関数，L凸関数に関する種々の問題に対して効率的なアルゴリズムが開発されている．これに関しては [4, 5] を参照されたい．
+　M凸関数，L凸関数に関する種々の問題に対して効率的なアルゴリズムが開発されている．これに関しては [4, 6] を参照されたい．
@@ 108行目: / 109行目: @@
 [3] K. Murota, "Discrete convex analysis", ''Mathematical Programming'', '''83''' (1998), 313-371.
-[4] 室田一雄, 「離散凸解析」, 『共立出版』，2001.
+[4] 室田一雄, 『離散凸解析』, 共立出版，2001.
-[5] K.Murota, ''Discrete Convex Analysis'', SIAM, 2003.
+[5] 室田一雄, 『離散凸解析の考え方』, 共立出版，2007.
-[6] R. T. Rockafellar, ''Convex Analysis'', Princeton University Press, 1970.
+[6] K.Murota, ''Discrete Convex Analysis'', SIAM, 2003.
-[7] A.Tamura, "Applications of discrete convex analysis to mathmatical economics", ''Publ. RIMS'', '''40''' (2004) , 1015-1037.
+[7] R. T. Rockafellar, ''Convex Analysis'', Princeton University Press, 1970.
-[8] D. J. A. Welsh, ''Matroid Theory''，Academic Press, 1976.
+[8] A.Tamura, "Applications of discrete convex analysis to mathmatical economics", ''Publ. RIMS'', '''40''' (2004) , 1015-1037.
-[9] N. White, ed., ''Theory of Matroids'', Cambridge University Press, 1986.
+[9] D. J. A. Welsh, ''Matroid Theory''，Academic Press, 1976.
 [[Category:グラフ･ネットワーク|りさんとつかいせき]]

@@ 1行目: / 1行目: @@
 '''【りさんとつかいせき (discrete convex analysis)】'''
 離散的な集合(例えば整数格子点の集合)の上で定義された関数の構造を, 凸解析の視点とマトロイド理論の視点の両方から考察する方法論を, 離散凸解析と呼ぶ. より一般的には, 解析的な視点と組合せ論的な視点の両方から「組合せ論的な凸性」という構造を考察する方法論を指す. 離散最適化, システム解析, 数理経済学などへの応用がある.
-詳しくは[[《離散凸解析》|基礎編：離散凸解析]]を参照.
+=== 詳説 ===

← 古い版		2007年8月8日 (水) 12:02時点における版
2行目:		2行目:

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

← 古い版	2007年7月20日 (金) 01:07時点における版
(相違点なし)