双対性理論

そうついせいりろん}{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{center} \begin{tabular}{cll} (P) & $\min_{x\in \mathbf{R}^n}$ & \hspace*{-5mm} $\varphi{(x)}$ \\ (D) & $\max_{y\in \mathbf{R}^m}$ & \hspace*{-5mm} $\psi{(y)}$ \end{tabular} \end{center}

また，

 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$ は凸集合となる．このとき，以下が成立する．

\medskip \noindent (i) \ $\inf_{x}\varphi{(x)}\ge\sup_{y}\psi{(y)}$ \\ (ii) \ $0\in{\mbox{\rm int}\,U}\; または \; 0\in{\mbox{\rm int}\,V}

       \Longrightarrow\inf_{x}\varphi{(x)}=\sup_{y}\psi{(y)}$

ここで，$\mbox{\rm int}\,U$ は $U$ の内部を表す．(i)を弱双対定理 (weak duality theorem)，(ii)を双対定理 (duality theorem) と呼び，$\inf_{x}\varphi{(x)}=\sup_{y}\psi{(y)}$ が満たされるとき，主問題(P)と双対問題(D)の間に双対性 (duality) が成立するという．(i)により，$\sup_{y}\psi{(y)}=+\infty$ なら主問題(P)は実行可能解を持たないが，$-\infty<\varphi{(\bar{x})}=\psi{(\bar{y})}<+\infty$ となる $\bar{x}$ と $\bar{y}$ が存在すれば，それぞれ(P)と(D)の最適解となり，強い意味の双対性が成立する．一方，$\inf_{x}\varphi{(x)}>\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)$となり \cite{[4]}，主問題(P)と双対問題(D)はそれぞれ

\begin{eqnarray} \mbox{\rm min}_{x\in \mathbf{R}^n} && \hspace*{-5mm} c^{\top}x+k(x)+h(b-Ax)

       \label{A-B-03+siki1}\\

\mbox{\rm max}_{y\in \mathbf{R}^m} && \hspace*{-5mm} b^{\top}y-h^{*}(y)-k^{*}(A^{\top}y-c)

       \label{A-B-03+siki2}

\end{eqnarray}

となる．ここで$b\in\mbox{\rm int}\,(A\mbox{\rm dom}k+\mbox{\rm dom}h)$ または$c\in\mbox{\rm int}\,(A^{\top}\mbox{\rm dom}h^{*}-\mbox{\rm dom}k^{*})$ が成立すれば，(ii)により主問題(\ref{A-B-03+siki1})と双対問題(\ref{A-B-03+siki2})の間に双対性が成立する．（ただし，dom は拡張実数値関数の実効定義域を表す．）これをフェンシェルの双対性 (Fenchel duality) と呼んでいる．通常は，簡略化して $c$ と $b$ を零ベクトル，$-A$ を恒等写像として，新たに$f(x)$ を凸関数 $f_1(x):=k(x)$ と凹関数 $f_2(x):=-h(x)$ の差で表し，主問題 $\min_{x}\{f_1(x)-f_2(x)\}$に対して，$\max_{y}\{f_{2}^{*}(y)-f_{1}^{*}(y)\}$ をフェンシェルの双対問題 (Fenchel dual problem) と呼ぶ．ただし，$f_{2}^{*}(y):=\inf_{x\in{\mathbf{R}^n}}\{y^{\top}x-f_{2}(x)\}$．双対性は $\mbox{\rm int}\,(\mbox{\rm dom}f_1)\,\cap\, \mbox{\rm int}\,(\mbox{\rm dom}f_2)\neq\emptyset$ のとき成立する．また，$k(x):=\sup_{s\le{0}}x^{\top}s$, $h(z):=\sup_{w\ge{0}}z^{\top}w$ とすると，(\ref{A-B-03+siki1})と(\ref{A-B-03+siki2})は線形計画の主問題と双対問題となる \cite{A-B-03-c,[4]}．

\begin{center} \begin{tabular}{clcll} (P$_{LP}$) & 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}.$ \end{tabular} \end{center}

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

\begin{equation} \label{A-B-03+siki3} L(x,y):=\inf_{u\in{\mathbf{R}^m}}\{\, f(x,u)-y^{\top}u \,\} \end{equation}

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

\begin{equation} \label{A-B-03+siki4} \varphi{(x)}=\sup_{y}L(x,y), \quad\quad \psi{(y)}=\inf_{x}L(x,y) \end{equation}

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

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

\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),

(ただし，$f_0,g_i,h_j$ は $\mathbf{R}^n$ で定義された実数値関数，$k+l=m$)に対して，

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

とおくと，(\ref{A-B-03+siki3})により$L(x,y)=f_{0}(x)+y^{T}F(x)-\theta^{*}(y)$ となり，$y=(\lambda,\mu)=(\lambda_{1},\ldots,\lambda_{k},\mu_{1},\ldots,\mu_{l}) \in{\mathbf{R}^{k}_{+}\times{\mathbf{R}^{l}}}$に対する問題(NLP)のラグランジュ関数は

\begin{equation} \label{A-B-03+siki5} 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}

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

\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)と呼ぶ．鞍点定理により，$L$ の鞍点 $(\bar{x},\bar{\lambda},\bar{\mu})$ が存在すれば，つまり

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

が成立すれば，$\bar{x}$ と $(\bar{\lambda},\bar{\mu})$ はそれぞれ問題(P$_{L}$)と(D$_{L}$)の最適解となり最適値が一致する．これをラグランジュの双対性 (Lagrangian duality) と呼ぶ．(iv)により，$\min_{x}\sup_{y}L(x,y)=\max_{y}\inf_{x}L(x,y)$ が成立すれば，この双対性が保証される．この等式に対する十分条件を述べた定理をミニマックス定理(minimax theorem) と呼ぶ [1]． 逆に，主問題の目的関数 $f_0$ と制約関数 $g_i$ がすべて凸で，$h_j$ がすべてアフィン関数であるような凸計画問題 (convex programming problem) においては，適当な条件のもとで，問題(P$_{L}$)の最適解 $\bar{x}$ に対して，$\bar{\lambda}\ge{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.