KKT条件 - 機械学習の「朱鷺の杜Wiki」
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(\ma
株式会社NTTデータ数理システム
読み：けーけーてぃーじょうけん 関連：制約想定 Karush-Kuhn-Tucker 条件の略． 微分可能な関数 $f \colon \mathbb{R}^n \to \mathbb{R}$，$g_i \colon \mathbb{R}^n \to \mathbb{R}$，$h_j \colon \mathbb{R}^n \to \mathbb{R}$ に対し，次のような等式・不等式制約をもつ数理計画問題 $(P)$ を考える． $$ (P) \begin{array}{lll} \min & f(x) & \\ \mathrm{s.t.} & g_i(x) \le 0 & (i=1,\ldots,m) \\ & h_j(x) = 0 & (j=1,\ldots,l) \end{array} $$ 以下の式が問題 $(P)$ に対する KKT 条件である． $$ \left\{ \begi
カーネル法
カーネル法 線形回帰、識別からカーネル関数へ y ( w ) = wT φ (x ) という一般化した線形回帰式に対して 2 1N λT T J ( w ) = ∑ {w φ ( x n ) − tn } + w w 2 n =1 2 ただし ⎛ φ1 ( x n ) ⎞ ⎜ ⎟ φ (x n ) = ⎜ M ⎟ ⎜ φ (x ) ⎟ ⎝M n⎠ tnはw T φ ( x n )がとるべき値。 ( Mは教師データの次元数 , Nは教師データ数) という正規化項つきの２乗誤差を考えるとき、 φ (x )についてもう少し組織的に考えてみよう。 カーネル関数と呼ばれる k (φ (x ), φ ( y )) で回帰や識別を考え直す ことにより、より効率の良い方法が見えてくる。 双対表現 まず、正規化項つきの２乗誤差関数を考える。 J ( w) = 1 2 ∑ {w φ (x
これで解決！シリーズ 大学数学 - クーン・タッカーの必要条件
クーン・タッカーの必要条件 ああん、クーン・タッカーって本当に分からないわ。ベクトルの記号が多すぎて、何を言ってるのかさっぱりなの。 ははは。大丈夫じゃよ。教科書などで書いてある定義とやらをまずみてみようじゃないか。ラプラシアンというものを定義して、その勾配がゼロとなるときがアヤシイっていうだけのことじゃが、ちょっと英語やら記号やらで身構えてしまいそうじゃな。 一つ一つの演算は出来るんだよ。勾配を計算したりとか、ベクトルの計算など。でも、なぜこんなものたちが急に出てきたかなんていうことがサッパリだよ。 ラプラシアンがなぜ急に出てきて、なぜそれの勾配がゼロとなるときが最小または最大になりうるのか、という根本的な疑問だね。でも心配いらないよ。実はね、真ん中に出てきている∇L=0という条件の式は、実はベクトルのつりあいの式なんだよ。 ベクトルのつりあいの式？∇L=0が？ 高校で学んだ力学に出てき
最適化：非線形計画について(最急降下、ニュートン、KKT条件)とNP困難問題に対する動的計画法 - 雑なメモ
2015-01-13 最適化：非線形計画について(最急降下、ニュートン、KKT条件)とNP困難問題に対する動的計画法 書きかけ 最適化 非線形計画 この記事の内容 試験が近いからぱっとノートとかまとめた記事。細かい定義とかは省略してます。そして特に断りが無い限りはベクトルで、といった添字のあるものはベクトルではない単なる実数か定義域の内部にある数の一つです。あと微分可能性とかはほぼ触れてないので察してください。 参考文献 [1] 数理計画入門(1996) 福島雅夫著 朝倉書店 過去のメモ 非線形計画の最適化問題：最急降下法、ニュートン法、KKT条件まで - 雑なメモ 非線形計画の最適化問題：最急降下法、ニュートン法、KKT条件まで - 雑なメモ 途中までは、上の記事とほぼ同じ内容。 このつぎのメモ（こっちの方が最新） 最適化：非線形計画＋組み合わせ最適化のまとめのメモ - 雑なメモ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Beginer_Opt
untitled