はじめに
本記事では、最適化でよく用いられる双対問題についてまとめた。
また、サポートベクターマシンにおける双対問題についても少し触れている。
線形計画問題の標準形
まず、以下の制約付き線形計画問題を考える。
$ \mathrm{min} \ f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} $
$ \mathrm{s.t.}\ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0} $
ここで、$ \boldsymbol{x} \in \mathbb{R}^n, A\in \mathbb{R}^{n\times m}, \boldsymbol{b} \in \mathbb{R}^m, \boldsymbol{c} \in \mathbb{R}^n$である。
上記の形は、線形計画問題の標準形と呼ばれる。
また、問題に不等式制約が含まれる場合にも、標準形に変換することが出来る。例えば、
$ A\boldsymbol{x} \le \boldsymbol{b}$
なる不等式制約があるとき、新たに変数$ \boldsymbol{y} \ge \boldsymbol{0}$を導入して、
$ A\boldsymbol{x}+ \boldsymbol{y} =\boldsymbol{b}$
とできる。この$ \boldsymbol{y}$をスラック変数と呼ぶ。
双対問題
先程の線形計画問題
$ \mathrm{min} \ f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} $
$ \mathrm{s.t.}\ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0} $
に対して、双対問題 (dual problem) は以下で与えられる。
$ \mathrm{max} \ f_d(\boldsymbol{y}) = \boldsymbol{b}^{\top} \boldsymbol{y} $
$ \mathrm{s.t.}\ A^{\top} \boldsymbol{y}+\boldsymbol{z} =\boldsymbol{c}, \boldsymbol{z} \ge \boldsymbol{0} $
ここで、$ \boldsymbol{y} \in \mathbb{R}^m, \boldsymbol{z} \in \mathbb{R}^m$である。
双対問題に対し、元の問題を主問題 (primal problem) と呼ぶ。
双対問題は主問題と密接な関係にあり、その関係を双対性 (duality) と呼ぶ。
弱双対定理
主問題と双対問題の目的関数について、以下の弱双対定理が成り立つ。
弱双対定理
$ \boldsymbol{x}, \boldsymbol{y}$がそれぞれ主問題と双対問題の実行可能解であるとき、以下の不等式が成り立つ。
$f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} \ge \boldsymbol{b}^{\top} \boldsymbol{y} = f_d(\boldsymbol{y}) $
[証明]
$ \boldsymbol{x}, \boldsymbol{y}$は実行可能解であるから、
$$ \begin{array}{rl} \boldsymbol{c}^{\top} \boldsymbol{x} - \boldsymbol{b}^{\top} \boldsymbol{y} &= (A^{\top} \boldsymbol{y}+\boldsymbol{z})^{\top} \boldsymbol{x} - (A\boldsymbol{x})^{\top} \boldsymbol{y} \\ &= (\boldsymbol{y}^{\top} A + \boldsymbol{z}^{\top})\boldsymbol{x} - (\boldsymbol{x}^{\top} A^{\top}) \boldsymbol{y} \\ &= \boldsymbol{y}^{\top} A \boldsymbol{x} + \boldsymbol{z}^{\top} \boldsymbol{x} - \boldsymbol{x}^{\top} A^{\top} \boldsymbol{y} \\ &= \boldsymbol{z}^{\top}\boldsymbol{x} \\ &\ge 0 \end{array} $$
よって、
$$ \boldsymbol{c}^{\top} \boldsymbol{x} \ge \boldsymbol{b}^{\top} \boldsymbol{y} $$
が成り立つ。■
また、主問題と双対問題の目的関数の差
$ f_p(\boldsymbol{x}) - f_d(\boldsymbol{y}) = \boldsymbol{c}^{\top} \boldsymbol{x} - \boldsymbol{b}^{\top} \boldsymbol{y} $
を双対ギャップと呼ぶ。
双対定理
主問題と双対問題について、以下の双対定理が成り立つ（証明は省略）。
双対定理
主問題と双対問題のいずれか一方が最適解を持つなら、もう一方も最適解を持ち、主問題の最小値と双対問題の最大値は一致する。
すなわち、
$ \boldsymbol{c}^{\top} \boldsymbol{x} = \boldsymbol{b}^{\top} \boldsymbol{y}$
が成り立つならば、$ \boldsymbol{x}, \boldsymbol{y} $はそれぞれ主問題と双対問題の最適解である。
したがって、双対問題を解くことで、主問題の最適解を求めることが出来る。
サポートベクターマシンと双対定理
サポートベクターマシン (SVM) では、以下の2つの利点により双対定理が利用されている。
- 双対問題ではカーネルトリックを利用でき、非線形な分類が可能になる
- 訓練データ数が次元数より少ない場合、計算が高速になる
2つ目の利点を補足すると、主問題の最適化変数の次元をn, 等式制約の数をmとすると、双対問題では最適化変数の次元がm, 等式制約の数がnと入れ替わる。よって、n»mであれば、双対問題を解く方が計算が速くなる。
ただし、SVMでは線形計画問題ではなく二次計画問題となる。
参考
以下のページ・書籍を参考にさせて頂いた。
双対定理 - 数理計画用語集
