赤黒木
【とつかいせき (convex analysis)】
凸解析 (convex analysis) は，ベクトル空間における凸集合あるいはベクトル空間上で定義された凸関数に関する諸性質を取り扱うものであり，数理計画の基礎理論として非常に重要な役割を果たしている．
次の性質をもつ空間 構文解析に失敗 (構文エラー): {\displaystyle ¥mathbf{R}^n¥, } の部分集合 構文解析に失敗 (構文エラー): {\displaystyle S ¥subseteq ¥mathbf{R}^n¥, } を凸集合 (convex set) と呼ぶ．
- 構文解析に失敗 (構文エラー): {\displaystyle x, ¥, y ¥in S, ¥ ¥alpha ¥in (0,1) ¥ ¥Longrightarrow ¥ ¥alpha x + (1-¥alpha) y ¥in S¥, }
特に，有限個の半空間の共通部分として表される凸集合を凸多面体と呼ぶ．
空間 構文解析に失敗 (構文エラー): {\displaystyle ¥mathbf{R}^n¥, } 上で定義された拡張実数値関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f : ¥mathbf{R}^n ¥to [-¥infty,+¥infty]¥, } に対して，そのエピグラフを構文解析に失敗 (構文エラー): {\displaystyle ¥mbox{epi}¥, f := ¥{ (x,¥mu) ¥in ¥mathbf{R}^{n+1} ¥, | ¥,f(x) ¥le ¥mu ¥}¥, } と定義し，構文解析に失敗 (構文エラー): {\displaystyle ¥mbox{epi}¥, f¥, } が凸集合であるような関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, } を凸関数 (convex function) と呼ぶ．ここで，関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, } の値域に 構文解析に失敗 (構文エラー): {\displaystyle ¥pm ¥infty¥, } が含まれていることは重要である．考察の対象とする関数をこのように拡張することにより，最適化問題に関連する諸性質を統一的に記述することが可能となる．例えば，実数値凸関数 構文解析に失敗 (構文エラー): {\displaystyle h : ¥mathbf{R}^n ¥to ¥mathbf{R}¥, } を凸集合 構文解析に失敗 (構文エラー): {\displaystyle S ¥subseteq ¥mathbf{R}^n¥, } 上で最小化する制約つき最適化問題は，拡張実数値関数 構文解析に失敗 (構文エラー): {\displaystyle ¥hat h : ¥mathbf{R}^n ¥to (-¥infty,+¥infty]¥, } を 構文解析に失敗 (構文エラー): {\displaystyle ¥hat h(x) = h(x) ¥ (x ¥in S¥, } のとき構文解析に失敗 (構文エラー): {\displaystyle )¥, } , 構文解析に失敗 (構文エラー): {\displaystyle ¥ = + ¥infty ¥ (x ¥not¥in S¥, } のとき構文解析に失敗 (構文エラー): {\displaystyle )¥, } と定義することにより，見かけ上，凸関数 構文解析に失敗 (構文エラー): {\displaystyle ¥hat h¥, } を制約なしで最小化する問題として表すことができる．また，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) = -¥infty¥, } となる点 構文解析に失敗 (構文エラー): {\displaystyle x¥, } が存在せず，さらに恒等的に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x) ¥equiv +¥infty¥, } ではないようなものを，特に真凸関数といい，集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle ¥mbox{dom}¥, f := ¥{ x ¥, | ¥, f(x) < +¥infty ¥}¥, } を 構文解析に失敗 (構文エラー): {\displaystyle f¥, } の実効定義域あるいは単に定義域と呼ぶ．真凸関数は理論的にも実際的にも意味のある凸関数のクラスと考えることができる．なお，構文解析に失敗 (構文エラー): {\displaystyle f(x) = -¥infty¥, } となる 構文解析に失敗 (構文エラー): {\displaystyle x¥, } が存在しないような関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, } に対しては
- 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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)¥, }
を凸関数の定義とすることもできる．さらに，
- 構文解析に失敗 (構文エラー): {\displaystyle 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)¥, }
であるとき，構文解析に失敗 (構文エラー): {\displaystyle f¥, }
を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 [1,2,3,4] に凸関数や凸集合の様々な性質に関する詳しい説明がある．
次の性質をもつ集合 構文解析に失敗 (構文エラー): {\displaystyle C ¥subseteq ¥mathbf{R}^n¥, } を錐と呼ぶ．
- 構文解析に失敗 (構文エラー): {\displaystyle x ¥in C, ¥ ¥alpha ¥ge 0 ¥ ¥Longrightarrow ¥ ¥alpha x ¥in C¥, }
特に，凸集合であるような錐を凸錐 (convex cone) という．最適化理論においては，凸錐はしばしば方向ベクトルの集合を表し，特に最適性条件の導出に際して重要である [4]．凸錐 構文解析に失敗 (構文エラー): {\displaystyle C ¥subseteq ¥mathbf{R}^n¥, }
に対して，集合 構文解析に失敗 (構文エラー): {\displaystyle ¥{ y ¥in ¥mathbf{R}^n ¥, | ¥,x^{¥top}y ¥le 0 ¥ ¥forall x ¥in C ¥}¥, }
を 構文解析に失敗 (構文エラー): {\displaystyle C¥, }
の極錐と呼び，構文解析に失敗 (構文エラー): {\displaystyle C^*¥, }
と表す．与えられたベクトル 構文解析に失敗 (構文エラー): {\displaystyle a^1, ¥dots, a^m ¥in ¥mathbf{R}^n¥, }
に対して定義される凸錐 構文解析に失敗 (構文エラー): {\displaystyle C = ¥{ x ¥in ¥mathbf{R}^n ¥, | ¥, x=¥sum_{i=1}^m ¥gamma_i a^i,¥ ¥gamma_i ¥ge 0, ¥ i=1,¥dots,m ¥}¥, }
の極錐は 構文解析に失敗 (構文エラー): {\displaystyle C^* = ¥{ y ¥in ¥mathbf{R}^n ¥, | ¥, y^{¥top}a^i ¥le 0, ¥, i=1,¥dots,m ¥}¥, }
で与えられ，さらに 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C = (C^*)^*¥, }
が成り立つ．これは，構文解析に失敗 (構文エラー): {\displaystyle b ¥in C¥, }
，すなわち 構文解析に失敗 (構文エラー): {\displaystyle ¥sum_{i=1}^m ¥gamma_i a^i = b¥, }
を満たす 構文解析に失敗 (構文エラー): {\displaystyle ¥gamma_i ¥ge 0, ¥, i=1,¥dots,m,¥, }
が存在することと，構文解析に失敗 (構文エラー): {\displaystyle b ¥not¥in C¥, }
，すなわち 構文解析に失敗 (構文エラー): {\displaystyle y^{¥top} b > 0¥, }
を満たすベクトル 構文解析に失敗 (構文エラー): {\displaystyle y ¥in C^*¥, }
が存在することの，どちらか一方のみが成立することを意味している．これはファーカスの定理と呼ばれている．このように，２つの条件の一方のみが必ず成り立つことを保証する定理は，一般に二者択一定理 (theorem of the alternative) と呼ばれ，最適性条件の導出に有用である [2]．
真凸関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, } に対して，次式を満足するベクトル 構文解析に失敗 (構文エラー): {\displaystyle ¥xi ¥in ¥mathbf{R}^n¥, } を 構文解析に失敗 (構文エラー): {\displaystyle f¥, } の 構文解析に失敗 (構文エラー): {\displaystyle x¥, } における劣勾配 (subgradient) と呼ぶ．
- 構文解析に失敗 (構文エラー): {\displaystyle f(y) ¥ge f(x) + ¥xi^{¥top}(y-x) ¥quad¥quad ¥forall ¥, y ¥in ¥mathbf{R}^n¥, } 構文解析に失敗 (構文エラー): {\displaystyle (1)¥, }
真凸関数はその実効定義域 構文解析に失敗 (構文エラー): {\displaystyle ¥mbox{dom} ¥, f¥, }
の任意の相対的内点において，少なくとも１つの劣勾配をもつ．特に，凸関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, }
が点 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
において微分可能ならば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f¥, }
の 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
における劣勾配は唯一存在し，通常の勾配 構文解析に失敗 (構文エラー): {\displaystyle ¥nabla f(x)¥, }
に等しい．しかし，構文解析に失敗 (構文エラー): {\displaystyle f¥, }
が点 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
において微分可能でないときには劣勾配は無数に存在する．一般に，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f¥, }
の 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
における劣勾配全体の集合は 構文解析に失敗 (構文エラー): {\displaystyle ¥partial f(x)¥, }
と表される．劣勾配の定義 (1) より，構文解析に失敗 (構文エラー): {\displaystyle 0 ¥in ¥partial f(x)¥, }
は点 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
が凸関数の最小点であるための必要十分条件であることは容易に確かめられる．劣勾配の概念は非凸関数に対しても拡張され，微分不可能最適化において基本的な役割を果たしている [1,3,4]．
真凸関数 構文解析に失敗 (構文エラー): {\displaystyle f¥, } に対して，次式で定義される真凸関数 構文解析に失敗 (構文エラー): {\displaystyle f^*¥, } を 構文解析に失敗 (構文エラー): {\displaystyle f¥, } の共役関数 (conjugate function) という．
- 構文解析に失敗 (構文エラー): {\displaystyle f^*(¥xi) := ¥sup_{x ¥in ¥mathbf{R}^n} ¥{ ¥, ¥xi^{¥top} x - f(x) ¥, ¥}¥, } 構文解析に失敗 (構文エラー): {\displaystyle (2)¥, }
いま，構文解析に失敗 (構文エラー): {\displaystyle ¥partial f¥, }
と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle ¥partial f^*¥, }
を点-集合写像とみなせば，構文解析に失敗 (構文エラー): {\displaystyle ¥partial f¥, }
と 構文解析に失敗 (構文エラー): {\displaystyle ¥partial f^*¥, }
は互いに逆写像の関係にあり，さらに，構文解析に失敗 (構文エラー): {\displaystyle ¥partial f^*(¥xi)¥, }
の任意の要素 構文解析に失敗 (構文エラー): {\displaystyle x¥, }
は共役関数 構文解析に失敗 (構文エラー): {\displaystyle f^*¥, }
の定義 (2) の右辺の最大を与える．すなわち，次の関係が成立する．
- 構文解析に失敗 (構文エラー): {\displaystyle ¥xi ¥in ¥partial f(x) ¥quad ¥Longleftrightarrow ¥quad x ¥in ¥partial f^*(¥xi) ¥quad ¥Longleftrightarrow ¥quad f(x) + f^*(¥xi) = ¥xi^{¥top} x¥, }
共役関数の概念は最適化問題に対する双対理論において特に重要である [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.