2次計画における双対問題 - 機械学習に詳しくなりたいブログ

$f(\mathbf{x})$ の最大値を、

${\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} g_1(\mathbf{x})\le0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ g_m(\mathbf{x})\le0 \tag{1} \end{array} \right. \end{eqnarray} }$

${\displaystyle \begin{eqnarray} \left\{ \begin{array}{l} h_1(\mathbf{x})=0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots \\ h_l(\mathbf{x})=0 \tag{2} \end{array} \right. \end{eqnarray} }$

の制約条件下で求めることを考えます。この問題において、 $f(\mathbf{x})$ が上に凸の2次関数で、制約条件が線形制約の場合、2次計画と呼びます。2次計画の問題を解くには、双対定理がよく使われるようです。この双対定理の背景にある理論は僕にとっては難解でなかなか理解が難しかったので、とりあえず解き方の手順だけを整理してみました。

まず、ラグランジュ関数を作ります。*1

$\displaystyle L(\mathbf{x},\boldsymbol \lambda ,\boldsymbol \mu) = f(\mathbf{x}) - \sum_{i=1}^{m} \lambda_{i} g_i(\mathbf{x}) - \sum_{i=1}^{l} \mu_{i} h_{i}(\mathbf{x}) \tag{3}$

解においては、不等式制約におけるラグランジュの未定乗数法（KKT条件）より、KKT条件

$\lambda_i g_i(\mathbf{x}) = 0 \tag{4}$ $\lambda_i \ge 0 \tag{5}$ $g_i(\mathbf{x}) \leq 0 \tag{6}$

が成り立ちます。ここで、 $L(\mathbf{x},\boldsymbol \lambda ,\boldsymbol \mu)$ は凸関数ですから、最大値においては $\displaystyle \frac{\partial L}{\partial \mathbf{x}}=\mathbf{0}$ が成り立ちます。 $\displaystyle \frac{\partial L}{\partial \mathbf{x}}=\mathbf{0}$ を用いてラグランジュ関数から $\mathbf{x}$ を消去すると、双対問題

$l(\boldsymbol \lambda ,\boldsymbol \mu) \tag{7}$

が得られます（KKT条件より $\lambda_i \ge0$ ）。これを最小にする $\boldsymbol \lambda ,\boldsymbol \mu$ を求めます。すると、式(3)、(7)に解が存在するなら、その最大値と最小値は一致し、この性質を双対定理と呼びます。もとのラグランジュ関数よりも双対問題のほうが解きやすいために、2次計画問題ではこの手法がよく用いられるようです。

*1:参考：ラグランジュの未定乗数法、不等式制約におけるラグランジュの未定乗数法（KKT条件）