* Karush-Kuhn-Tucker条件 (KKT条件; Karush-Kuhn-Tucker conditions) [#v1673106]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

\(n\)次元のベクトル \(\mathbf{x}=(x_1,\ldots,x_n)\) について,次の制約を持つ最適化問題:
-目的関数:\(\min_{\mathbf{x}} f(\mathbf{x})\)
-制約条件:\(g_1(\mathbf{x})\le0,g_2(\mathbf{x})\le0,\ldots,g_m(\mathbf{x})\le0\)

\(f(\mathbf{x})\) と \(g_i(\mathbf{x})\) が全て凸関数であれば,凸計画問題と呼ばれ,局所最適解が大域最適解になる.

凸計画問題なら,次の''Lagrange関数'' (Lagragian)について
\[L=f(\mathbf{x})+\sum_i^m \lambda_i g_i(\mathbf{x})\]
次の連立方程式の解を \(\mathbf{x}^\ast,\lambda^\ast_1,\lambda^\ast_2,\ldots,\lambda^\ast_m\) とし,
\[\frac{\partial L}{\partial x_1}=0,\frac{\partial L}{\partial x_2}=0,\ldots,\frac{\partial L}{\partial x_n}=0,\frac{\partial L}{\partial \lambda_1}=0,\frac{\partial L}{\partial \lambda_2}=0,\ldots,\frac{\partial L}{\partial \lambda_m}=0\]
\(\mathbf{x}^\ast\) と \(\lambda^\ast_1,\lambda^\ast_2,\ldots,\lambda^\ast_m\) が次の制約を満たすとき,
\[g_i(\mathbf{x}^\ast)\le0\]
\[\lambda_i^\ast\ge0\]
\[\lambda^\ast_ig_i^\ast(\mathbf{x}^\ast)=0\]
\(\mathbf{x}^\ast\) は凸計画問題の局所最適解になる.

>-- しましま

**関連項目 [#n5dd8976]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.

-[[Karush-Kuhn-Tucker条件]]
-[[Karush-Kuhn-Tucker conditions]]
#br
-[[最適化]]
-[[Lagrangeの未定乗数法]]
-[[SVM]]
#br
-[[検索:KKT条件 Karush-Kuhn-Tucker]]

**リンク集 [#v2f1b15e]

//関連するWWW資源があればリンクしてください.

-[[Wikipedia:Karush-Kuhn-Tucker_conditions]]
-[[MathWorld:Kuhn-TuckerTheorem]]

**関連文献 [#g7731e8f]

//この%項目%に関連する書籍や論文を紹介してください.

-Book/最適化の手法 4.6章
-[[Book/Pattern Recognition and Machine Learning]] Appendix E
-[[Book/データマイニングの基礎]] 3.3節
-[[Book/サポートベクターマシン(知の科学)]] 3.2節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS