機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100％趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

不等式制約におけるラグランジュの未定乗数法（KKT条件）

微分積分

ラグランジュの未定乗数法にて等式制約条件下における解の求め方を確認しました。今回は条件が不等式の場合を考えます。 $g(\mathbf x) \leq 0$ の条件において $f(\mathbf x)$ の最大値を求める問題です。

$n$ 個の変数を持つ関数を考えるので引数 $\mathbf{x}$ はベクトルです。前提条件として $g(\mathbf x)$ は下に凸、 $f(\mathbf x)$ は上に凸とします。（目的関数も制約条件も凸関数である問題を凸計画と呼びます）

もし $g(\mathbf x) \lt 0$ の中に $f(\mathbf x)$ の最大値があれば、この制約条件は無くても解には影響しません。これはラグランジュの式

$L(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) \tag{1}$

において、 $\lambda=0$ とした場合に等しいです。要するにただの $f(\mathbf x)$ の最大値問題です。

$g(\mathbf x) \lt 0$ の中に解がないのなら、各関数の凸の条件により領域の境界 $g(\mathbf x) = 0$ 上に解が存在することになります。 $g(\mathbf x)$ が下に凸、 $f(\mathbf x)$ が上に凸ですから、境界上の解において $\nabla g, \nabla f$ は外向きのベクトルとなります。下図のようなイメージです。

f:id:opabinia2:20180130202509p:plain

凸の前提条件がないと、例えば領域内に $f(\mathbf x)$ の最大値がなくても、境界上の全ての値よりも大きい極大値が存在する場合が考えられます。するとこの考え方が成り立ちません。

さて、 $\nabla g, \nabla f$ の方向が同じということは、 $\nabla f = \lambda \nabla g$ となる $\lambda \gt 0$ が存在することになります。このときの解の求め方はラグランジュの未定乗数法と同じで、式(1)を解けばよいです。

以上より、解が境界内にあれば $\lambda=0$ 、境界上にあれば $g(\mathbf x) = 0$ ですので、いずれの場合にしてもどちらかが0ですから、

$\lambda g(\mathbf x) = 0 \tag{2}$

が成り立ちます。

まとめると、 $g(\mathbf x) \leq 0$ の条件において $f(\mathbf x)$ の最大値を求めるためには、

$\lambda g(\mathbf{x}) = 0 \tag{3}$ $\lambda \ge 0 \tag{4}$ $g(\mathbf{x}) \leq 0 \tag{5}$

の条件の元で

$L(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x}) \tag{6}$

を解けばよいことになります。この式(3)～(5)をKKT条件（カルーシュ・クーン・タッカー条件）と呼びます。名前がかっこいい。

なお問題の条件によって図で示した勾配の向きが変わりますので、KKT条件の符号もそれに応じたものになります。例えば $\nabla g, \nabla f$ が逆向きになれば $\lambda \lt 0$ です。

凸計画でない場合の解の求め方はどうなるのか？よくわかっていないが、現実の問題は扱いやすいようになるべく凸関数を使って定式化するんだそう。

とりあえずここまでで線形回帰における正則化項の意味が理解できます。→正則化項（罰金項）の意味