双対性理論

【そうついせいりろん (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) といい，$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 x^{*}\in{X^*}\,} の値を$\langle x,x^{*}\rangle \,$ または $x^{*}(x)\,$ と書く．$X\,$ が $n\,$ 次元実ユークリッド空間 $\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}$ は同一視でき，$(\mathbf {R} ^{n})^{**}=\mathbf {R} ^{n}$ となり，$\langle x,x^{*}\rangle$ は$x\,$ と $x^{*}\,$ の内積 $x^{\top }x^{*}\,$ となる．以下に述べる事柄は，無限次元空間に対しても拡張できるが，ここでは簡単のため $\mathbf {R} ^{n}\,$ に限定して説明する．

　空間 $\mathbf {R} ^{n}$ 上で定義された拡張実数値関数 $f:\mathbf {R} ^{n}\to {\bar {\mathbf {R} }}$ に対して(ただし，${\bar {\mathbf {R} }}=\mathbf {R} \cup \{\infty ,-\infty \}$)，

$f^{*}(\xi ):=\sup _{x\in {\mathbf {R} ^{n}}}\{\,\xi ^{\top }x-f(x)\,\}$

で定義される関数 $f^{*}\,$ を $f\,$ の共役関数 (conjugate function) という．共役関数 $f^{*}\,$ に対して，さらにその共役関数 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle f^{**}=(f^{*})^{*}\,} を考えることができるが，$f\,$ が下半連続な真凸関数のときには，$f^{**}\,$ は $f\,$ に一致する．$f\,$ に $f^{*}\,$ を対応させる写像をルジャンドル-フェンシェル変換 (Legendre-Fenchel transform) と呼ぶ．

　下半連続な真凸関数 $f:\mathbf {R} ^{n}\times {\mathbf {R} ^{m}}\to {\bar {\mathbf {R} }}\,$に対して，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [4]．

${\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}}$

また，

$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 \}$

とおくと，$U\,$ と $V\,$ は凸集合となる．このとき，以下が成立する．

${\mbox{(i)}}\,$ ${\mbox{inf}}_{x}\varphi {(x)}\geq {\mbox{sup}}_{y}\psi {(y)}$

${\mbox{(ii)}}\,$ $0\in {{\mbox{int}}\,U}\;$ または $\;0\in {{\mbox{int}}\,V}\Longrightarrow {\mbox{inf}}_{x}\varphi {(x)}={\mbox{sup}}_{y}\psi {(y)}$

ここで，${\mbox{int}}\,U$ は $U\,$ の内部を表す．(i)を弱双対定理 (weak duality theorem)，(ii)を双対定理 (duality theorem) と呼び，構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{inf}}_{x}\varphi {(x)}={\mbox{sup}}_{y}\psi {(y)}} が満たされるとき，主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという．(i)により，${\mbox{sup}}_{y}\psi {(y)}=+\infty$ なら主問題(P)は実行可能解を持たないが，$-\infty <\varphi {({\bar {x}})}=\psi {({\bar {y}})}<+\infty$ となる ${\bar {x}}$ と ${\bar {y}}$ が存在すれば，それぞれ(P)と(D)の最適解となり，強い意味の双対性が成立する．一方，構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{inf}}_{x}\varphi {(x)}>{\mbox{sup}}_{y}\psi {(y)}} となるとき，主問題と双対問題の間に双対性のギャップ (duality gap) が存在するという．

　主問題(P)において，$f(x,u):=c^{\top }x+k(x)+h(b-Ax+u)$（ただし，構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k:\mathbf {R} ^{n}\to {\bar {\mathbf {R} }}} と $h:\mathbf {R} ^{m}\to {\bar {\mathbf {R} }}$ は下半連続な真凸関数で$A\in {\mathbf {R} ^{m\times {n}}}$, $b\in {\mathbf {R} ^{m}}$, $c\in {\mathbf {R} ^{n}}$ ）とすると，$f^{*}(v,y)=-b^{\top }y+h^{*}(y)+k^{*}(A^{\top }y-c+v)$となり [4]，主問題(P)と双対問題(D)はそれぞれ

${\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}}$

となる．ここで$b\in {\mbox{int}}\,(A{\mbox{dom}}k+{\mbox{dom}}h)\,$ または$c\in {\mbox{int}}\,(A^{\top }{\mbox{dom}}h^{*}-{\mbox{dom}}k^{*})\,$ が成立すれば，(ii)により主問題 (1) と双対問題 (2) の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これをフェンシェルの双対性 (Fenchel duality) と呼んでいる．通常は，簡略化して $c\,$ と $b\,$ を零ベクトル，$-A\,$ を恒等写像として，新たに$f(x)\,$ を凸関数 $f_{1}(x):=k(x)\,$ と凹関数 $f_{2}(x):=-h(x)\,$ の差で表し，主問題 ${\mbox{min}}_{x}\{f_{1}(x)-f_{2}(x)\}\,$に対して，構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{max}}_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}} をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，$f_{2}^{*}(y):={\mbox{inf}}_{x\in {\mathbf {R} ^{n}}}\{y^{\top }x-f_{2}(x)\}$．双対性は ${\mbox{int}}\,({\mbox{dom}}f_{1})\,\cap \,{\mbox{int}}\,({\mbox{dom}}f_{2})\neq \emptyset$ のとき成立する．また，構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k(x):={\mbox{sup}}_{s\leq {0}}x^{\top }s,h(z):={\mbox{sup}}_{w\geq {0}}z^{\top }w} とすると，(1) と(2) は線形計画の主問題と双対問題となる [2, 4]．

${\begin{array}{clcll}({\mbox{P}}_{LP})&{\mbox{min.}}&c^{\top }x&s.t.&x\geq {0},\ Ax\geq {b}.\\({\mbox{D}}_{LP})&{\mbox{max.}}&b^{\top }y&s.t.&y\geq {0},\ A^{\top }y\leq {c}.\end{array}}$

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

$L(x,y):=\inf _{u\in {\mathbf {R} ^{m}}}\{\,f(x,u)-y^{\top }u\,\}$

$(3)\,$

　　　　

と定義する．$-L(x,\cdot )=(f(x,\cdot ))^{*},f(x,\cdot )=(-L(x,\cdot ))^{*}$が成立しているので，

$\varphi {(x)}=\sup _{y}L(x,y),\quad \quad \psi {(y)}=\inf _{x}L(x,y)$

$(4)\,$

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

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mbox{(iii)}}\,} ${\mbox{inf}}_{x}\varphi {(x)}={\mbox{inf}}_{x}\,[\,{\mbox{sup}}_{y}L(x,y)\,]\geq {\mbox{sup}}_{y}\,[\,{\mbox{inf}}_{x}L(x,y)\,]={\mbox{sup}}_{y}\psi {(y)}$

${\mbox{(iv)}}\,$ 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \varphi {({\bar {x}})}={\mbox{inf}}_{x}\varphi {(x)}={\mbox{sup}}_{y}\psi {(y)}=\psi {({\bar {y}})}\Longleftrightarrow ({\bar {x}},{\bar {y}})} が$L\,$の鞍点

$\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) と呼ぶ．非線形計画問題

${\mbox{(NLP)}}\;\;{\mbox{min.}}\ f_{0}(x)\quad {\mbox{s. t.}}\;\;g_{i}(x)\leq {0}\ (i=1,\ldots ,k),\;\;h_{j}(x)=0\ (j=1,\ldots ,l),$

(ただし，$f_{0},g_{i},h_{j}$ は $\mathbf {R} ^{n}$ で定義された実数値関数，$k+l=m$) に対して，

${\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) により構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y=(\lambda ,\mu )=(\lambda _{1},\ldots ,\lambda _{k},\mu _{1},\ldots ,\mu _{l})\in {\mathbf {R} _{+}^{k}\times {\mathbf {R} ^{l}}}} に対する問題(NLP)のラグランジュ関数は

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

$(5)\,$

となる．この $(\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} }

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

構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \max _{\lambda \geq {0},\mu }L({\bar {x}},\lambda ,\mu )=L({\bar {x}},{\bar {\lambda }},{\bar {\mu }})=\min _{x}L(x,{\bar {\lambda }},{\bar {\mu }})}

が成立すれば，${\bar {x}}$ と 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{\lambda},\bar{\mu})} はそれぞれ問題$({\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\, } と制約関数 $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 \bar{L}(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)+r\sigma{(u)}-y^{\top}u\,\}}

ただし，構文解析に失敗 (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 u\neq{0}\,} に対して 構文解析に失敗 (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.