赤黒木 - 版の履歴

2007年9月22日 (土) 05:52にSaruによる

2007-09-22T05:52:49Z

Orsjwiki: "赤黒木" を保護しました。 [edit=sysop:move=sysop]

2007-07-19T21:58:14Z

"赤黒木" を保護しました。 [edit=sysop:move=sysop]

2007年7月9日 (月) 23:48に124.144.188.143による

2007-07-09T23:48:37Z

2007年7月9日 (月) 05:00に122.17.2.240による

2007-07-09T05:00:42Z

122.26.167.76: ページの白紙化

2007-07-06T05:57:04Z

ページの白紙化

122.26.167.76: 新しいページ: ''''【とつかいせき (convex analysis)】''' 　凸解析 (convex analysis) は，ベクトル空間における凸集合あるいはベクトル空間上で定義さ...'

2007-07-06T05:53:29Z

新しいページ: ''''【とつかいせき (convex analysis)】''' 　凸解析 (convex analysis) は，ベクトル空間における凸集合あるいはベクトル空間上で定義さ...'

新規ページ

'''【とつかいせき (convex analysis)】'''

　[[凸解析]] (convex analysis) は，ベクトル空間における凸集合あるいはベクトル空間上で定義された凸関数に関する諸性質を取り扱うものであり，数理計画の基礎理論として非常に重要な役割を果たしている．

　次の性質をもつ空間 <math>¥mathbf{R}^n¥, </math> の部分集合 <math>S ¥subseteq ¥mathbf{R}^n¥, </math> を[[凸集合]] (convex set) と呼ぶ．

:<math>x, ¥, y ¥in S, ¥ ¥alpha ¥in (0,1)
¥ ¥Longrightarrow ¥ ¥alpha x + (1-¥alpha) y ¥in S¥, </math>

特に，有限個の半空間の共通部分として表される凸集合を凸多面体と呼ぶ．

　空間 <math>¥mathbf{R}^n¥, </math> 上で定義された拡張実数値関数 <math>f : ¥mathbf{R}^n ¥to [-¥infty,+¥infty]¥, </math> に対して，そのエピグラフを<math>¥mbox{epi}¥, f := ¥{ (x,¥mu) ¥in ¥mathbf{R}^{n+1} ¥, | ¥,f(x) ¥le ¥mu ¥}¥, </math>と定義し，<math>¥mbox{epi}¥, f¥, </math> が凸集合であるような関数 <math>f¥, </math> を[[凸関数]] (convex function) と呼ぶ．ここで，関数 <math>f¥, </math> の値域に <math>¥pm ¥infty¥, </math> が含まれていることは重要である．考察の対象とする関数をこのように拡張することにより，最適化問題に関連する諸性質を統一的に記述することが可能となる．例えば，実数値凸関数 <math>h : ¥mathbf{R}^n ¥to ¥mathbf{R}¥, </math> を凸集合 <math>S ¥subseteq ¥mathbf{R}^n¥, </math> 上で最小化する制約つき最適化問題は，拡張実数値関数 <math>¥hat h : ¥mathbf{R}^n ¥to (-¥infty,+¥infty]¥, </math> を <math>¥hat h(x) = h(x) ¥ (x ¥in S¥, </math> のとき<math>)¥, </math>, <math>¥ = + ¥infty ¥ (x ¥not¥in S¥, </math> のとき<math>)¥, </math> と定義することにより，見かけ上，凸関数 <math>¥hat h¥, </math> を制約なしで最小化する問題として表すことができる．また，<math>f(x) = -¥infty¥, </math> となる点 <math>x¥, </math> が存在せず，さらに恒等的に <math>f(x) ¥equiv +¥infty¥, </math> ではないようなものを，特に真凸関数といい，集合 <math>¥mbox{dom}¥, f := ¥{ x ¥, | ¥, f(x) < +¥infty ¥}¥, </math> を <math>f¥, </math> の実効定義域あるいは単に定義域と呼ぶ．真凸関数は理論的にも実際的にも意味のある凸関数のクラスと考えることができる．なお，<math>f(x) = -¥infty¥, </math> となる <math>x¥, </math> が存在しないような関数 <math>f¥, </math> に対しては

:<math>x, ¥, y ¥in ¥mbox{dom} ¥, f, ¥ ¥alpha ¥in (0,1)
¥ ¥Longrightarrow ¥ f(¥alpha x + (1-¥alpha)y)
¥le ¥alpha f(x) + (1-¥alpha) f(y)¥, </math>

を凸関数の定義とすることもできる．さらに，

:<math>x, ¥, y ¥in ¥mbox{dom} ¥, f,
¥ x ¥ne y, ¥ ¥alpha ¥in (0,1)
¥ ¥Longrightarrow ¥ f(¥alpha x + (1-¥alpha)y)
< ¥alpha f(x) + (1-¥alpha) f(y)¥, </math>

であるとき，<math>f¥, </math> を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 [1,2,3,4] に凸関数や凸集合の様々な性質に関する詳しい説明がある．

　次の性質をもつ集合 <math>C ¥subseteq ¥mathbf{R}^n¥, </math> を錐と呼ぶ．

:<math>x ¥in C, ¥ ¥alpha ¥ge 0 ¥ ¥Longrightarrow ¥ ¥alpha x ¥in C¥, </math>

特に，凸集合であるような錐を[[凸錐]] (convex cone) という．最適化理論においては，凸錐はしばしば方向ベクトルの集合を表し，特に最適性条件の導出に際して重要である [4]．凸錐 <math>C ¥subseteq ¥mathbf{R}^n¥, </math> に対して，集合 <math>¥{ y ¥in ¥mathbf{R}^n ¥, | ¥,x^{¥top}y ¥le 0 ¥ ¥forall x ¥in C ¥}¥, </math> を <math>C¥, </math> の極錐と呼び，<math>C^*¥, </math> と表す．与えられたベクトル <math>a^1, ¥dots, a^m ¥in ¥mathbf{R}^n¥, </math> に対して定義される凸錐 <math>C = ¥{ x ¥in ¥mathbf{R}^n ¥, | ¥, x=¥sum_{i=1}^m ¥gamma_i a^i,¥ ¥gamma_i ¥ge 0, ¥ i=1,¥dots,m ¥}¥, </math> の極錐は <math>C^* = ¥{ y ¥in ¥mathbf{R}^n ¥, | ¥, y^{¥top}a^i ¥le 0, ¥, i=1,¥dots,m ¥}¥, </math> で与えられ，さらに <math>C = (C^*)^*¥, </math> が成り立つ．これは，<math>b ¥in C¥, </math>，すなわち <math>¥sum_{i=1}^m ¥gamma_i a^i = b¥, </math> を満たす <math>¥gamma_i ¥ge 0, ¥, i=1,¥dots,m,¥, </math> が存在することと，<math>b ¥not¥in C¥, </math>，すなわち <math>y^{¥top} b > 0¥, </math> を満たすベクトル <math>y ¥in C^*¥, </math> が存在することの，どちらか一方のみが成立することを意味している．これはファーカスの定理と呼ばれている．このように，２つの条件の一方のみが必ず成り立つことを保証する定理は，一般に[[二者択一定理]] (theorem of the alternative) と呼ばれ，最適性条件の導出に有用である [2]．

　真凸関数 <math>f¥, </math> に対して，次式を満足するベクトル <math>¥xi ¥in ¥mathbf{R}^n¥, </math> を <math>f¥, </math> の <math>x¥, </math> における[[劣勾配]] (subgradient) と呼ぶ．

:<math>f(y) ¥ge f(x) + ¥xi^{¥top}(y-x) ¥quad¥quad ¥forall ¥, y ¥in ¥mathbf{R}^n¥, </math>　　<math>(1)¥, </math>

真凸関数はその実効定義域 <math>¥mbox{dom} ¥, f¥, </math> の任意の相対的内点において，少なくとも１つの劣勾配をもつ．特に，凸関数 <math>f¥, </math> が点 <math>x¥, </math> において微分可能ならば，<math>f¥, </math> の <math>x¥, </math> における劣勾配は唯一存在し，通常の勾配 <math>¥nabla f(x)¥, </math> に等しい．しかし，<math>f¥, </math> が点 <math>x¥, </math> において微分可能でないときには劣勾配は無数に存在する．一般に，<math>f¥, </math> の <math>x¥, </math> における劣勾配全体の集合は <math>¥partial f(x)¥, </math> と表される．劣勾配の定義 (1) より，<math>0 ¥in ¥partial f(x)¥, </math> は点 <math>x¥, </math> が凸関数の最小点であるための必要十分条件であることは容易に確かめられる．劣勾配の概念は非凸関数に対しても拡張され，微分不可能最適化において基本的な役割を果たしている [1,3,4]．

　真凸関数 <math>f¥, </math> に対して，次式で定義される真凸関数 <math>f^*¥, </math> を <math>f¥, </math> の[[共役関数]] (conjugate function) という．

:<math>f^*(¥xi) := ¥sup_{x ¥in ¥mathbf{R}^n} ¥{ ¥, ¥xi^{¥top} x - f(x) ¥, ¥}¥, </math>　　<math>(2)¥, </math>

いま，<math>¥partial f¥, </math> と <math>¥partial f^*¥, </math> を点-集合写像とみなせば，<math>¥partial f¥, </math> と <math>¥partial f^*¥, </math> は互いに逆写像の関係にあり，さらに，<math>¥partial f^*(¥xi)¥, </math> の任意の要素 <math>x¥, </math> は共役関数 <math>f^*¥, </math> の定義 (2) の右辺の最大を与える．すなわち，次の関係が成立する．

:<math>¥xi ¥in ¥partial f(x) ¥quad ¥Longleftrightarrow ¥quad
x ¥in ¥partial f^*(¥xi) ¥quad ¥Longleftrightarrow ¥quad
f(x) + f^*(¥xi) = ¥xi^{¥top} x¥, </math>

共役関数の概念は最適化問題に対する双対理論において特に重要である [3,4].

----
'''参考文献'''

[1] 福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.

[2] O.L. Mangasarian, ''Nonlinear Programming'', McGraw-Hill, 1969; (reprint, SIAM, 1994).

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

[4] R.T. Rockafellar and R.J.B. Wets, ''Variational Analysis'', Springer, 1998.

← 古い版		2007年9月22日 (土) 05:52時点における版
1行目:		1行目:
−	'''~~【あかくろぎ~~ (red black tree)】'''	+	'''【あかくろぎ (red black tree) 】'''

−	~~平衡二分探索木の一種で,~~ (1) ~~すべての頂点は赤か黒,~~ (2) ~~赤い頂点は必ず黒い親をもつ,~~ (3) ~~根とすべての葉は黒,~~ (4) 根から葉へのどのパスも同数の黒い頂点を含む, という4つの条件を満たす. この条件より, 根から葉へのどのパスも, 長さが2倍以上違わなくなり, ゆえに要素数 <math>n \, </math> の赤黒木の高さは <math>O(\log n) \,</math>~~になる. 赤黒木は, 木の形の変化に対して再平衡化を行うことにより, 要素の挿入・削除・ある要素が含まれるかの確認を~~<math> O(\log n) \,</math> ~~で実行できる.~~	+	平衡二分探索木の一種で，(1) すべての頂点は赤か黒，(2) 赤い頂点は必ず黒い親をもつ，(3) 根とすべての葉は黒，(4) 根から葉へのどのパスも同数の黒い頂点を含む，という4つの条件を満たす．この条件より，根から葉へのどのパスも，長さが2倍以上違わなくなり，ゆえに要素数<math>n \, </math>の赤黒木の高さは<math>\mathrm{O}(\log n) \,</math>になる．赤黒木は，木の形の変化に対して再平衡化を行うことにより，要素の挿入・削除・ある要素が含まれるかの確認を<math> \mathrm{O}(\log n) \,</math>で実行できる．

← 古い版		2007年7月9日 (月) 23:48時点における版
1行目:		1行目:
	'''【あかくろぎ (red black tree)】'''		'''【あかくろぎ (red black tree)】'''

−	平衡二分探索木の一種で, (1) すべての頂点は赤か黒, (2) 赤い頂点は必ず黒い親をもつ, (3) 根とすべての葉は黒, (4) 根から葉へのどのパスも同数の黒い頂点を含む, という4つの条件を満たす. この条件より, 根から葉へのどのパスも, 長さが2倍以上違わなくなり, ゆえに要素数 $n$ の赤黒木の高さは O($\log n$)になる. 赤黒木は, 木の形の変化に対して再平衡化を行うことにより, 要素の挿入・削除・ある要素が含まれるかの確認を O$(\log n)$ で実行できる.	+	平衡二分探索木の一種で, (1) すべての頂点は赤か黒, (2) 赤い頂点は必ず黒い親をもつ, (3) 根とすべての葉は黒, (4) 根から葉へのどのパスも同数の黒い頂点を含む, という4つの条件を満たす. この条件より, 根から葉へのどのパスも, 長さが2倍以上違わなくなり, ゆえに要素数 <math>n \, </math> の赤黒木の高さは <math>O(\log n) \,</math>になる. 赤黒木は, 木の形の変化に対して再平衡化を行うことにより, 要素の挿入・削除・ある要素が含まれるかの確認を<math> O(\log n) \,</math> で実行できる.

← 古い版	2007年7月9日 (月) 05:00時点における版
1行目:	1行目:
	+	'''【あかくろぎ (red black tree)】'''

	+	平衡二分探索木の一種で, (1) すべての頂点は赤か黒, (2) 赤い頂点は必ず黒い親をもつ, (3) 根とすべての葉は黒, (4) 根から葉へのどのパスも同数の黒い頂点を含む, という4つの条件を満たす. この条件より, 根から葉へのどのパスも, 長さが2倍以上違わなくなり, ゆえに要素数 $n$ の赤黒木の高さは O($\log n$)になる. 赤黒木は, 木の形の変化に対して再平衡化を行うことにより, 要素の挿入・削除・ある要素が含まれるかの確認を O$(\log n)$ で実行できる.

← 古い版		2007年7月6日 (金) 05:57時点における版
1行目:		1行目:
−	~~'''【とつかいせき (convex analysis)】'''~~

−	[[凸解析]] (convex analysis) は，ベクトル空間における凸集合あるいはベクトル空間上で定義された凸関数に関する諸性質を取り扱うものであり，数理計画の基礎理論として非常に重要な役割を果たしている．
−
−	~~次の性質をもつ空間 <math>¥mathbf{R}^n¥, </math> の部分集合 <math>S ¥subseteq ¥mathbf{R}^n¥, </math> を[[凸集合]] (convex set) と呼ぶ．~~
−
−
−	~~:<math>x, ¥, y ¥in S, ¥ ¥alpha ¥in (0,1)~~
−	~~¥ ¥Longrightarrow ¥ ¥alpha x + (1-¥alpha) y ¥in S¥, </math>~~
−
−
−	~~特に，有限個の半空間の共通部分として表される凸集合を凸多面体と呼ぶ．~~
−
−	空間 <math>¥mathbf{R}^n¥, </math> 上で定義された拡張実数値関数 <math>f : ¥mathbf{R}^n ¥to [-¥infty,+¥infty]¥, </math> に対して，そのエピグラフを<math>¥mbox{epi}¥, f := ¥{ (x,¥mu) ¥in ¥mathbf{R}^{n+1} ¥, \| ¥,f(x) ¥le ¥mu ¥}¥, </math>と定義し，<math>¥mbox{epi}¥, f¥, </math> が凸集合であるような関数 <math>f¥, </math> を[[凸関数]] (convex function) と呼ぶ．ここで，関数 <math>f¥, </math> の値域に <math>¥pm ¥infty¥, </math> が含まれていることは重要である．考察の対象とする関数をこのように拡張することにより，最適化問題に関連する諸性質を統一的に記述することが可能となる．例えば，実数値凸関数 <math>h : ¥mathbf{R}^n ¥to ¥mathbf{R}¥, </math> を凸集合 <math>S ¥subseteq ¥mathbf{R}^n¥, </math> 上で最小化する制約つき最適化問題は，拡張実数値関数 <math>¥hat h : ¥mathbf{R}^n ¥to (-¥infty,+¥infty]¥, </math> を <math>¥hat h(x) = h(x) ¥ (x ¥in S¥, </math> のとき<math>)¥, </math>, <math>¥ = + ¥infty ¥ (x ¥not¥in S¥, </math> のとき<math>)¥, </math> と定義することにより，見かけ上，凸関数 <math>¥hat h¥, </math> を制約なしで最小化する問題として表すことができる．また，<math>f(x) = -¥infty¥, </math> となる点 <math>x¥, </math> が存在せず，さらに恒等的に <math>f(x) ¥equiv +¥infty¥, </math> ではないようなものを，特に真凸関数といい，集合 <math>¥mbox{dom}¥, f := ¥{ x ¥, \| ¥, f(x) < +¥infty ¥}¥, </math> を <math>f¥, </math> の実効定義域あるいは単に定義域と呼ぶ．真凸関数は理論的にも実際的にも意味のある凸関数のクラスと考えることができる．なお，<math>f(x) = -¥infty¥, </math> となる <math>x¥, </math> が存在しないような関数 <math>f¥, </math> に対しては
−
−
−	~~:<math>x, ¥, y ¥in ¥mbox{dom} ¥, f, ¥ ¥alpha ¥in (0,1)~~
−	~~¥ ¥Longrightarrow ¥ f(¥alpha x + (1-¥alpha)y)~~
−	~~¥le ¥alpha f(x) + (1-¥alpha) f(y)¥, </math>~~
−
−
−	~~を凸関数の定義とすることもできる．さらに，~~
−
−
−	~~:<math>x, ¥, y ¥in ¥mbox{dom} ¥, f,~~
−	~~¥ x ¥ne y, ¥ ¥alpha ¥in (0,1)~~
−	~~¥ ¥Longrightarrow ¥ f(¥alpha x + (1-¥alpha)y)~~
−	~~< ¥alpha f(x) + (1-¥alpha) f(y)¥, </math>~~
−
−
−	であるとき，<math>f¥, </math> を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 [1,2,3,4] に凸関数や凸集合の様々な性質に関する詳しい説明がある．
−
−	~~次の性質をもつ集合 <math>C ¥subseteq ¥mathbf{R}^n¥, </math> を錐と呼ぶ．~~
−
−
−	~~:<math>x ¥in C, ¥ ¥alpha ¥ge 0 ¥ ¥Longrightarrow ¥ ¥alpha x ¥in C¥, </math>~~
−
−
−	特に，凸集合であるような錐を[[凸錐]] (convex cone) という．最適化理論においては，凸錐はしばしば方向ベクトルの集合を表し，特に最適性条件の導出に際して重要である [4]．凸錐 <math>C ¥subseteq ¥mathbf{R}^n¥, </math> に対して，集合 <math>¥{ y ¥in ¥mathbf{R}^n ¥, \| ¥,x^{¥top}y ¥le 0 ¥ ¥forall x ¥in C ¥}¥, </math> を <math>C¥, </math> の極錐と呼び，<math>C^¥, </math> と表す．与えられたベクトル <math>a^1, ¥dots, a^m ¥in ¥mathbf{R}^n¥, </math> に対して定義される凸錐 <math>C = ¥{ x ¥in ¥mathbf{R}^n ¥, \| ¥, x=¥sum_{i=1}^m ¥gamma_i a^i,¥ ¥gamma_i ¥ge 0, ¥ i=1,¥dots,m ¥}¥, </math> の極錐は <math>C^ = ¥{ y ¥in ¥mathbf{R}^n ¥, \| ¥, y^{¥top}a^i ¥le 0, ¥, i=1,¥dots,m ¥}¥, </math> で与えられ，さらに <math>C = (C^)^¥, </math> が成り立つ．これは，<math>b ¥in C¥, </math>，すなわち <math>¥sum_{i=1}^m ¥gamma_i a^i = b¥, </math> を満たす <math>¥gamma_i ¥ge 0, ¥, i=1,¥dots,m,¥, </math> が存在することと，<math>b ¥not¥in C¥, </math>，すなわち <math>y^{¥top} b > 0¥, </math> を満たすベクトル <math>y ¥in C^*¥, </math> が存在することの，どちらか一方のみが成立することを意味している．これはファーカスの定理と呼ばれている．このように，２つの条件の一方のみが必ず成り立つことを保証する定理は，一般に[[二者択一定理]] (theorem of the alternative) と呼ばれ，最適性条件の導出に有用である [2]．
−
−	真凸関数 <math>f¥, </math> に対して，次式を満足するベクトル <math>¥xi ¥in ¥mathbf{R}^n¥, </math> を <math>f¥, </math> の <math>x¥, </math> における[[劣勾配]] (subgradient) と呼ぶ．
−
−
−	~~:<math>f(y) ¥ge f(x) + ¥xi^{¥top}(y-x) ¥quad¥quad ¥forall ¥, y ¥in ¥mathbf{R}^n¥, </math>　　<math>(1)¥, </math>~~
−
−
−	真凸関数はその実効定義域 <math>¥mbox{dom} ¥, f¥, </math> の任意の相対的内点において，少なくとも１つの劣勾配をもつ．特に，凸関数 <math>f¥, </math> が点 <math>x¥, </math> において微分可能ならば，<math>f¥, </math> の <math>x¥, </math> における劣勾配は唯一存在し，通常の勾配 <math>¥nabla f(x)¥, </math> に等しい．しかし，<math>f¥, </math> が点 <math>x¥, </math> において微分可能でないときには劣勾配は無数に存在する．一般に，<math>f¥, </math> の <math>x¥, </math> における劣勾配全体の集合は <math>¥partial f(x)¥, </math> と表される．劣勾配の定義 (1) より，<math>0 ¥in ¥partial f(x)¥, </math> は点 <math>x¥, </math> が凸関数の最小点であるための必要十分条件であることは容易に確かめられる．劣勾配の概念は非凸関数に対しても拡張され，微分不可能最適化において基本的な役割を果たしている [1,3,4]．
−
−	~~真凸関数 <math>f¥, </math> に対して，次式で定義される真凸関数 <math>f^*¥, </math> を <math>f¥, </math> の[[共役関数]] (conjugate function) という．~~
−
−
−	~~:<math>f^*(¥xi) := ¥sup_{x ¥in ¥mathbf{R}^n} ¥{ ¥, ¥xi^{¥top} x - f(x) ¥, ¥}¥, </math>　　<math>(2)¥, </math>~~
−
−
−	いま，<math>¥partial f¥, </math> と <math>¥partial f^¥, </math> を点-集合写像とみなせば，<math>¥partial f¥, </math> と <math>¥partial f^¥, </math> は互いに逆写像の関係にあり，さらに，<math>¥partial f^(¥xi)¥, </math> の任意の要素 <math>x¥, </math> は共役関数 <math>f^¥, </math> の定義 (2) の右辺の最大を与える．すなわち，次の関係が成立する．
−
−
−	~~:<math>¥xi ¥in ¥partial f(x) ¥quad ¥Longleftrightarrow ¥quad~~
−	~~x ¥in ¥partial f^*(¥xi) ¥quad ¥Longleftrightarrow ¥quad~~
−	~~f(x) + f^*(¥xi) = ¥xi^{¥top} x¥, </math>~~
−
−
−	~~共役関数の概念は最適化問題に対する双対理論において特に重要である [3,4].~~
−
−
−
−	~~----~~
−	~~'''参考文献'''~~
−
−	~~[1] 福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.~~
−
−	~~[2] O.L. Mangasarian, ''Nonlinear Programming'', McGraw-Hill, 1969; (reprint, SIAM, 1994).~~
−
−	~~[3] R.T. Rockafellar, ''Convex Analysis'', Princeton University Press, 1970.~~
−
−	~~[4] R.T. Rockafellar and R.J.B. Wets, ''Variational Analysis'', Springer, 1998.~~

← 古い版	2007年7月19日 (木) 21:58時点における版
(相違点なし)