双対定理#

読み: そうついていり
英名: Duality Theorem

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

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

に対し，凸関数 \(F \colon \mathbb{R}^{n+m} \to \mathbb{R}\) を \(F(x,\bullet)\) が閉真凸で次を満たすものとする．

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

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

共役関数とは次で定義される関数である．

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

そして \(\varphi^*\) を用いて主問題 (P) の双対問題を次のように構成する．

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

双対問題 (D) の目的関数は次である．

(80)#\[-\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\) を次とした場合の双対問題は，特にラグランジュ双対問題と呼ばれる．

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

こう呼ばれる所以は，この場合の拡張ラグランジュ関数は次の形になり，よく慣れ親しまれているラグランジュ関数に他ならないからである．

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

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

以後，下記のような主問題 (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\) とする．

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

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

問題 (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^*\) が成り立ち，これを双対定理と呼ぶ．