双対性理論

【そうついせいりろん (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} }}\,$に対して，関数 $\varphi :\mathbf {R} ^{n}\to {\bar {\mathbf {R} }}\,$ と $\psi :\mathbf {R} ^{m}\to {\bar {\mathbf {R} }}\,$ をそれぞれ $\varphi {(x)}:=f(x,0)\,$ と $\psi {(y)}:=-f^{*}(0,y)\,$ で定義し，次の問題(P)と(D)を主問題 (primal problem) とその双対問題 (dual problem) と呼ぶ [1, 4]．

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

また，

$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)&&{\mbox{(1)}}\\\\{\mbox{max}}_{y\in \mathbf {R} ^{m}}&b^{\top }y-h^{*}(y)-k^{*}(A^{\top }y-c)&&{\mbox{(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\,\}$　　　　${\mbox{(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)$　　　　${\mbox{(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)$　　　　${\mbox{(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]． 逆に，主問題の目的関数 $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}\,$ などがある．

---

参考文献

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