双対性理論

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

概要

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

詳説

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

　「双対」 (dual) と「共役」 (conjugate) は元々同義語として用いられ，数学の関数解析の分野では，ノルム空間 $X\,$ 上の有界線形汎関数の全体を$X\,$ の双対空間 (dual space) または共役空間 (conjugate space) といい，$X^{*}\,$ と表して，$x\in {X}\,$ における $x^{*}\in {X^{*}}\,$ の値を$\langle x,x^{*}\rangle \,$ または $x^{*}(x)\,$ と書く．$X\,$ が $n\,$ 次元実ユークリッド空間 $\mathbf {R} ^{n}$ の場合は，$(\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^{*}\,$ に対して，さらにその共役関数 $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) と呼び，${\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)の最適解となり，強い意味の双対性が成立する．一方，${\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)$（ただし，$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)\}\,$に対して，${\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$ のとき成立する．また，$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) により，

${\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)}}\,$ $\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) により$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) と呼ぶ．このとき，主問題と双対問題は

${\begin{array}{cllll}({\mbox{P}}_{L})&{\mbox{min.}}&\displaystyle \sup _{\lambda \geq {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\leq \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 }})$ が存在すれば，つまり

$\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}}$ と $({\bar {\lambda }},{\bar {\mu }})$ はそれぞれ問題$({\mbox{P}}_{L})\,$と$({\mbox{D}}_{L})\,$の最適解となり最適値が一致する．これをラグランジュの双対性 (Lagrangian duality) と呼ぶ．(iv) により，${\mbox{min}}_{x}{\mbox{sup}}_{y}L(x,y)={\mbox{max}}_{y}{\mbox{inf}}_{x}L(x,y)\,$ が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理をミニマックス定理(minimax theorem) と呼ぶ [1, 2]． 逆に，主問題の目的関数 $f_{0}\,$ と制約関数 $g_{i}\,$ がすべて凸で，$h_{j}\,$ がすべてアフィン関数であるような凸計画問題 (convex programming problem) においては，適当な条件のもとで，問題$({\mbox{P}}_{L})\,$の最適解 ${\bar {x}}$ に対して，${\bar {\lambda }}\geq {0}$ であるようなラグランジュ乗数 $({\bar {\lambda }},{\bar {\mu }})$ が存在して，$({\bar {x}},{\bar {\lambda }},{\bar {\mu }})$ がラグランジュ関数 $L\,$ の鞍点となる．また，次のような拡張ラグランジュ関数(augmented Lagrangian function) に基づく双対性も考えられている [2, 3, 4]．

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

ただし，$r\,$ は正定数，$\sigma :\mathbf {R} ^{m}\rightarrow {\bar {\mathbf {R} }}\,$ は $u\neq {0}\,$ に対して $0=\sigma {(0)}<\sigma {(u)}\,$ を満足する下半連続な真凸関数である．関数 $\sigma \,$ の例としては $\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.