《凸解析》 - 版の履歴

2007年8月6日 (月) 16:48にKuwashimaによる

2007-08-06T16:48:50Z

2007年8月6日 (月) 14:35にTetsuyatominagaによる

2007-08-06T14:35:41Z

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

2007-07-19T12:59:31Z

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

2007年7月14日 (土) 15:18に220.104.197.230による

2007-07-14T15:18:29Z

2007年7月6日 (金) 06:04に122.26.167.76による

2007-07-06T06:04:24Z

2007年7月6日 (金) 05:59に122.26.167.76による

2007-07-06T05:59:00Z

差分を表示

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

2007-07-05T01:45:00Z

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

新規ページ

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

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

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

x, \, y \in S, \ \alpha \in (0,1)
\ \Longrightarrow \ \alpha x + (1-\alpha) y \in S

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

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

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)

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

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)

であるとき，$f$ を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 \cite{1,2,3,4} に凸関数や凸集合の様々な性質に関する詳しい説明がある．

　次の性質をもつ集合 $C \subseteq \mathbf{R}^n$ を錐と呼ぶ．

x \in C, \ \alpha \ge 0 \ \Longrightarrow \ \alpha x \in C

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

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

\begin{equation} \label{A-B-09+siki1}
f(y) \ge f(x) + \xi^{\top}(y-x) \quad\quad \forall \, y \in \mathbf{R}^n
\end{equation}

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

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

\begin{equation} \label{A-B-09+siki2}
f^*(\xi) := \sup_{x \in \mathbf{R}^n} \{ \, \xi^{\top} x - f(x) \, \}
\end{equation}

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

\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] J.-B. Hiriart-Urruty and C. Lemaréchal, ''Convex Analysis and Minimization Algorithms, I and II'',
% Springer, 1993.
福島雅夫,
『非線形最適化の基礎』,
朝倉書店, 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年8月6日 (月) 16:48時点における版
113行目:		113行目:

	[5]福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.		[5]福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.
		+
		+
		+	[[Category:非線形計画\|とつかいせき]]

@@ 44行目: / 44行目: @@
-であるとき，<math>f\, </math> を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 [1,2,3,4]  に凸関数や凸集合の様々な性質に関する詳しい説明がある．
+であるとき，<math>f\, </math> を狭義凸関数という．明らかに，狭義凸関数は凸関数である．文献 [1,2,3,4,5]  に凸関数や凸集合の様々な性質に関する詳しい説明がある．
 　次の性質をもつ集合 <math>C \subseteq \mathbf{R}^n\, </math> を錐と呼ぶ．
@@ 70行目: / 70行目: @@
-真凸関数はその実効定義域 <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>\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,5]．
 　真凸関数 <math>f\, </math> に対して，次式で定義される真凸関数 <math>f^*\, </math> を <math>f\, </math> の[[共役関数]] (conjugate function) という．
@@ 97行目: / 97行目: @@
-共役関数の概念は最適化問題に対する双対理論において特に重要である [3,4].
+共役関数の概念は最適化問題に対する双対理論において特に重要である [3,4,5].
@@ 104行目: / 104行目: @@
 '''参考文献'''
-[1]  福島雅夫,『非線形最適化の基礎』, 朝倉書店,  2001.
+[1]  D.P.Bertsekas, ''Convex analysis and Optimization'', Athena Scientific, 2003.
 [2]  O.L. Mangasarian, ''Nonlinear Programming'', McGraw-Hill, 1969; (reprint, SIAM, 1994).
@@ 111行目: / 111行目: @@
 [4]  R.T. Rockafellar and R.J.B. Wets, ''Variational Analysis'',  Springer, 1998.

@@ 6行目: / 6行目: @@
-:<math>x, \, y \in S, \ \alpha \in (0,1)
+<table align="center">
 \ \Longrightarrow \ \alpha x + (1-\alpha) y \in S\, </math>
@@ 15行目: / 20行目: @@
-:<math>x, \, y \in \mbox{dom} \, f, \ \alpha \in (0,1)
+<table align="center">
 \ \Longrightarrow \ f(\alpha x + (1-\alpha)y)
 \le \alpha f(x) + (1-\alpha) f(y)\, </math>
@@ 23行目: / 33行目: @@
-:<math>x, \, y \in \mbox{dom} \, f,
+<table align="center">
 \ x \ne y, \ \alpha \in (0,1)
 \ \Longrightarrow \ f(\alpha x + (1-\alpha)y)
 < \alpha f(x) + (1-\alpha) f(y)\, </math>
@@ 34行目: / 49行目: @@
-:<math>x \in C, \ \alpha \ge 0 \ \Longrightarrow \ \alpha x \in C\, </math>
+<table align="center">
-特に，凸集合であるような錐を[[凸錐]] (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]．
+特に，凸集合であるような錐を[[凸錐]] (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>\textstyle 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>\textstyle \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>
+<table align="center">
@@ 50行目: / 75行目: @@
-:<math>f^*(\xi) := \sup_{x \in \mathbf{R}^n} \{ \, \xi^{\top} x - f(x) \, \}\, </math>　　<math>(2)\, </math>
+<table align="center">
@@ 56行目: / 87行目: @@
-:<math>\xi \in \partial f(x) \quad \Longleftrightarrow \quad
+<table align="center">
 x \in \partial f^*(\xi)  \quad \Longleftrightarrow \quad
 f(x) + f^*(\xi) = \xi^{\top} x\, </math>

@@ 37行目: / 37行目: @@
-特に，凸集合であるような錐を[[凸錐]] (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]．
+特に，凸集合であるような錐を[[凸錐]] (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) と呼ぶ．
@@ 68行目: / 68行目: @@
 '''参考文献'''
-[1]  福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.
+[1]  福島雅夫,『非線形最適化の基礎』, 朝倉書店,  2001.
 [2]  O.L. Mangasarian, ''Nonlinear Programming'', McGraw-Hill, 1969; (reprint, SIAM, 1994).
@@ 74行目: / 74行目: @@
 [3]  R.T. Rockafellar, ''Convex Analysis'', Princeton University Press, 1970.
-[4]  R.T. Rockafellar and R.J.B. Wets, ''Variational Analysis'', Springer, 1998.
+[4]  R.T. Rockafellar and R.J.B. Wets, ''Variational Analysis'',  Springer, 1998.

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