Karush-Kuhn-Tucker条件 (KKT条件; Karush-Kuhn-Tucker conditions)

\(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\) は凸計画問題の局所最適解になる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:05 (2493d)