この記事では、サポートベクターマシン(Support Vector Machine。以下、SVM)の最適化問題の定式化で用いる、Lagrange双対の理論について、必要な結果をまとめておきます。
元々はSVMの実装を行う記事に書いていたのですが、長くなったので分離することにしました。
なお、この記事の内容は
- 茨木俊秀(2011)「最適化の数学 (共立講座 21世紀の数学 13)」共立出版
の2章に基づきます。
結果だけ知りたい方は、1の問題の定義と、2での$L$の定義式、3での$q$の定義式、後は5の結果を見ていただければ大丈夫です。
1 最適化問題
ここでは、次の形の最適化問題を考えます1。
- 目的関数：$f : \mathbb{R}^n \rightarrow \mathbb{R}$
- 拘束条件を表す関数: $g_i : \mathbb{R}^n \rightarrow \mathbb{R}$ $(i \in \{ 0, \dots, m-1 \})$
$$
\begin{align}
& \min_{x \in S} f(x) \
& S := \left\{ x \in \mathbb{R}^d \middle| g_i(x) \geq 0 \ \forall i \in \{ 0, \dots, m-1 \} \right\}
\end{align}
$$
2 Lagrangian
この最適化問題に対し、Lagrangian $L : \mathbb{R}^n \times \mathbb{R}_{+}^{m} \rightarrow \mathbb{R}$を次のように定義します($\mathbb{R}_{+}$は非負実数の集合を現します。)：
$$
\begin{align}
L(x,\lambda) := f(x) - \sum_{i=0}^{m-1} \lambda_i g_i(x),
\end{align}
$$
このLagrangianを用いて、元の$x$についての最小化問題を、$\lambda$についての最大化問題に書き直します。
3 双対問題
まず、Lagrangianから以下のような関数を定義します：
$$
\begin{align}
F(x) &:= \sup_{\lambda \in \mathbb{R}_{+}^{m}} L(x,\lambda)
\end{align}
$$
すると、元の最小化問題は、次のようにも書けます。
$$
\begin{align}
\inf_{x \in \mathbb{R}^n} \sup_{\lambda \in \mathbb{R}_{+}^{m}} L(x,\lambda)
\end{align}
$$
これは、次のように示せます：まず、
$$
\begin{align}
F(x) = \sup_{\lambda \in \mathbb{R}_{+}^{m}} L(x,\lambda) =
\begin{cases}
f(x) & (\forall i \in \{ 0, \dots, m-1 \} (g_i(x) \geq 0 )) \
\infty & (\mbox{otherwise})
\end{cases},
\end{align}
$$
が成り立ちます。従って、次が成り立ちます。
$$
\begin{align}
\inf_{x \in \mathbb{R}^n} F(x) = \inf_{x \in S} f(x)
\end{align}
$$
このことから、上の書き換えが成り立つことが分かります。
さて、この$\inf$と$\sup$を入れ替えることを考えてみましょう。@@@ Why???
$$
\begin{align}
q(\lambda) &:= \inf_{x \in \mathbb{R}^n} L(x, \lambda)
\end{align}
$$
とおくと、この「入れ替えた問題」は、次の最大化問題になります。
$$
\begin{align}
\sup_{\lambda \in \mathbb{R}_{+}^{m}} q(\lambda)
\end{align}
$$
これを、元の問題の(Lagrange)双対問題と呼びます。対して、元の問題を主問題と呼びます。
4 主問題と双対問題の関係
では、双対問題を立てることによって何が嬉しいのかを考えていきましょう。結論から述べると、
- 主問題は直接解けなくても、双対問題は簡単に解けることがある。
- 双対問題の解や最適値から、主問題の解や最適値についての情報を得られることがある。
のがご利益です。
まず、定義より明らかに、
$$
\begin{align}
\forall x \in \mathbb{R}^n, \forall \lambda \in \mathbb{R}_{+}^{m} \ :
F(x) \geq L(x,\lambda) \geq q(\lambda)
\end{align}
$$
が成り立ちます。これより、
$$
\begin{align}
\inf_{x \in S} f(x) \geq \sup_{\lambda \in \mathbb{R}_{+}^{m}} q(\lambda)
\end{align}
$$
が従います。
後者の結果は、「弱双対定理」と呼ばれ、「双対問題の最適値は、主問題の最適値の下界を与える」ことを述べています。
主問題と双対問題の最適解の関係については、次の節で見ていきましょう。
5 凸最適化問題の双対定理
ここでは、主問題は以下の性質を満たすと仮定します。
- $f$は凸関数であり、$g_i$は全て凹関数であるとします。 つまり、主問題は凸最適化問題とします。
- 実行可能領域$S$は内点を持つとします。
- $f$は$x^{\ast} \in S$で最小値を取り、$q$は$\lambda^{\ast} \in \mathbb{R}_{+}^{m}$で最大値を取るとします。
このとき、次の性質が成り立つことが知られています
$$
\begin{align}
f(x^{\ast}) = q(\lambda^{\ast})
\end{align}
$$
これは、(強)双対定理として知られています。
このことから、次の性質が成り立ちます。
- $ f(x^{\ast}) = L(x^{\ast}, \lambda^{\ast}) = q(\lambda^{\ast})$
- $\forall x \in \mathbb{R}^{n} \forall \lambda \in \mathbb{R}_{+}^{m} : L(x, \lambda^{\ast}) \geq L(x^{\ast}, \lambda^{\ast}) \geq L(x^{\ast}, \lambda)$
前者は、$F(x) \geq L(x,\lambda) \geq q(\lambda)$と強双対定理より直ちに従います。
後者は、次のようにして示せます: $L(x, \lambda^{\ast}) \geq q(\lambda^{\ast}) = L(x^{\ast},\lambda^{\ast})$と、$L(x^{\ast}, \lambda) \leq F(x^{\ast}) = L(x^{\ast}, \lambda^{\ast})$
これらの性質を利用して$\lambda^{\ast}$から$x^{\ast}$を求めることができます2。