はじめに #
本記事では、最適化でよく用いられる双対問題についてまとめた。 また、サポートベクターマシンにおける双対問題についても少し触れている。
線形計画問題の標準形 #
まず、以下の制約付き線形計画問題を考える。
$$ \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では線形計画問題ではなく二次計画問題となる。
参考 #
以下のページを参考にさせて頂いた。
