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

提供: ORWiki
ナビゲーションに移動 検索に移動
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}
 
(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)はそれぞれ
 
 主問題(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>
  
----
 
  
<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>\mbox{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>\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{int}\,(\mbox{dom}f_1)\,\cap\, \mbox{int}\,(\mbox{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>
 
:<math>
 
\begin{array}{clcll}
 
\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}
 
\end{array}
 
</math>
 
</math>
72行目: 65行目:
 
次に,[[ラグランジュ関数]] (Lagrangian function) を
 
次に,[[ラグランジュ関数]] (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,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u\,\}</math>
 +
    <math>\mbox{(3)}\,<\math>
  
  
と定義する.<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>
\end{equation}</math>
 
  
  

2007年6月29日 (金) 11:41時点における版

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

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

 「双対」 (dual) と「共役」 (conjugate) は元々同義語として用いられ,数学の関数解析の分野では,ノルム空間 上の有界線形汎関数の全体を の双対空間 (dual space) または共役空間 (conjugate space) といい, と表して, における の値を または と書く. 次元実ユークリッド空間 の場合は, は同一視でき, となり, の内積 となる.以下に述べる事柄は,無限次元空間に対しても拡張できるが,ここでは簡単のため に限定して説明する.

 空間 上で定義された拡張実数値関数 に対して(ただし,),



で定義される関数 の共役関数 (conjugate function) という.共役関数 に対して,さらにその共役関数 を考えることができるが, が下半連続な真凸関数のときには, に一致する. を対応させる写像をルジャンドル-フェンシェル変換 (Legendre-Fenchel transform) と呼ぶ.

 下半連続な真凸関数 に対して,関数 をそれぞれ で定義し,次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [1, 4].



また,



とおくと, は凸集合となる.このとき,以下が成立する.


(i)

(ii) または


ここで, の内部を表す.(i)を弱双対定理 (weak duality theorem),(ii)を双対定理 (duality theorem) と呼び, が満たされるとき,主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという.(i)により, なら主問題(P)は実行可能解を持たないが, となる が存在すれば,それぞれ(P)と(D)の最適解となり,強い意味の双対性が成立する.一方, となるとき,主問題と双対問題の間に双対性のギャップ (duality gap) が存在するという.

 主問題(P)において,(ただし, は下半連続な真凸関数で, , )とすると,となり [4],主問題(P)と双対問題(D)はそれぞれ



となる.ここで または が成立すれば,(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する.(ただし,dom は拡張実数値関数の実効定義域を表す.)これをフェンシェルの双対性 (Fenchel duality) と呼んでいる.通常は,簡略化して を零ベクトル, を恒等写像として,新たに を凸関数 と凹関数 の差で表し,主問題 に対して, をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ.ただし,.双対性は のとき成立する.また, とすると,(1) と(2) は線形計画の主問題と双対問題となる [2, 4].



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


    構文解析に失敗 (不明な関数「\math」): {\displaystyle \mbox{(3)}\,<\math> と定義する.<math>-L(x,\cdot)=(f(x,\cdot))^{*}, f(x,\cdot)=(-L(x,\cdot))^{*}} が成立しているので,

    構文解析に失敗 (不明な関数「\math」): {\displaystyle \mbox{(4)}\,<\math> となる.通常,<math>\inf_{x}L(x,\bar{y})=L(\bar{x},\bar{y})=\sup_{y}L(\bar{x},y)} すなわち,すべての に対してが成り立つとき, を関数 上での鞍点 (saddle point) と呼ぶ.(4) により,


構文解析に失敗 (不明な関数「\medskip」): {\displaystyle \medskip \noindent (iii) \ \inf_{x}\varphi{(x)}=\inf_{x}\,[\,\sup_{y}L(x,y)\,] \ge\sup_{y}\,[\,\inf_{x}L(x,y)\,]=\sup_{y}\psi{(y)} \\ (iv) \ \varphi{(\bar{x})}=\inf_{x}\varphi{(x)} =\sup_{y}\psi{(y)}=\psi{(\bar{y})} \Longleftrightarrow (\bar{x},\bar{y}) が L の鞍点 \\ \hspace*{1cm} \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})} \medskip \noindent }


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

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


(ただし, で定義された実数値関数,) に対して,


構文解析に失敗 (不明な関数「\begin{center}」): {\displaystyle \begin{center} \begin{tabular}{r@{}l} 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{tabular} \end{center} }


とおくと,(3) により となり,に対する問題(NLP)のラグランジュ関数は


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


となる.この をラグランジュ乗数 (Lagrange multipliers) と呼ぶ.このとき,主問題と双対問題は


構文解析に失敗 (不明な関数「\begin{center}」): {\displaystyle \begin{center} \begin{tabular}{cllll} (P_{L}) & min. & \displaystyle \sup_{\lambda\ge{0},\mu} L(x, \lambda, \mu) & s. t. & \displaystyle{x \in {\mathbf{R}^n}}, \\ (D_{L}) & max. & \displaystyle \inf_{x} L(x,\lambda,\mu) & s. t. & \displaystyle{0 \le \lambda \in {\mathbf{R}^{k}}}, \ \displaystyle \mu \in {\mathbf{R}^{l}}, \end{tabular} \end{center} }


となり,一般に問題(D_{L})をラグランジュの双対問題 (Lagrangian dual problem)と呼ぶ.鞍点定理により, の鞍点 が存在すれば,つまり



が成立すれば, はそれぞれ問題(P)と(D)の最適解となり最適値が一致する.これをラグランジュの双対性 (Lagrangian duality) と呼ぶ.(iv)により, が成立すれば,この双対性が保証される.この等式に対する十分条件を述べた定理をミニマックス定理(minimax theorem) と呼ぶ [1]. 逆に,主問題の目的関数 と制約関数 がすべて凸で, がすべてアフィン関数であるような凸計画問題 (convex programming problem) においては,適当な条件のもとで,問題(P)の最適解 に対して, であるようなラグランジュ乗数 が存在して, がラグランジュ関数 の鞍点となる.さらに,次のような拡張ラグランジュ関数(augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4].



ただし, は正定数, に対して を満足する下半連続な真凸関数である.関数 の例としては などがある.



参考文献

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