はじめに
以前の投稿でラグランジュの未定乗数法を扱った。今回はそれを一般化し、KKT条件と呼ばれる一連の条件式を導く。
問題設定
(1)
で与えられるとき、の極値を求めるには、関数
(2)
を考え、のとについての極値を計算すればよい。ここで、関数をラグランジュ関数と呼ぶのであった。今回は、束縛条件を不等号に拡張する。
(3)
さらに、の極値ではなく最小値(条件を満たす領域における最小値)を考える。まとめると、今回の問題設定は以下のようになる。
(4)
(5)
の最小値を求めよ。
ラグランジュの未定乗数法
見通しをよくするため、先の記事の例題で用いた関数 を考える。下図の緑色の放物曲面がである。ここに、の領域(赤色の円柱内部)を重ねてみる。
(A)はのとき、(B)はのときである。(A)の場合、の縁で最小()となり、(B)の場合、の最小値がそのまま解()となる。この観察を定式化する。
まず最初に(A)を考える。最小値は領域の縁上にあるからが成り立つ。いま、点を微小量だけからはみ出さない方向に動かす。このとき次式が成り立つ。
(6)
(7)
が成り立つ。点におけるの等高線とは点で接するから、とは同じ向きを持つか、真逆の向きを持つ。同じ向きを持つ場合、として
(8)
(9)
となる。ここでにおけるの値を評価すると
(10)
いま、であったからとなる。これはが最小値であることと矛盾する。したがって、とは反平行でなければならない。
(11)
ここでラグランジュ関数
(12)
を導入すれば、(A)の場合の最小値は次式を解けばよいことが分かる。
(13)
式(13)の4つ目の式は最小値がの縁にあることを表している。
次に(B)の場合を考える。このときは領域がの最小値を含むから束縛条件なしでの最小値を求めればよい。これはラグランジュ関数においてと置くことを意味する。
(A)と(B)の2つの結果を融合すると解くべき式は以下となる。
(14)
式(14)の4つ目の条件は、(A)の場合はを、(B)の場合はを意味する。式(14)の4つの式のセットを、カルーシュ・キューン・タッカー条件(Karush-Kuhn-Tucker condition)あるいはKKT条件と呼ぶ。
まとめ
今回は、以前紹介したラグランジュの未定乗数法を一般化し、KKT条件と呼ばれる式のセットを導出した。これは最適化問題における主問題と双対問題の間を橋渡しするものであり、SVMなどの最適化問題を解く際には必ず現れる重要な条件である。主問題と双対問題の説明は機会を改めたい。