双対定理

読み：そうついていり
英名：Duality Theorem
関連：主問題，双対問題

$f \colon \mathbb{R}^n \to \mathbb{R}, \ g_i \colon \mathbb{R}^m \to \mathbb{R} \ (i=1,\ldots,m)$ を凸関数とし，次の凸計画問題 (P) を考える．

$$ (P) \left| \begin{array}{ll} \min & f(x) \\ \mathrm{s.t.} & g_i(x) \le 0 \ (i=1,\ldots,m). \end{array} \right. $$

16. に対し，凸関数 $F \colon \mathbb{R}^{n+m} \to \mathbb{R}$ を $F(x,\bullet)$ が閉真凸で

$$ F(x,0)= \left\{ \begin{array}{ll} f(x), & g_i(x) \le 0 \ (i=1,\ldots,m) \\ +\infty, & \text{上記以外の場合} \end{array} \right. $$

を満たすものとし，$\varphi(u)=\inf\{ F(x,u) \mid x \in \mathbb{R}^n \}$ とおく．すると，$\varphi$ は凸関数であり，(P) の下限値は $\varphi(0)$ となる．ここで，関数 $\varphi$ の共役関数を $\varphi^*$ で表す．共役関数とは

$$ \varphi^*(\lambda)=\inf\{ \alpha \mid \lambda^\top u - \alpha \le \varphi(u), u \in \mathbb{R}^m, \alpha \in \mathbb{R} \} $$

で定義される関数である．$\varphi^*$ を用いて主問題 (P) の双対問題を次のように構成する．

$$ (D) \left| \begin{array}{ll} \max & -\varphi^*(-\lambda) \\ \mathrm{s.t.} & \lambda \in \mathbb{R}^m. \end{array} \right. $$

双対問題 (D) の目的関数は

$$ -\varphi^*(-\lambda)=\sup\{ -\alpha \mid -\lambda^\top u - \alpha \le \varphi(u), u \in \mathbb{R}^m, \alpha \in \mathbb{R} \} $$

であるから，双対問題 (D) は $h(u) \le \varphi(u)$ をみたすアフィン関数 $h(u) = -\lambda^\top u - \alpha$ のうち，原点での値 $h(0)$ を最大化するようなアフィン関数の勾配を決定する問題といえる．

故に，$\inf(P) = \varphi(0) \ge \sup(D)$ が成り立ち，これを弱双対定理と呼ぶ．不等式 $\inf(P) \ge \sup(D)$ において，等号が成り立たないとき，双対ギャップがあるという．

以下，簡単に，双対ギャップが消えるための条件を述べる．簡単な計算から $\sup(D) = \varphi^{**}(0)$ となるので，$\varphi(0) = \varphi^{**}(0)$ は双対ギャップが消えることの必要十分条件であり，この事実を双対定理と呼ぶ．

例えば，$\varphi$ が閉真凸ならば $\varphi = \varphi^{**}$ となるので，双対ギャップは消える．また，双対問題の定義から，$\varphi$ の原点において劣勾配が存在することと，双対問題 (D) に最適解が存在して $\inf(P) = \max(D)$ となることが同値であることも感覚的に分かるであろう．更に，$\varphi$ の原点における劣勾配は双対問題 (D) の最適解を与える．即ち，$\left\{ \lambda \middle| -\varphi^*(-\lambda) = \max(D) \right\}$ は $\varphi$ の原点での劣微分に他ならない．

双対問題 (D) の目的関数は，拡張ラグランジュ関数と呼ばれる関数 $L(x,\lambda) = \inf \left\{ F(x,u) + \lambda^\top u \middle| u \right\}$ を用いて $\inf \left\{ L(x,\lambda) \middle| x \right\}$ と定義することもあるが，これは $-\varphi^*(-\lambda)$ と一致することを注意しておく．

双対問題は凸関数 $F$ の取り方により，その形は様々であるが，$F$ を

$$ F(x,u)= \left\{ \begin{array}{ll} f(x), & g_i(x) \le u \ (i=1,\ldots,m) \\ +\infty, & \text{上記以外の場合} \end{array} \right. $$

とした場合の双対問題は，特にラグランジュ双対問題と呼ばれる．こう呼ばれる所以は，この場合の拡張ラグランジュ関数は

$$ L(x,\lambda)= \left\{ \begin{array}{ll} f(x) + \sum_i{\lambda_i g_i(x)}, & \lambda \ge 0\\ -\infty, & \text{上記以外の場合} \end{array} \right. $$

という形になり，よく慣れ親しまれているラグランジュ関数に他ならないからである．

最後に主問題が線形計画問題だった場合の弱双対定理，双対定理について触れておく．

以後，下記のような主問題 (P) と双対問題 (D) を考える．ただし，$c \in \mathbb{R}^n, b \in \mathbb{R}^m, A (m \times n \ \text{行列})$ とし，変数 $x,w$ は $x \in \mathbb{R}^n, w \in \mathbb{R}^m$ とする．

$$ (P) \left| \begin{array}{ll} \min & c^\top x \\ \mathrm{s.t.} & Ax = b, \ x \ge 0, \end{array} \right. $$

$$ (D) \left| \begin{array}{ll} \max & b^\top w \\ \mathrm{s.t.} & A^\top w \le c. \end{array} \right. $$

問題 (P)，(D) の任意の実行可能解 $x,w$ に対し，$c^\top x \ge b^\top w$ が常に成立し，これを弱双対定理と呼ぶ．

また，問題 (P)，(D) に関して，いずれか一方の問題が最適解をもつならば他方の問題も最適解をもち，それらの値が等しくなるという性質がある．即ち，問題 (P)，(D) 各々の最適解が存在するとして，(P) の最適解を $x^*$，(D)の最適解を $w^*$ とおくと，問題 (P) の最小値 $c^\top x^*$ と問題 (D) の最大値 $b^\top w^*$ との間に $c^\top x^* = b^\top w^*$ が成り立ち，これを双対定理と呼ぶ．

[参考]
今野 浩，山下 浩，非線形計画法，日科技連，1978
福島 雅夫，非線形最適化の基礎，朝倉書店，2001