非線形最適化問題における双対問題の導出

統計や機械学習では非線形問題の双対問題を利用した議論がよくなされます．しかし，双対問題の導出が天下り的に書かれている本が多く，一般的な双対問題の導出方法が書いてなかったのでまとめました．

まずは非線形最適化の極小解の必要条件であるKKT条件 (Karush–Kuhn–Tucker conditions) の復習をします．またここに出てくる全ての関数は微分可能であるとします．

KTT条件

一般的な関数$f(x)$の制約付き最小化問題を考えます．ちなみに$x$は$n$次元のベクトルとします．

$$
\begin{align*}
\text{minimize} & \quad f(x) \\
\text{subject to} & \quad g_i(x) \leq 0 \quad (i = 1, \dots, m)
\end{align*}
$$

このとき，$x^*$が極小解となる必要条件であるKKT条件（厳密にはKKT条件が必要条件になるには$\nabla g_i(x)$が一次独立である条件も必要）は以下の条件を満たす$\lambda_i (i = 1, \dots, m)$が存在することです．

$$
\begin{align*}
\nabla f(x^*) + \sum_{i = 1}^m \lambda_i \nabla g_i(x^*) = 0 \\
\lambda_i g_i(x^*) = 0 \quad (i = 1, \dots, m) \\
g_i(x^*) \leq 0 \quad (i = 1, \dots, m) \\
\lambda_i \geq 0 \quad (i = 1, \dots, m)
\end{align*}
$$

もちろん，$f(x)$が凸関数であれば，KKT条件は$x^*$が最適解である必要条件となります．幾何的な解釈ができるので，上の式を覚える必要はないですが解釈などはここでは行いません．

KKT条件の一つ目の条件は一次条件 (first order condition) ですが，微分する前の左辺のことをラグランジェ関数 (Lagrangian function) と呼びます．つまり，上の最小化問題のラグランジェ関数は，

$$
L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i(x).
$$

$\lambda_i$のことをラグランジェ乗数 (Lagrangian multiplier) と呼びます．ちなみに$\lambda$は$\lambda_i$を$m$個並べた$m$次元のベクトルです．

ラグランジェ関数を用いて双対問題を導出します．その前にラグランジェ関数と元の最適化問題の関係について議論します．

ラグランジェ関数との関係

ラグランジェ関数を$\lambda$の関数とみなします．つまり，$x$を特定の値$\tilde{x}$に固定します．このとき以下のような$\lambda$の最大化問題をと考えます．

$$
\begin{align*}
\text{maximize} & \quad L(\tilde{x}, \lambda) \\
\text{subject to} & \quad \lambda_i \geq 0 \quad (i = 1, \dots, m)
\end{align*}
$$

ラグランジェ関数を見ればわかりますが，$\lambda_i$の係数は$g_i(\tilde{x})$です．$\tilde{x}$の数値によって$g_i(\tilde{x})$の正負が変わります．もしある$i$で，$g_i(\tilde{x}) > 0$のとき，$\lambda_i$の値を大きくすれば関数値はいくらでも大きくなるので，非有界となります．逆に全ての$i$で$g_i(\tilde{x}) \leq 0$であれば，上の問題の解は$\lambda = \bf 0$で，最適値は$f(\tilde{x})$となります．上の問題の最適値は$\tilde{x}$の値によって変化するので，その最適値を$F(\tilde{x})$とおきます．すると，

$$
F(\tilde{x}) = \begin{cases}
f(\tilde{x}) \quad g_i(\tilde{x}) \leq 0 (i = 1, \dots, m) \\
\infty \quad (\text{otherwise})
\end{cases}
$$

よって，$F(\tilde{x})$を目的関数とする最小化問題の最適値は，元の$f(x)$の制約付き最小化問題の最適値と同じになります．

$$
\min_{\tilde{x}} F(\tilde{x}) = \min_{\tilde{x}} \max_{\lambda \geq 0} L(\tilde{x}, \lambda).
$$

次にラグランジェ双対問題を導出するキーとなるmin-maxとmax-minの関係性を示す定理を証明します．

$$
\min_{x} \max_{\lambda \geq 0} L(x, \lambda) \geq \max_{\lambda \geq 0} \min_{x} L(x, \lambda)
$$

（証明）

$$
\forall \lambda \geq 0 , x \quad L(x, \lambda) \geq \min_{x} L(x, \lambda)．
$$

よって，両辺で$\lambda$を最大化しても不等式は変わらないので，

$$
\forall x \quad \max_{\lambda \geq 0} L(x, \lambda) \geq \max_{\lambda \geq 0} \min_{x} L(x, \lambda)．
$$

任意の$x$について成り立つので，左辺で最小値取っても不等式は変わらず，

$$
\min_{x} \max_{\lambda \geq 0} L(x, \lambda) \geq \max_{\lambda \geq 0} \min_{x} L(x, \lambda)．
$$

（証明終わり）

上の定理を使って双対問題を導出します．

$$
\min_{x} F(x) = \min_{x} \max_{\lambda \geq 0} L(x, \lambda) \geq \max_{\lambda \geq 0} \min_{x} L(x, \lambda).
$$

ここで，$\bar{F}(\lambda) = \min_{x} L(x, \lambda)$とおくと，

$$
\max_{\lambda \leq 0} \min_{x} L(x, \lambda) =\max_{\lambda \geq 0} \bar{F}(\lambda)
$$

となる．

この$\bar{F}(\lambda)$の最大化問題が双対問題となる．

結局，ラグランジェ関数を作りそれを目的関数とした$x$に関する制約なし最小化問題を解いた$\lambda$に依存した最適値が双対問題の目的関数となります．

非線形の最小化問題では，一般に双対問題の最適値と主問題の最適値は一致しません．Slater's conditionと呼ばれる条件を満たすと一致することが知られています[2]．

Slater's conditionを満たす具体例の一つがSupport vector machine (SVM) に出てくる最適化問題です．次回は，SVMを例に双対問題を応用した議論について書きたいと思います．

参考文献

[1]: 田村明久 村松正和 (2002)．最適化法　共立出版

[2]: Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.