《双対性理論》 - 版の履歴

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

2007-08-06T16:45:13Z

2007年8月6日 (月) 13:58にTetsuyatominagaによる

2007-08-06T13:58:58Z

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

2007-07-19T12:57:38Z

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

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

2007-07-14T14:04:16Z

差分を表示

2007年7月4日 (水) 07:08にOrsjwikiによる

2007-07-04T07:08:13Z

Orsjwiki: 新しいページ: ''''【そうついせいりろん (duality theory)】''' 　双対性理論 (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸...'

2007-07-03T07:58:21Z

新しいページ: ''''【そうついせいりろん (duality theory)】''' 　双対性理論 (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸...'

新規ページ

'''【そうついせいりろん (duality theory)】'''

　[[双対性理論]] (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> に限定して説明する．

　空間 <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>)，

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

で定義される関数 <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>
\begin{array}{lll}
\mbox{(P)} & \min_{x\in \mathbf{R}^n}& \varphi{(x)} \\
\mbox{(D)} & \max_{y\in \mathbf{R}^m}& \psi{(y)}
\end{array}
</math>

また，

:<math>U:=\{u\in{\mathbf{R}^m}\,| \inf_{x\in{\mathbf{R}^n}}f(x,u)<+\infty\}\quad V:=\{v\in{\mathbf{R}^n}\,|\inf_{y\in{\mathbf{R}^m}}f^{*}(v,y)<+\infty\}</math>

とおくと，<math>U\, </math> と <math>V\, </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}
\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>\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)はそれぞれ

:<math>\begin{array}{llll}
\mbox{min}_{x\in \mathbf{R}^n} & c^{\top}x+k(x)+h(b-Ax) & & \mbox{(1)}\\
\\
\mbox{max}_{y\in \mathbf{R}^m} & b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c) & & \mbox{(2)}
\end{array}
</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}
(\mbox{P}_{LP}) & \mbox{min.} & c^{\top}x & s. t. & x\ge{0}, \ Ax\ge{b}. \\
(\mbox{D}_{LP}) & \mbox{max.} & b^{\top}y & s. t. & y\ge{0}, \ A^{\top}y\le{c}.
\end{array}
</math>

次に，[[ラグランジュ関数]] (Lagrangian function) を

:<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>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math>　　　　<math>\mbox{(4)}\,</math>

となる．通常，<math>\mbox{inf}_{x}L(x,\bar{y})=L(\bar{x},\bar{y})=\mbox{sup}_{y}L(\bar{x},y)</math>すなわち，すべての <math>x\in{\mathbf{R}^n}</math>と<math>y\in{\mathbf{R}^m}</math> に対して<math>L(x,\bar{y})\ge{L(\bar{x},\bar{y})}\ge{L(\bar{x},y)}</math>が成り立つとき，<math>(\bar{x},\bar{y})</math> を関数 <math>L\, </math> の <math>\mathbf{R}^{n}\times{\mathbf{R}^m}</math> 上での鞍点 (saddle point) と呼ぶ．(4) により，

<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})}
\Longleftrightarrow (\bar{x},\bar{y})</math> が<math>L\,</math>の鞍点

::<math>\Longleftrightarrow \mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)
\Longleftrightarrow
\varphi{(\bar{x})}=L(\bar{x},\bar{y})=\psi{(\bar{y})}</math>

が成立する．(iv) を[[鞍点定理]] (saddle point theorem) と呼ぶ．非線形計画問題

:<math>\mbox{(NLP)} \; \;
\mbox{min.} \ f_{0}(x) \quad \mbox{s. t.} \; \;
g_{i}(x)\le{0} \ (i=1,\ldots, k), \; \;
h_{j}(x)=0 \ (j=1,\ldots,l),</math>

(ただし，<math>f_0,g_i,h_j</math> は <math>\mathbf{R}^n</math> で定義された実数値関数，<math>k+l=m</math>) に対して，

:<math>
\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}\,|\,
(\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)}
\end{array}
</math>

とおくと，(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>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>

となる．この <math>(\lambda,\mu)</math> をラグランジュ乗数 (Lagrange multipliers) と呼ぶ．このとき，主問題と双対問題は

:<math>
\begin{array}{cllll}
(\mbox{P}_{L}) & \mbox{min.}
& \displaystyle \sup_{\lambda\ge{0},\mu} L(x, \lambda, \mu)
& \mbox{s. t.} & \displaystyle{x \in {\mathbf{R}^n}}, \\
(\mbox{D}_{L}) & \mbox{max.}
& \displaystyle \inf_{x} L(x,\lambda,\mu)
& \mbox{s. t.}
& \displaystyle{0 \le \lambda \in {\mathbf{R}^{k}}},
\displaystyle \mu \in {\mathbf{R}^{l}},
\end{array}
</math>

となり，一般に問題<math>(\mbox{D}_{L})</math>をラグランジュの双対問題 (Lagrangian dual problem)と呼ぶ．鞍点定理により，<math>L\, </math> の鞍点 <math>(\bar{x},\bar{\lambda},\bar{\mu})</math> が存在すれば，つまり

:<math>\max_{\lambda\ge{0},\mu}L(\bar{x},\lambda,\mu)=L(\bar{x},\bar{\lambda},\bar{\mu})
=\min_{x}L(x,\bar{\lambda},\bar{\mu})</math>

が成立すれば，<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{L}(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)+r\sigma{(u)}-y^{\top}u\,\}</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] I. Ekeland and R. Temam, ''Convex Analysis and Variational Problems'', North-Holland, Amsterdam, 1976.

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

[3] 今野浩, 山下浩,『非線形計画法』, 日科技連, 1978.

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

← 古い版		2007年8月6日 (月) 16:45時点における版
225行目:		225行目:

	[5] A.M.Rubinov, ''Abstract Convexity and Global Optimization'', Kluwer Academic, Dordrecht, 2000.		[5] A.M.Rubinov, ''Abstract Convexity and Global Optimization'', Kluwer Academic, Dordrecht, 2000.
		+
		+
		+	[[Category:非線形計画\|そうついせいりろん]]

@@ 16行目: / 16行目: @@
-で定義される関数 <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>に対して，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [4]．
@@ 25行目: / 25行目: @@
 <td><math>
 \begin{array}{lll}
-\mbox{(P)} & \min_{x\in \mathbf{R}^n}& \varphi{(x)} \\
+\mbox{(P)} & \min_{x\in \mathbf{R}^n}& \varphi{(x)}:=f(x,0) \\
-\mbox{(D)} & \max_{y\in \mathbf{R}^m}& \psi{(y)}
+\mbox{(D)} & \max_{y\in \mathbf{R}^m}& \psi{(y)}:=-f^{*}(0,y)
 \end{array}
 </math>
@@ 198行目: / 198行目: @@
-が成立すれば，<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, 2]． 逆に，主問題の目的関数 <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]．
@@ 209行目: / 209行目: @@
-ただし，<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> などがある．さらに、最近では大域的最適化(global optimization)や抽象的凸解析(abstract convex analysis)の立場からの研究も行われている[5]．
@@ 216行目: / 216行目: @@
 '''参考文献'''
-[1] I. Ekeland and R. Temam, ''Convex Analysis and Variational Problems'', North-Holland, Amsterdam, 1976.
+[1] J.M.Borwein and A.S.Lewis, ''Convex Analysis and Nonlinear Optimization, Theory and Examples(Second Edition)'', Springer, NewYork, 2006.
 [2] 福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.
@@ 223行目: / 223行目: @@
 [4] R.T. Rockafellar and R. J-B. Wets, ''Variational Analysis'', Springer, Berlin, 1998.

← 古い版		2007年7月4日 (水) 07:08時点における版
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]．

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