Helve’s Python memo

Pythonを使った機械学習や最適化の備忘録

線形計画問題と双対問題

本記事では、最適化でよく用いられる双対問題についてまとめた。
また、サポートベクターマシンにおける双対問題についても少し触れている。

目次

線形計画問題の標準形

まず、以下の制約付き線形計画問題を考える。
\begin{align}
& \mathrm{min} \ f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} \\
& \mathrm{s.t.}\ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0}
\end{align}

ここで、  \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}をスラック変数と呼ぶ。

双対問題

先程の線形計画問題
\begin{align}
& \mathrm{min} \ f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} \\
& \mathrm{s.t.}\ A\boldsymbol{x}=\boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0}
\end{align}

に対して、双対問題 (dual problem) は以下で与えられる。
\begin{align}
& \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}
\end{align}

ここで、 \boldsymbol{y} \in \mathbb{R}^m, \boldsymbol{z} \in \mathbb{R}^mである。

双対問題に対し、元の問題を主問題 (primal problem) と呼ぶ。

双対問題は主問題と密接な関係にあり、その関係を双対性 (duality) と呼ぶ。

弱双対定理

主問題と双対問題の目的関数について、以下の弱双対定理が成り立つ。

弱双対定理
 \boldsymbol{x}, \boldsymbol{y}がそれぞれ主問題と双対問題の実行可能解であるとき、以下の不等式が成り立つ。

\begin{align}
f_p(\boldsymbol{x}) = \boldsymbol{c}^{\top} \boldsymbol{x} \ge
\boldsymbol{b}^{\top} \boldsymbol{y} = f_d(\boldsymbol{y})
\end{align}

[証明]
 \boldsymbol{x}, \boldsymbol{y}は実行可能解であるから、

\begin{align}
\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{align}

よって、
\begin{align}
\boldsymbol{c}^{\top} \boldsymbol{x} \ge \boldsymbol{b}^{\top} \boldsymbol{y}
\end{align}
が成り立つ。■

また、主問題と双対問題の目的関数の差
 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では線形計画問題ではなく二次計画問題となる。

参考

以下のページ・書籍を参考にさせて頂いた。

双対定理 - 数理計画用語集