ラグランジュの未定乗数法の一般化

はじめに

　以前の投稿でラグランジュの未定乗数法を扱った。今回はそれを一般化し、KKT条件と呼ばれる一連の条件式を導く。

問題設定

　最初に以前の結果を再掲する。x\in\mathbb{R}^n,u\in\mathbb{R}とする。束縛条件が

(1)   \begin{equation*} g(x)=0 \end{equation*}

で与えられるとき、f(x)の極値を求めるには、関数

(2)   \begin{equation*} L(x,u)=f(x)+ug(x) \end{equation*}

を考え、L(x,u)のxとuについての極値を計算すればよい。ここで、関数L(x,u)をラグランジュ関数と呼ぶのであった。今回は、束縛条件を不等号に拡張する。

(3)   \begin{equation*} g(x)\leq0 \end{equation*}

さらに、f(x)の極値ではなく最小値（条件を満たす領域における最小値）を考える。まとめると、今回の問題設定は以下のようになる。

束縛条件が

(4)   \begin{equation*} g(x)\leq0 \end{equation*}

で与えられるとき

(5)   \begin{equation*} f(x) \end{equation*}

の最小値を求めよ。

ラグランジュの未定乗数法

　見通しをよくするため、先の記事の例題で用いた関数 f(x)=x^2+y^2 を考える。下図の緑色の放物曲面がf(x)である。ここに、g(x)\leq0の領域S_g（赤色の円柱内部）を重ねてみる。

(A)はg(x)=(x-1)^2+(y-1)^2のとき、(B)はg(x)=x^2+y^2のときである。(A)の場合、S_gの縁で最小（\beta）となり、(B)の場合、f(x)の最小値がそのまま解（\beta）となる。この観察を定式化する。

　まず最初に(A)を考える。最小値\betaは領域S_gの縁上にあるからg(\beta)=0が成り立つ。いま、点\betaを微小量dだけS_gからはみ出さない方向に動かす。このとき次式が成り立つ。

(6)   \begin{equation*} g(\beta+d)\simeq g(\beta)+\nabla g(\beta)^T d\leq0 \end{equation*}

g(\beta)=0であるから

(7)   \begin{equation*} \nabla g(\beta)^T d\leq0 \end{equation*}

が成り立つ。点\betaにおけるz=f(x)の等高線とg(x)=0は点\betaで接するから、\nabla f(x)と\nabla g(x)は同じ向きを持つか、真逆の向きを持つ。同じ向きを持つ場合、\lambda\geq0として

(8)   \begin{equation*} \nabla f(\beta)=\lambda\nabla g(\beta) \end{equation*}

と書くことができる。このとき

(9)   \begin{equation*} \nabla f(\beta)^T d=\lambda g(\beta)^T d\leq0 \end{equation*}

となる。ここで\beta+dにおけるf(x)の値を評価すると

(10)   \begin{equation*} f(\beta+d)\simeq f(\beta)+\nabla f(\beta)^Td \end{equation*}

いま、\nabla f(\beta)^Td\leq0であったからf(\beta+d)<f(\beta)となる。これはf(\beta)が最小値であることと矛盾する。したがって、\nabla f(\beta)と\nabla g(\beta)は反平行でなければならない。

(11)   \begin{equation*} \nabla f(\beta)=-\lambda\nabla g(\beta),\;\;\lambda\geq0 \end{equation*}

ここでラグランジュ関数L(x,\lambda)

(12)   \begin{equation*} L(x,\lambda)=f(x)+\lambda g(x) \end{equation*}

を導入すれば、(A)の場合の最小値は次式を解けばよいことが分かる。

(13)   \begin{eqnarray*} \dfrac{\partial L(x,\lambda)}{\partial x}&=&0\\ g(x)&\leq&0\\ \lambda&\geq&0\\ g(x)&=&0 \end{eqnarray*}

式(13)の4つ目の式g(x)=0は最小値がS_gの縁にあることを表している。

　次に(B)の場合を考える。このときは領域S_gがf(x)の最小値を含むから束縛条件なしでf(x)の最小値を求めればよい。これはラグランジュ関数において\lambda=0と置くことを意味する。

　(A)と(B)の2つの結果を融合すると解くべき式は以下となる。

(14)   \begin{eqnarray*} \dfrac{\partial L(x,\lambda)}{\partial x}&=&0\\ g(x)&\leq&0\\ \lambda&\geq&0\\ \lambda g(x)&=&0 \end{eqnarray*}

式(14)の4つ目の条件\lambda g(x)=0は、(A)の場合はg(x)=0を、(B)の場合は\lambda=0を意味する。式(14)の4つの式のセットを、カルーシュ・キューン・タッカー条件（Karush-Kuhn-Tucker condition）あるいはKKT条件と呼ぶ。

まとめ

　今回は、以前紹介したラグランジュの未定乗数法を一般化し、KKT条件と呼ばれる式のセットを導出した。これは最適化問題における主問題と双対問題の間を橋渡しするものであり、SVMなどの最適化問題を解く際には必ず現れる重要な条件である。主問題と双対問題の説明は機会を改めたい。

参考文献

  • 異常検知と変化検知（書籍）
  • しっかり学ぶ数理最適化（書籍）

    • Kumada Seiya

    Kumada Seiya

    仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

    最近の記事

    • 関連記事
    • おすすめ記事
    • 特集記事

    アーカイブ

    カテゴリー

    PAGE TOP