双対性理論 - 版の履歴

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

2008-03-13T13:43:59Z

基礎編と用語編のマージ

差分を表示

2007年8月8日 (水) 11:27にKanda.kによる

2007-08-08T11:27:01Z

Orsjwiki: "双対性理論" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T02:20:09Z

"双対性理論" を保護しました。 [edit=sysop:move=sysop]

122.17.2.240: ページの置換: ''''【そうついせいりろん (duality theory)】''' 非線形計画のみならず線形計画, 多目的計画, 離散凸解析などの分野で主問題とその双対...'

2007-07-12T16:46:32Z

ページの置換: ''''【そうついせいりろん (duality theory)】''' 非線形計画のみならず線形計画, 多目的計画, 離散凸解析などの分野で主問題とその双対...'

差分を表示

2007年7月3日 (火) 03:10にOrsjwikiによる

2007-07-03T03:10:30Z

2007年6月29日 (金) 10:02に122.26.167.76による

2007-06-29T10:02:38Z

2007年6月29日 (金) 04:46にOrsjwikiによる

2007-06-29T04:46:58Z

2007年6月29日 (金) 03:18にOrsjwikiによる

2007-06-29T03:18:19Z

2007年6月29日 (金) 02:41にOrsjwikiによる

2007-06-29T02:41:22Z

2007年6月28日 (木) 10:49にOrsjwikiによる

2007-06-28T10:49:22Z

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

	非線形計画のみならず線形計画, 多目的計画, 離散凸解析などの分野で主問題とその双対問題の関係および集合や関数の双対関係を説明する重要な基礎理論. 共役関数やラグランジュ関数の性質に基づいていて, 鞍点定理やミニマックス定理と密接に関係している.		非線形計画のみならず線形計画, 多目的計画, 離散凸解析などの分野で主問題とその双対問題の関係および集合や関数の双対関係を説明する重要な基礎理論. 共役関数やラグランジュ関数の性質に基づいていて, 鞍点定理やミニマックス定理と密接に関係している.
		+
		+	詳しくは[[《双対性理論》\|基礎編：双対性理論]]を参照.

← 古い版		2007年7月3日 (火) 03:10時点における版
143行目:		143行目:


−	が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題<math>(\mbox{P}_{L})\,</math>と<math>(\mbox{D}_{L})\,</math>の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv) により，<math>\mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)\,</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理]](minimax theorem) と呼ぶ [1]．逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題<math>(\mbox{P}_{L})\,</math>の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．	+	が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題<math>(\mbox{P}_{L})\,</math>と<math>(\mbox{D}_{L})\,</math>の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv) により，<math>\mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)\,</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理(数理計画における)]](minimax theorem) と呼ぶ [1]．逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題<math>(\mbox{P}_{L})\,</math>の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．

@@ 3行目: / 3行目: @@
 　[[双対性理論]] (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸解析などの分野で主問題とその双対問題の関係，および集合や関数の双対関係を説明する重要な基礎理論である [1, 2, 3, 4]．
-　「双対」 (dual) と「共役」 (conjugate) は元々同義語として用いられ，数学の関数解析の分野では，ノルム空間 <math>X\, </math> 上の有界線形汎関数の全体を<math>X\,</math>  の双対空間 (dual space) または共役空間 (conjugate space) といい，<math>X^{*}\, </math> と表して，<math>x\in{X}\, </math> における <math>x^{*}\in{X^*}</math> の値を<math>\langle x, x^{*}\rangle</math> または <math>x^{*}(x)</math> と書く．<math>X\, </math> が <math>n\, </math> 次元実ユークリッド空間 <math>\mathbf{R}^n</math> の場合は，<math>(\mathbf{R}^n)^{*}</math> と <math>\mathbf{R}^n</math> は同一視でき，<math>(\mathbf{R}^n)^{**}=\mathbf{R}^n</math> となり，<math>\langle x, x^{*}\rangle</math> は<math>x\, </math> と <math>x^{*}\, </math> の内積 <math>x^{\top}x^{*}</math> となる．以下に述べる事柄は，無限次元空間に対しても拡張できるが，ここでは簡単のため <math>\mathbf{R}^n</math> に限定して説明する．
+　「双対」 (dual) と「共役」 (conjugate) は元々同義語として用いられ，数学の関数解析の分野では，ノルム空間 <math>X\, </math> 上の有界線形汎関数の全体を<math>X\,</math>  の双対空間 (dual space) または共役空間 (conjugate space) といい，<math>X^{*}\, </math> と表して，<math>x\in{X}\, </math> における <math>x^{*}\in{X^*}\,</math> の値を<math>\langle x, x^{*}\rangle\,</math> または <math>x^{*}(x)\,</math> と書く．<math>X\, </math> が <math>n\, </math> 次元実ユークリッド空間 <math>\mathbf{R}^n</math> の場合は，<math>(\mathbf{R}^n)^{*}</math> と <math>\mathbf{R}^n</math> は同一視でき，<math>(\mathbf{R}^n)^{**}=\mathbf{R}^n</math> となり，<math>\langle x, x^{*}\rangle</math> は<math>x\, </math> と <math>x^{*}\, </math> の内積 <math>x^{\top}x^{*}\,</math> となる．以下に述べる事柄は，無限次元空間に対しても拡張できるが，ここでは簡単のため <math>\mathbf{R}^n\,</math> に限定して説明する．
 　空間 <math>\mathbf{R}^n</math> 上で定義された拡張実数値関数 <math>f: \mathbf{R}^n\to\bar{\mathbf{R}}</math> に対して(ただし，<math>\bar{\mathbf{R}}=\mathbf{R}\cup \{ \infty , -\infty\}</math>)，
@@ 11行目: / 11行目: @@
-で定義される関数 <math>f^*\, </math> を <math>f\, </math> の共役関数 (conjugate function) という．共役関数 <math>f^*\, </math> に対して，さらにその共役関数 <math>f^{**}=(f^*)^{*}</math> を考えることができるが，<math>f\, </math> が下半連続な真凸関数のときには，<math>f^{**}\, </math> は <math>f\, </math> に一致する．<math>f\, </math> に <math>f^*\, </math> を対応させる写像をルジャンドル-フェンシェル変換 (Legendre-Fenchel transform) と呼ぶ．
+で定義される関数 <math>f^*\, </math> を <math>f\, </math> の共役関数 (conjugate function) という．共役関数 <math>f^*\, </math> に対して，さらにその共役関数 <math>f^{**}=(f^*)^{*}\,</math> を考えることができるが，<math>f\, </math> が下半連続な真凸関数のときには，<math>f^{**}\, </math> は <math>f\, </math> に一致する．<math>f\, </math> に <math>f^*\, </math> を対応させる写像をルジャンドル-フェンシェル変換 (Legendre-Fenchel transform) と呼ぶ．
-　下半連続な真凸関数 <math>f: \mathbf{R}^n\times{\mathbf{R}^m}\to\bar{\mathbf{R}}</math>に対して，関数 <math>\varphi : \mathbf{R}^n \to \bar{\mathbf{R}}</math> と <math>\psi : \mathbf{R}^m \to \bar{\mathbf{R}}</math> をそれぞれ <math>\varphi{(x)}:=f(x,0)</math> と <math>\psi{(y)}:=-f^{*}(0,y)</math> で定義し，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [1, 4]．
+　下半連続な真凸関数 <math>f: \mathbf{R}^n\times{\mathbf{R}^m}\to\bar{\mathbf{R}}\,</math>に対して，関数 <math>\varphi : \mathbf{R}^n \to \bar{\mathbf{R}}\,</math> と <math>\psi : \mathbf{R}^m \to \bar{\mathbf{R}}\,</math> をそれぞれ <math>\varphi{(x)}:=f(x,0)\,</math> と <math>\psi{(y)}:=-f^{*}(0,y)\,</math> で定義し，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [1, 4]．
@@ 33行目: / 33行目: @@
-<math>\mbox{(i)}</math>   <math>\mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}</math>
+<math>\mbox{(i)}\,</math>   <math>\mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}</math>
-<math>\mbox{(ii)}</math>  <math>0\in{\mbox{int}\,U}\;</math> または <math>\; 0\in{\mbox{int}\,V}
+<math>\mbox{(ii)}\,</math>  <math>0\in{\mbox{int}\,U}\;</math> または <math>\; 0\in{\mbox{int}\,V}
          \Longrightarrow\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}</math>
@@ 52行目: / 52行目: @@
-となる．ここで<math>b\in\mbox{int}\,(A\mbox{dom}k+\mbox{dom}h)</math> または<math>c\in\mbox{int}\,(A^{\top}\mbox{dom}h^{*}-\mbox{dom}k^{*})</math> が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これを[[フェンシェルの双対性]] (Fenchel duality) と呼んでいる．通常は，簡略化して <math>c\, </math> と <math>b\, </math> を零ベクトル，<math>-A\, </math> を恒等写像として，新たに<math>f(x)\, </math> を凸関数 <math>f_1(x):=k(x)</math> と凹関数 <math>f_2(x):=-h(x)</math> の差で表し，主問題 <math>\mbox{min}_{x}\{f_1(x)-f_2(x)\}</math>に対して，<math>\mbox{max}_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}</math> をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，<math>f_{2}^{*}(y):=\mbox{inf}_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}</math>．双対性は <math>\mbox{int}\,(\mbox{dom}f_1)\,\cap\, \mbox{int}\,(\mbox{dom}f_2)\neq\emptyset</math> のとき成立する．また，<math>k(x):=\mbox{sup}_{s\le{0}}x^{\top}s, h(z):=\mbox{sup}_{w\ge{0}}z^{\top}w</math> とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．
+となる．ここで<math>b\in\mbox{int}\,(A\mbox{dom}k+\mbox{dom}h)\,</math> または<math>c\in\mbox{int}\,(A^{\top}\mbox{dom}h^{*}-\mbox{dom}k^{*})\,</math> が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これを[[フェンシェルの双対性]] (Fenchel duality) と呼んでいる．通常は，簡略化して <math>c\, </math> と <math>b\, </math> を零ベクトル，<math>-A\, </math> を恒等写像として，新たに<math>f(x)\, </math> を凸関数 <math>f_1(x):=k(x)\,</math> と凹関数 <math>f_2(x):=-h(x)\,</math> の差で表し，主問題 <math>\mbox{min}_{x}\{f_1(x)-f_2(x)\}\,</math>に対して，<math>\mbox{max}_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}</math> をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，<math>f_{2}^{*}(y):=\mbox{inf}_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}</math>．双対性は <math>\mbox{int}\,(\mbox{dom}f_1)\,\cap\, \mbox{int}\,(\mbox{dom}f_2)\neq\emptyset</math> のとき成立する．また，<math>k(x):=\mbox{sup}_{s\le{0}}x^{\top}s, h(z):=\mbox{sup}_{w\ge{0}}z^{\top}w</math> とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．
@@ 66行目: / 66行目: @@
-:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>　　　　<math>\mbox{(3)}</math>
+:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>　　　　<math>\mbox{(3)}\,</math>
@@ 72行目: / 72行目: @@
-:<math>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math>　　　　<math>\mbox{(4)}</math>
+:<math>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math>　　　　<math>\mbox{(4)}\,</math>
@@ 79行目: / 79行目: @@
-<math>\mbox{(iii)}</math>   <math>\mbox{inf}_{x}\varphi{(x)}=\mbox{inf}_{x}\,[\,\mbox{sup}_{y}L(x,y)\,]
+<math>\mbox{(iii)}\,</math>   <math>\mbox{inf}_{x}\varphi{(x)}=\mbox{inf}_{x}\,[\,\mbox{sup}_{y}L(x,y)\,]
          \ge\mbox{sup}_{y}\,[\,\mbox{inf}_{x}L(x,y)\,]=\mbox{sup}_{y}\psi{(y)}</math>
-<math>\mbox{(iv)}</math>    <math>\varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})}
+<math>\mbox{(iv)}\,</math>    <math>\varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})}
          \Longleftrightarrow (\bar{x},\bar{y})</math> が<math>L\,</math>の鞍点
@@ 103行目: / 103行目: @@
 :<math>
-\begin{array}{lll}
+\begin{array}{rll}
 F(x) &:= & (g_{1}(x),\ldots,g_{k}(x),h_{1}(x),\ldots,h_{l}(x))^{\top}\\
 \theta(w) &:= & \sup_{\lambda,\mu}\{\lambda^{\top}w_{1}+\mu^{\top}w_{2}\,|\,
@@ 116行目: / 116行目: @@
 :<math>L(x,\lambda,\mu)=f_{0}(x)+\sum_{i=1}^{k}\lambda_{i}g_{i}(x)
-                 +\sum_{j=1}^{l}\mu_{j}h_{j}(x)</math>　　　　<math>\mbox{(5)}</math>
+                 +\sum_{j=1}^{l}\mu_{j}h_{j}(x)</math>　　　　<math>\mbox{(5)}\,</math>
@@ 143行目: / 143行目: @@
-が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題<math>(\mbox{P}_{L})</math>と<math>(\mbox{D}_{L})</math>の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv)により，<math>\mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理]](minimax theorem) と呼ぶ [1]． 逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題<math>(\mbox{P}_{L})</math>の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．
+が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題<math>(\mbox{P}_{L})\,</math>と<math>(\mbox{D}_{L})\,</math>の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv) により，<math>\mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)\,</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理]](minimax theorem) と呼ぶ [1]． 逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題<math>(\mbox{P}_{L})\,</math>の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．
@@ 149行目: / 149行目: @@
-ただし，<math>r\, </math> は正定数，<math>\sigma:\mathbf{R}^{m}\rightarrow\bar{\mathbf{R}}</math> は <math>u\neq{0}</math> に対して <math>0=\sigma{(0)}<\sigma{(u)}</math> を満足する下半連続な真凸関数である．関数 <math>\sigma</math> の例としては <math>\sigma{(u)}:=\frac{1}{2}\|u\|^{2}</math> などがある．
+ただし，<math>r\, </math> は正定数，<math>\sigma:\mathbf{R}^{m}\rightarrow\bar{\mathbf{R}}\,</math> は <math>u\neq{0}\,</math> に対して <math>0=\sigma{(0)}<\sigma{(u)}\,</math> を満足する下半連続な真凸関数である．関数 <math>\sigma\,</math> の例としては <math>\sigma{(u)}:=\frac{1}{2}\|u\|^{2}\,</math> などがある．

@@ 1行目: / 1行目: @@
-<math>\int f(x)dx</math><math>\int f(x)dx</math>'''【そうついせいりろん (duality theory)】'''
+'''【そうついせいりろん (duality theory)】'''
 　[[双対性理論]] (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸解析などの分野で主問題とその双対問題の関係，および集合や関数の双対関係を説明する重要な基礎理論である [1, 2, 3, 4]．
@@ 18行目: / 18行目: @@
 :<math>
 \begin{array}{lll}
-(P) & \min_{x\in \mathbf{R}^n}& \varphi{(x)} \\
+\mbox{(P)} & \min_{x\in \mathbf{R}^n}& \varphi{(x)} \\
-(D) & \max_{y\in \mathbf{R}^m}& \psi{(y)}
+\mbox{(D)} & \max_{y\in \mathbf{R}^m}& \psi{(y)}
 \end{array}
 </math>
@@ 57行目: / 57行目: @@
 :<math>
 \begin{array}{clcll}
-\mbox{(P}_{LP}\mbox{)} & \mbox{min.} & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
+(\mbox{P}_{LP}) & \mbox{min.} & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
-\mbox{(D}_{LP}\mbox{)} & \mbox{max.} & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
+(\mbox{D}_{LP}) & \mbox{max.} & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
 \end{array}
 </math>
@@ 83行目: / 83行目: @@
-<math>\mbox{(iv)}</math>    <math>varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})}
+<math>\mbox{(iv)}</math>    <math>\varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})}
          \Longleftrightarrow (\bar{x},\bar{y})</math> が<math>L\,</math>の鞍点
@@ 112行目: / 112行目: @@
-とおくと，(3) により<math>L(x,y)=f_{0}(x)+y^{T}F(x)-\theta^{*}(y)</math> となり，<math>y=(\lambda,\mu)=(\lambda_{1},\ldots,\lambda_{k},\mu_{1},\ldots,\mu_{l}) \in{\mathbf{R}^{k}_{+}\times{\mathbf{R}^{l}}}</math>に対する問題(NLP)のラグランジュ関数は
+とおくと，(3) により<math>y=(\lambda,\mu)=(\lambda_{1},\ldots,\lambda_{k},\mu_{1},\ldots,\mu_{l}) \in{\mathbf{R}^{k}_{+}\times{\mathbf{R}^{l}}}</math>に対する問題(NLP)のラグランジュ関数は
-:<math>\begin{equation}
+:<math>L(x,\lambda,\mu)=f_{0}(x)+\sum_{i=1}^{k}\lambda_{i}g_{i}(x)
-L(x,\lambda,\mu)=f_{0}(x)+\sum_{i=1}^{k}\lambda_{i}g_{i}(x)
+                 +\sum_{j=1}^{l}\mu_{j}h_{j}(x)</math>　　　　<math>\mbox{(5)}</math>
@@ 124行目: / 122行目: @@
-:<math>\begin{center}
+:<math>
-\begin{tabular}{cllll}
+\begin{array}{cllll}
-(P_{L}) & min.
+(\mbox{P}_{L}) & \mbox{min.}
          & \displaystyle \sup_{\lambda\ge{0},\mu} L(x, \lambda, \mu)
-         & s. t. & \displaystyle{x \in {\mathbf{R}^n}}, \\
+         & \mbox{s. t.} & \displaystyle{x \in {\mathbf{R}^n}}, \\
-(D_{L}) & max.
+(\mbox{D}_{L}) & \mbox{max.}
          & \displaystyle \inf_{x} L(x,\lambda,\mu)
-         & s. t.
+         & \mbox{s. t.}
-         & \displaystyle{0 \le \lambda \in {\mathbf{R}^{k}}}, \
+         & \displaystyle{0 \le \lambda \in {\mathbf{R}^{k}}},
            \displaystyle \mu \in {\mathbf{R}^{l}},
-\end{tabular}
+\end{array}
 </math>
-となり，一般に問題(D_{L})をラグランジュの双対問題 (Lagrangian dual problem)と呼ぶ．鞍点定理により，<math>L\, </math> の鞍点 <math>(\bar{x},\bar{\lambda},\bar{\mu})</math> が存在すれば，つまり
+となり，一般に問題<math>(\mbox{D}_{L})</math>をラグランジュの双対問題 (Lagrangian dual problem)と呼ぶ．鞍点定理により，<math>L\, </math> の鞍点 <math>(\bar{x},\bar{\lambda},\bar{\mu})</math> が存在すれば，つまり
@@ 146行目: / 143行目: @@
-が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題(P<math>_{L}</math>)と(D<math>_{L}</math>)の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv)により，<math>\min_{x}\sup_{y}L(x,y)=\max_{y}\inf_{x}L(x,y)</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理]](minimax theorem) と呼ぶ [1]． 逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題(P<math>_{L}</math>)の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．
+が成立すれば，<math>\bar{x}</math> と <math>(\bar{\lambda},\bar{\mu})</math> はそれぞれ問題<math>(\mbox{P}_{L})</math>と<math>(\mbox{D}_{L})</math>の最適解となり最適値が一致する．これを[[ラグランジュの双対性]] (Lagrangian duality) と呼ぶ．(iv)により，<math>\mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)</math> が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理を[[ミニマックス定理]](minimax theorem) と呼ぶ [1]． 逆に，主問題の目的関数 <math>f_0\, </math> と制約関数 <math>g_i\, </math> がすべて凸で，<math>h_j\, </math> がすべてアフィン関数であるような[[凸計画問題]] (convex programming problem) においては，適当な条件のもとで，問題<math>(\mbox{P}_{L})</math>の最適解 <math>\bar{x}</math> に対して，<math>\bar{\lambda}\ge{0}</math> であるようなラグランジュ乗数 <math>(\bar{\lambda},\bar{\mu})</math> が存在して，<math>(\bar{x},\bar{\lambda},\bar{\mu})</math> がラグランジュ関数 <math>L\, </math> の鞍点となる．さらに，次のような[[拡張ラグランジュ関数]](augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．

@@ 1行目: / 1行目: @@
-'''【そうついせいりろん (duality theory)】'''
+<math>\int f(x)dx</math><math>\int f(x)dx</math>'''【そうついせいりろん (duality theory)】'''
 　[[双対性理論]] (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸解析などの分野で主問題とその双対問題の関係，および集合や関数の双対関係を説明する重要な基礎理論である [1, 2, 3, 4]．
@@ 33行目: / 33行目: @@
-(i)   <math>\mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}</math>
+<math>\mbox{(i)}</math>   <math>\mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}</math>
-(ii)  <math>0\in{\mbox{int}\,U}\;</math> または <math>\; 0\in{\mbox{int}\,V}
+<math>\mbox{(ii)}</math>  <math>0\in{\mbox{int}\,U}\;</math> または <math>\; 0\in{\mbox{int}\,V}
          \Longrightarrow\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}</math>
@@ 66行目: / 66行目: @@
-:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>
+:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>　　　　<math>\mbox{(3)}</math>
 と定義する．<math>-L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}</math>が成立しているので，
-:<math>\medskip
-\noindent
-(iii) \ \inf_{x}\varphi{(x)}=\inf_{x}\,[\,\sup_{y}L(x,y)\,]
+<math>\mbox{(iii)}</math>   <math>\mbox{inf}_{x}\varphi{(x)}=\mbox{inf}_{x}\,[\,\mbox{sup}_{y}L(x,y)\,]
-         \ge\sup_{y}\,[\,\inf_{x}L(x,y)\,]=\sup_{y}\psi{(y)} \\
+         \ge\mbox{sup}_{y}\,[\,\mbox{inf}_{x}L(x,y)\,]=\mbox{sup}_{y}\psi{(y)}</math>
-(iv) \ \varphi{(\bar{x})}=\inf_{x}\varphi{(x)}
-        =\sup_{y}\psi{(y)}=\psi{(\bar{y})}
-         \Longleftrightarrow (\bar{x},\bar{y}) が L の鞍点
+<math>\mbox{(iv)}</math>    <math>varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})}
-        \\ \hspace*{1cm}
+         \Longleftrightarrow (\bar{x},\bar{y})</math> が<math>L\,</math>の鞍点
-       \Longleftrightarrow \min_{x}\sup_{y}L(x,y)=\max_{y}\inf_{x}L(x,y)
          \Longleftrightarrow
-         \varphi{(\bar{x})}=L(\bar{x},\bar{y})=\psi{(\bar{y})}
+         \varphi{(\bar{x})}=L(\bar{x},\bar{y})=\psi{(\bar{y})}</math>
@@ 100行目: / 95行目: @@
 :<math>\mbox{(NLP)} \; \;
 \mbox{min.} \ f_{0}(x) \quad \mbox{s. t.} \; \;
-g_{i}(x)\le{0} \ (i=1,\ldots, k), \
+g_{i}(x)\le{0} \ (i=1,\ldots, k), \; \;
 h_{j}(x)=0 \ (j=1,\ldots,l),</math>
@@ 107行目: / 102行目: @@
-:<math>\begin{center}
+:<math>
-\begin{tabular}{r@{}l}
+\begin{array}{lll}
-F(x)\,&:=(g_{1}(x),\ldots,g_{k}(x),h_{1}(x),\ldots,h_{l}(x))^{\top}\\
+F(x) &:= & (g_{1}(x),\ldots,g_{k}(x),h_{1}(x),\ldots,h_{l}(x))^{\top}\\
-\theta(w)\,&:=\sup_{\lambda,\mu}\{\lambda^{\top}w_{1}+\mu^{\top}w_{2}\,|\,
+\theta(w) &:= & \sup_{\lambda,\mu}\{\lambda^{\top}w_{1}+\mu^{\top}w_{2}\,|\,
          (\lambda,\mu)\in{\mathbf{R}^{k}_{+}\times{\mathbf{R}^{l}}},w=(w_1,w_2)^{\top}\}\\
-f(x,u)\,&:=f_{0}(x)+\theta{(F(x)+u)}
+f(x,u) &:= & f_{0}(x)+\theta{(F(x)+u)}
-\end{tabular}
+\end{array}
 </math>

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

@@ 33行目: / 33行目: @@
-(i)   <math>\inf_{x}\varphi{(x)}\ge\sup_{y}\psi{(y)}</math>
+(i)   <math>\mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}</math>
 (ii)  <math>0\in{\mbox{int}\,U}\;</math> または <math>\; 0\in{\mbox{int}\,V}
-         \Longrightarrow\inf_{x}\varphi{(x)}=\sup_{y}\psi{(y)}</math>
+         \Longrightarrow\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}</math>
-ここで，<math>\mbox{int}\,U</math> は <math>U\, </math> の内部を表す．(i)を弱双対定理 (weak duality theorem)，(ii)を[[双対定理]] (duality theorem) と呼び，<math>\inf_{x}\varphi{(x)}=\sup_{y}\psi{(y)}</math> が満たされるとき，主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという．(i)により，<math>\sup_{y}\psi{(y)}=+\infty</math> なら主問題(P)は実行可能解を持たないが，<math>-\infty<\varphi{(\bar{x})}=\psi{(\bar{y})}<+\infty</math> となる <math>\bar{x}</math> と <math>\bar{y}</math> が存在すれば，それぞれ(P)と(D)の最適解となり，強い意味の双対性が成立する．一方，<math>\inf_{x}\varphi{(x)}>\sup_{y}\psi{(y)}</math> となるとき，主問題と双対問題の間に[[双対性のギャップ]] (duality gap) が存在するという．
+ここで，<math>\mbox{int}\,U</math> は <math>U\, </math> の内部を表す．(i)を弱双対定理 (weak duality theorem)，(ii)を[[双対定理]] (duality theorem) と呼び，<math>\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}</math> が満たされるとき，主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという．(i)により，<math>\mbox{sup}_{y}\psi{(y)}=+\infty</math> なら主問題(P)は実行可能解を持たないが，<math>-\infty<\varphi{(\bar{x})}=\psi{(\bar{y})}<+\infty</math> となる <math>\bar{x}</math> と <math>\bar{y}</math> が存在すれば，それぞれ(P)と(D)の最適解となり，強い意味の双対性が成立する．一方，<math>\mbox{inf}_{x}\varphi{(x)}>\mbox{sup}_{y}\psi{(y)}</math> となるとき，主問題と双対問題の間に[[双対性のギャップ]] (duality gap) が存在するという．
 　主問題(P)において，<math>f(x,u):=c^{\top}x+k(x)+h(b-Ax+u)</math>（ただし，<math>k: \mathbf{R}^n\to\bar{\mathbf{R}}</math> と <math>h: \mathbf{R}^m\to\bar{\mathbf{R}}</math> は下半連続な真凸関数で<math>A\in{\mathbf{R}^{m\times{n}}}</math>, <math>b\in{\mathbf{R}^m}</math>, <math>c\in{\mathbf{R}^n}</math> ）とすると，<math>f^{*}(v,y)=-b^{\top}y+h^{*}(y)+k^{*}(A^{\top}y-c+v)</math>となり [4]，主問題(P)と双対問題(D)はそれぞれ
@@ 51行目: / 51行目: @@
 </math>
-<math>\min_{x}\{f_1(x)-f_2(x)\}</math>
+となる．ここで<math>b\in\mbox{int}\,(A\mbox{dom}k+\mbox{dom}h)</math> または<math>c\in\mbox{int}\,(A^{\top}\mbox{dom}h^{*}-\mbox{dom}k^{*})</math> が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これを[[フェンシェルの双対性]] (Fenchel duality) と呼んでいる．通常は，簡略化して <math>c\, </math> と <math>b\, </math> を零ベクトル，<math>-A\, </math> を恒等写像として，新たに<math>f(x)\, </math> を凸関数 <math>f_1(x):=k(x)</math> と凹関数 <math>f_2(x):=-h(x)</math> の差で表し，主問題 <math>\mbox{min}_{x}\{f_1(x)-f_2(x)\}</math>に対して，<math>\mbox{max}_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}</math> をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，<math>f_{2}^{*}(y):=\mbox{inf}_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}</math>．双対性は <math>\mbox{int}\,(\mbox{dom}f_1)\,\cap\, \mbox{int}\,(\mbox{dom}f_2)\neq\emptyset</math> のとき成立する．また，<math>k(x):=\mbox{sup}_{s\le{0}}x^{\top}s, h(z):=\mbox{sup}_{w\ge{0}}z^{\top}w</math> とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．
 :<math>
 \begin{array}{clcll}
-(P_{LP}) & min. & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
+\mbox{(P}_{LP}\mbox{)} & \mbox{min.} & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
-(D_{LP}) & max. & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
+\mbox{(D}_{LP}\mbox{)} & \mbox{max.} & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
 \end{array}
 </math>
@@ 72行目: / 65行目: @@
 次に，[[ラグランジュ関数]] (Lagrangian function) を
-と定義する．<math>-L(x,\cdot)=\left(f(x,\cdot)\right)^{*},　f(x,\cdot)=\left(-L(x,\cdot)\right)^{*}</math>が成立しているので，
+と定義する．<math>-L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}</math>が成立しているので，
-:<math>\begin{equation} \label{A-B-03+siki4}
+:<math>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math>
-\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)
+　　　　<math>\mbox{(4)}\,<\math>

@@ 44行目: / 44行目: @@
-:<math>\begin{eqnarray}
+:<math>\begin{array}{llll}
-\mbox{\rm min}_{x\in \mathbf{R}^n} &&
+\mbox{min}_{x\in \mathbf{R}^n} & c^{\top}x+k(x)+h(b-Ax) & & \mbox{(1)}\\
-\hspace*{-5mm} c^{\top}x+k(x)+h(b-Ax)
+\\
-        \label{A-B-03+siki1}\\
+\mbox{max}_{y\in \mathbf{R}^m} & b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c) & & \mbox{(2)}
-\mbox{\rm max}_{y\in \mathbf{R}^m} &&
+\end{array}
 </math>
-となる．ここで<math>b\in\mbox{\rm int}\,(A\mbox{\rm dom}k+\mbox{\rm dom}h)</math> または<math>c\in\mbox{\rm int}\,(A^{\top}\mbox{\rm dom}h^{*}-\mbox{\rm dom}k^{*})</math> が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これを[[フェンシェルの双対性]] (Fenchel duality) と呼んでいる．通常は，簡略化して <math>c\, </math> と <math>b\, </math> を零ベクトル，<math>-A\, </math> を恒等写像として，新たに<math>f(x)\, </math> を凸関数 <math>f_1(x):=k(x)</math> と凹関数 <math>f_2(x):=-h(x)</math> の差で表し，主問題 <math>\min_{x}\{f_1(x)-f_2(x)\}</math>に対して，<math>\max_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}</math> をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，<math>f_{2}^{*}(y):=\inf_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}</math>．双対性は <math>\mbox{\rm int}\,(\mbox{\rm dom}f_1)\,\cap\,        \mbox{\rm int}\,(\mbox{\rm dom}f_2)\neq\emptyset</math> のとき成立する．また，<math>k(x):=\sup_{s\le{0}}x^{\top}s, h(z):=\sup_{w\ge{0}}z^{\top}w</math> とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．
+<math>\min_{x}\{f_1(x)-f_2(x)\}</math>
-:<math>\begin{center}
+----
-\begin{tabular}{clcll}
 (P_{LP}) & min. & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
 (D_{LP}) & max. & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
-\end{tabular}
+\end{array}
 </math>
@@ 69行目: / 72行目: @@
 次に，[[ラグランジュ関数]] (Lagrangian function) を
-:<math>\begin{equation} \label{A-B-03+siki3}
+:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u \,\}</math>　　　<math>mbox{(3)}<\math>
 L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u \,\}