《双対性理論》のソースを表示

'''【そうついせいりろん (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>)，


<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: \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]．


<table align="center">
<tr>
<td><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>
</td>
</tr>
</table>


また，


<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>


とおくと，<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)はそれぞれ


<table align="center">
<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) & & (2)
\end{array}
</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]．


<table align="center">
<tr>
<td>
<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></td>
</tr>
</table>


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


<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>が成立しているので，

<table align="center">
<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>


となる．通常，<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>) に対して，


<table align="center">
<tr>
<td><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></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)のラグランジュ関数は

<table align="center">
<tr>
<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>


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


<table align="center">
<tr>
<td><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>
</td>
</tr>
</table>


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

<table align="center">
<tr>
<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]．


<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> などがある．



----
'''参考文献'''

[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.