知識メモ
知識メモ
ラグランジュ未定乗数法

f(x) \rightarrow min
s.t. \ \ \ g_j (x) = 0 \ \ \ (j = 1, 2, ..., m)
を満たす n変数関数 f(x) の最適解 x* , λ* は
\frac{\partial f(x^{\ast})}{\partial x_i} + \sum_{j=1}^{m} \lambda_j^{\ast} \frac{\partial g_j(x^{\ast})}{\partial x_i} = 0 \ \ \ (i = 1,2,...,n)
g_j (x^{\ast}) = 0 \ \ \ (j = 1,2,...,m)
を満たしている。
すなわちこれを解けば、いくつかの解の中に x*, λ* を含むはずである。


クーン・タッカー（Kuhn-Tucker）定理　または　KKT条件

f(x) \rightarrow min
s.t. \ \ \ g_j (x) \leq 0 \ \ \ (j = 1, 2, ..., m)
を満たす n変数関数 f(x) の最適解 x* , λ* に関する条件で、
\frac{\partial f(x^{\ast})}{\partial x_i} + \sum_{j=1}^{m} \lambda_j^{\ast} \frac{\partial g_j(x^{\ast})}{\partial x_i} = 0

\lambda_j^{\ast} g_j (x^{\ast}) = 0

g_j (x^{\ast}) \leq 0

\lambda_j^{\ast} \geq 0

(i = 1,2,...,n, \ \ j = 1,2,...,m)

のことを言う。この条件の方程式を解き、

①解があるならば、そのうちひとつが最適解
②解がないならば、「KKT条件を満たさないような最適解が存在する」または「最適解なし」

となる。つまり、最適解がKKT条件を満たすとは限らない。

ちなみに λ が非負なのは、境界において f の勾配と g の勾配（法線ベクトル）が必ず逆向きになるため


ジョン（John）条件

\lambda_0^{\ast} \frac{\partial f(x^{\ast})}{\partial x_i} + \sum_{j=1}^{m} \lambda_j^{\ast} \frac{\partial g_j(x^{\ast})}{\partial x_i} = 0

\lambda_j^{\ast} g_j (x^{\ast}) = 0

g_j (x^{\ast}) \leq 0

\lambda_0^{\ast} , \ \lambda_j^{\ast} \geq 0

(i = 1,2,...,n, \ \ j = 1,2,...,m)

最適解があれば、このジョン条件は満たす。
しかし、ジョン条件を満たす解を求めたからといって、その中に最適解が存在するとは限らない（最適解がないパターン？）。

タグ：

解析学
「ラグランジュ未定乗数法、KKT条件、John条件」をウィキ内検索
最終更新：2012年08月24日 01:34