「双対性理論」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(基礎編と用語編のマージ)
 
(4人の利用者による、間の5版が非表示)
1行目: 1行目:
 
'''【そうついせいりろん (duality theory)】'''
 
'''【そうついせいりろん (duality theory)】'''
  
 +
=== 概要 ===
 +
非線形計画のみならず線形計画, 多目的計画, 離散凸解析などの分野で主問題とその双対問題の関係および集合や関数の双対関係を説明する重要な基礎理論. 共役関数やラグランジュ関数の性質に基づいていて, 鞍点定理やミニマックス定理と密接に関係している.
 +
 +
=== 詳説 ===
 
　[[双対性理論]] (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸解析などの分野で主問題とその双対問題の関係，および集合や関数の双対関係を説明する重要な基礎理論である [1, 2, 3, 4]．
 
　[[双対性理論]] (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>)，
 
　空間 <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>
+
<table align="center">
 +
<tr>
 +
<td><math>f^*(\xi):=\sup_{x\in{\mathbf{R}^n}} \{ \, \xi^{\top}x - f(x) \, \}</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
−
で定義される関数 <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]．
  
  
−
:<math>
+
<table align="center">
 +
<tr>
 +
<td><math>
 
\begin{array}{lll}
 
\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}
 
\end{array}
 
</math>
 
</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
27行目: 41行目:
  
  
−
:<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>
+
<table align="center">
 +
<tr>
 +
<td><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>
 +
</td>
 +
</tr>
 +
</table>
  
  
33行目: 52行目:
  
  
−
<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>
 
         \Longrightarrow\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}</math>
  
44行目: 63行目:
  
  
−
:<math>\begin{array}{llll}
+
<table align="center">
−
\mbox{min}_{x\in \mathbf{R}^n} & c^{\top}x+k(x)+h(b-Ax) & & \mbox{(1)}\\
+
<tr>
 +
<td><math>
 +
\begin{array}{llll}
 +
\mbox{min}_{x\in \mathbf{R}^n} & c^{\top}x+k(x)+h(b-Ax) & & (1)\\
 
\\
 
\\
−
\mbox{max}_{y\in \mathbf{R}^m} & b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c) & & \mbox{(2)}
+
\mbox{max}_{y\in \mathbf{R}^m} & b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c) & & (2)
 
\end{array}
 
\end{array}
 
</math>
 
</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
−
となる．ここで<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]．
  
  
−
:<math>
+
<table align="center">
 +
<tr>
 +
<td>
 +
<math>
 
\begin{array}{clcll}
 
\begin{array}{clcll}
 
(\mbox{P}_{LP}) & \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{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}
 
\end{array}
−
</math>
+
</math></td>
 +
</tr>
 +
</table>
  
  
66行目: 96行目:
  
  
−
:<math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>　　　　<math>\mbox{(3)}</math>
+
<table align="center">
−
 
+
<tr>
 +
<td><math>L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math></td>
 +
<td width="100" align="right"><math>(3)\,</math>
 +
</td>
 +
</tr>
 +
</table>
 +
　　　　
  
 
と定義する．<math>-L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}</math>が成立しているので，
 
と定義する．<math>-L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}</math>が成立しているので，
  
−
 
+
<table align="center">
−
:<math>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math>　　　　<math>\mbox{(4)}</math>
+
<tr>
 +
<td>
 +
<math>\varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)</math></td>
 +
<td width="100" align="right"><math>(4)\,</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
78行目: 120行目:
  
  
−
 
+
<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>
 
         \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>の鞍点
 
         \Longleftrightarrow (\bar{x},\bar{y})</math> が<math>L\,</math>の鞍点
  
92行目: 133行目:
  
 
が成立する．(iv) を[[鞍点定理]] (saddle point theorem) と呼ぶ．非線形計画問題
 
が成立する．(iv) を[[鞍点定理]] (saddle point theorem) と呼ぶ．非線形計画問題
 +
  
 
:<math>\mbox{(NLP)} \; \;  
 
:<math>\mbox{(NLP)} \; \;  
102行目: 144行目:
  
  
−
:<math>
+
<table align="center">
−
\begin{array}{lll}
+
<tr>
 +
<td><math>
 +
\begin{array}{rll}
 
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}\,|\,
109行目: 153行目:
 
f(x,u) &:= & f_{0}(x)+\theta{(F(x)+u)}
 
f(x,u) &:= & f_{0}(x)+\theta{(F(x)+u)}
 
\end{array}
 
\end{array}
−
</math>
+
</math></td>
 +
</tr>
 +
</table>
  
  
 
とおくと，(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)のラグランジュ関数は
 
とおくと，(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)のラグランジュ関数は
  
−
 
+
<table align="center">
−
:<math>L(x,\lambda,\mu)=f_{0}(x)+\sum_{i=1}^{k}\lambda_{i}g_{i}(x)
+
<tr>
−
                 +\sum_{j=1}^{l}\mu_{j}h_{j}(x)</math>　　　　<math>\mbox{(5)}</math>
+
<td><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></td>
 +
<td width="100" align="right"><math>(5)\,</math></td>
 +
</tr>
 +
</table>
  
  
122行目: 172行目:
  
  
−
:<math>
+
<table align="center">
 +
<tr>
 +
<td><math>
 
\begin{array}{cllll}
 
\begin{array}{cllll}
 
(\mbox{P}_{L}) & \mbox{min.}  
 
(\mbox{P}_{L}) & \mbox{min.}  
134行目: 186行目:
 
\end{array}
 
\end{array}
 
</math>
 
</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
 
となり，一般に問題<math>(\mbox{D}_{L})</math>をラグランジュの双対問題 (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> が存在すれば，つまり  
  
−
 
+
<table align="center">
−
:<math>\max_{\lambda\ge{0},\mu}L(\bar{x},\lambda,\mu)=L(\bar{x},\bar{\lambda},\bar{\mu})
+
<tr>
−
         =\min_{x}L(x,\bar{\lambda},\bar{\mu})</math>
+
<td><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></td>
 +
</tr>
 +
</table>
  
  
−
が成立すれば，<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]．
  
  
−
:<math>\bar{L}(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)+r\sigma{(u)}-y^{\top}u\,\}</math>
+
<table align="center">
 +
<tr>
 +
<td><math>\bar{L}(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)+r\sigma{(u)}-y^{\top}u\,\}</math>
 +
</td>
 +
</tr>
 +
</table>
  
  
−
ただし，<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]．
  
  
156行目: 220行目:
 
'''参考文献'''
 
'''参考文献'''
  
−
[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.
 
[2] 福島雅夫,『非線形最適化の基礎』, 朝倉書店, 2001.
163行目: 227行目:
  
 
[4] R.T. Rockafellar and R. J-B. Wets, ''Variational Analysis'', Springer, Berlin, 1998.
 
[4] R.T. Rockafellar and R. J-B. Wets, ''Variational Analysis'', Springer, Berlin, 1998.
 +
 +
[5] A.M.Rubinov, ''Abstract Convexity and Global Optimization'', Kluwer Academic, Dordrecht, 2000.
 +
 +
 +
[[Category:非線形計画|そうついせいりろん]]

2008年3月13日 (木) 22:43時点における最新版

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

概要

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

詳説

　双対性理論 (duality theory)は，非線形計画のみならず線形計画，多目的計画，離散凸解析などの分野で主問題とその双対問題の関係，および集合や関数の双対関係を説明する重要な基礎理論である [1, 2, 3, 4]．

　「双対」 (dual) と「共役」 (conjugate) は元々同義語として用いられ，数学の関数解析の分野では，ノルム空間 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\, } 上の有界線形汎関数の全体を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\,} の双対空間 (dual space) または共役空間 (conjugate space) といい，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X^{*}\, } と表して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\in{X}\, } における の値を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \langle x, x^{*}\rangle\,} または 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^{*}(x)\,} と書く．構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\, } が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 次元実ユークリッド空間 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n} の場合は，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mathbf{R}^n)^{*}} と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n} は同一視でき，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mathbf{R}^n)^{**}=\mathbf{R}^n} となり，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \langle x, x^{*}\rangle} は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^{*}\, } の内積 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x^{\top}x^{*}\,} となる．以下に述べる事柄は，無限次元空間に対しても拡張できるが，ここでは簡単のため 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n\,} に限定して説明する．

　空間 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\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\bar{\mathbf{R}}} に対して(ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{\mathbf{R}}=\mathbf{R}\cup \{ \infty , -\infty\}} )，


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^*(\xi):=\sup_{x\in{\mathbf{R}^n}} \{ \, \xi^{\top}x - f(x) \, \}}


で定義される関数 を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の共役関数 (conjugate function) という．共役関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^*\, } に対して，さらにその共役関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^{**}=(f^*)^{*}\,} を考えることができるが，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } が下半連続な真凸関数のときには，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^{**}\, } は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } に一致する．構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^*\, } を対応させる写像をルジャンドル-フェンシェル変換 (Legendre-Fenchel transform) と呼ぶ．

　下半連続な真凸関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f: \mathbf{R}^n\times{\mathbf{R}^m}\to\bar{\mathbf{R}}\,} に対して，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [4]．


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{lll} \mbox{(P)} & \min_{x\in \mathbf{R}^n}& \varphi{(x)}:=f(x,0) \\ \mbox{(D)} & \max_{y\in \mathbf{R}^m}& \psi{(y)}:=-f^{*}(0,y) \end{array} }


また，


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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\}}


とおくと，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\, } と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V\, } は凸集合となる．このとき，以下が成立する．


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(i)}\,} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{inf}_{x}\varphi{(x)}\ge\mbox{sup}_{y}\psi{(y)}}

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(ii)}\,} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\in{\mbox{int}\,U}\;} または 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \; 0\in{\mbox{int}\,V} \Longrightarrow\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}}


ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{int}\,U} は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle U\, } の内部を表す．(i)を弱双対定理 (weak duality theorem)，(ii)を双対定理 (duality theorem) と呼び，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}} が満たされるとき，主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという．(i)により，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{sup}_{y}\psi{(y)}=+\infty} なら主問題(P)は実行可能解を持たないが，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle -\infty<\varphi{(\bar{x})}=\psi{(\bar{y})}<+\infty} となる 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{y}} が存在すれば，それぞれ(P)と(D)の最適解となり，強い意味の双対性が成立する．一方，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{inf}_{x}\varphi{(x)}>\mbox{sup}_{y}\psi{(y)}} となるとき，主問題と双対問題の間に双対性のギャップ (duality gap) が存在するという．

　主問題(P)において，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x,u):=c^{\top}x+k(x)+h(b-Ax+u)} （ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k: \mathbf{R}^n\to\bar{\mathbf{R}}} と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h: \mathbf{R}^m\to\bar{\mathbf{R}}} は下半連続な真凸関数で構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\in{\mathbf{R}^{m\times{n}}}} , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\in{\mathbf{R}^m}} , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c\in{\mathbf{R}^n}} ）とすると，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f^{*}(v,y)=-b^{\top}y+h^{*}(y)+k^{*}(A^{\top}y-c+v)} となり [4]，主問題(P)と双対問題(D)はそれぞれ


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{llll} \mbox{min}_{x\in \mathbf{R}^n} & c^{\top}x+k(x)+h(b-Ax) & & (1)\\ \\ \mbox{max}_{y\in \mathbf{R}^m} & b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c) & & (2) \end{array} }


となる．ここで構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\in\mbox{int}\,(A\mbox{dom}k+\mbox{dom}h)\,} または構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c\in\mbox{int}\,(A^{\top}\mbox{dom}h^{*}-\mbox{dom}k^{*})\,} が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これをフェンシェルの双対性 (Fenchel duality) と呼んでいる．通常は，簡略化して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c\, } と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\, } を零ベクトル，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle -A\, } を恒等写像として，新たに構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(x)\, } を凸関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_1(x):=k(x)\,} と凹関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_2(x):=-h(x)\,} の差で表し，主問題 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min}_{x}\{f_1(x)-f_2(x)\}\,} に対して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{max}_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}} をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_{2}^{*}(y):=\mbox{inf}_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}} ．双対性は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{int}\,(\mbox{dom}f_1)\,\cap\, \mbox{int}\,(\mbox{dom}f_2)\neq\emptyset} のとき成立する．また，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k(x):=\mbox{sup}_{s\le{0}}x^{\top}s, h(z):=\mbox{sup}_{w\ge{0}}z^{\top}w} とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} }


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


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3)\,}

　　　　

と定義する．構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle -L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}} が成立しているので，

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y)} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (4)\,}


となる．通常，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{inf}_{x}L(x,\bar{y})=L(\bar{x},\bar{y})=\mbox{sup}_{y}L(\bar{x},y)} すなわち，すべての 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\in{\mathbf{R}^n}} と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y\in{\mathbf{R}^m}} に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L(x,\bar{y})\ge{L(\bar{x},\bar{y})}\ge{L(\bar{x},y)}} が成り立つとき，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x},\bar{y})} を関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^{n}\times{\mathbf{R}^m}} 上での鞍点 (saddle point) と呼ぶ．(4) により，


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(iii)}\,} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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)}}


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{(iv)}\,} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi{(\bar{x})}=\mbox{inf}_{x}\varphi{(x)}=\mbox{sup}_{y}\psi{(y)}=\psi{(\bar{y})} \Longleftrightarrow (\bar{x},\bar{y})} が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\,} の鞍点

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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})}}


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



(ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_0,g_i,h_j} は 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf{R}^n} で定義された実数値関数，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k+l=m} ) に対して，


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} }


とおくと，(3) により構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y=(\lambda,\mu)=(\lambda_{1},\ldots,\lambda_{k},\mu_{1},\ldots,\mu_{l}) \in{\mathbf{R}^{k}_{+}\times{\mathbf{R}^{l}}}} に対する問題(NLP)のラグランジュ関数は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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)} 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (5)\,}


となる．この 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\lambda,\mu)} をラグランジュ乗数 (Lagrange multipliers) と呼ぶ．このとき，主問題と双対問題は


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} }


となり，一般に問題構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mbox{D}_{L})} をラグランジュの双対問題 (Lagrangian dual problem)と呼ぶ．鞍点定理により，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } の鞍点 が存在すれば，つまり

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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})}


が成立すれば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{\lambda},\bar{\mu})} はそれぞれ問題構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mbox{P}_{L})\,} と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mbox{D}_{L})\,} の最適解となり最適値が一致する．これをラグランジュの双対性 (Lagrangian duality) と呼ぶ．(iv) により，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min}_{x}\mbox{sup}_{y}L(x,y)=\mbox{max}_{y}\mbox{inf}_{x}L(x,y)\,} が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理をミニマックス定理(minimax theorem) と呼ぶ [1, 2]． 逆に，主問題の目的関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_0\, } と制約関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g_i\, } がすべて凸で，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h_j\, } がすべてアフィン関数であるような凸計画問題 (convex programming problem) においては，適当な条件のもとで，問題構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mbox{P}_{L})\,} の最適解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} に対して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{\lambda}\ge{0}} であるようなラグランジュ乗数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{\lambda},\bar{\mu})} が存在して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x},\bar{\lambda},\bar{\mu})} がラグランジュ関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L\, } の鞍点となる．また，次のような拡張ラグランジュ関数(augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．



ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r\, } は正定数，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma:\mathbf{R}^{m}\rightarrow\bar{\mathbf{R}}\,} は に対して 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0=\sigma{(0)}<\sigma{(u)}\,} を満足する下半連続な真凸関数である．関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma\,} の例としては 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sigma{(u)}:=\frac{1}{2}\|u\|^{2}\,} などがある．さらに、最近では大域的最適化(global optimization)や抽象的凸解析(abstract convex analysis)の立場からの研究も行われている[5]．


参考文献

[1] J.M.Borwein and A.S.Lewis, Convex Analysis and Nonlinear Optimization, Theory and Examples(Second Edition), Springer, NewYork, 2006.

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

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

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

[5] A.M.Rubinov, Abstract Convexity and Global Optimization, Kluwer Academic, Dordrecht, 2000.

「https://orsj-ml.org/orwiki/wiki/index.php?title=双対性理論&oldid=9667」から取得