MathLabs
定理証明済み

カルーシュ・クーン・タッカー条件

内容

問題 min⁡f(x)\min f(x)（制約 gi(x)≤0 (i=1,…,m)g_i(x) \le 0\ (i=1,\dots,m)、hj(x)=0 (j=1,…,p)h_j(x)=0\ (j=1,\dots,p)、f,gi,hjf, g_i, h_j は微分可能）を考える。x∗x^* が制約想定を満たす局所最小点であれば、乗数 μi≥0\mu_i \ge 0、λj\lambda_j が存在し次を満たす：（停留条件）∇f(x∗)+∑iμi∇gi(x∗)+∑jλj∇hj(x∗)=0\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0；（主実行可能性）gi(x∗)≤0, hj(x∗)=0g_i(x^*)\le 0,\ h_j(x^*)=0；（双対実行可能性）μi≥0\mu_i \ge 0；（相補性）μigi(x∗)=0\mu_i g_i(x^*) = 0（すべての ii について）。凸問題ではこれらの条件は大域最適性の十分条件でもある。

なぜ正しいのか?

制約付き最適点では、どんな小さな実行可能な移動でも目的関数を改善できない。停留条件は、ff の勾配が活性制約の勾配の非負結合によってちょうど打ち消されることを意味する——最適点は内向きにしか押さない力（乗数）によって実行可能領域の境界に『固定』されている。相補性は、制約が力（μi>0\mu_i>0）を及ぼすのは、それが実際に活性である（gi(x∗)=0g_i(x^*)=0）ときに限ることを意味し、余裕のある制約は何も寄与しない。

証明の概略

制約想定（活性制約勾配の線形独立性、または凸問題でのスレーター条件など）の下で、x∗x^* における実行可能方向の集合は活性制約の線形化錐と一致する。x∗x^* が局所最小点であるため、∇f(x∗)\nabla f(x^*) はどの実行可能方向とも負の内積を持てず、−∇f(x∗)-\nabla f(x^*) は活性制約の勾配が生成する錐に属する——これはまさに線形化された系にファルカスの補題を適用したものであり、乗数 μi,λj\mu_i, \lambda_j が得られる。

この定理を使うトピック

凸最適化

関連する定理

線形計画法の強双対定理凸関数の局所最小値は大域最小値である

ステップごとの証明

この定理のステップごとの証明はまだありません。

参考文献

  1. Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
  2. Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty (2006). Nonlinear Programming: Theory and Algorithms