機器學(xué)習(xí)中用到的數(shù)值分析-資料下載頁
2025-06-17 04:49本頁面
【正文】 對于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT條件是說最優(yōu)值必須滿足以下條件：1. L(a, b, x)對x求導(dǎo)為零；2. h(x) =0。3. a*g(x) = 0。求取這三個等式之后就能得到候選最優(yōu)值。其中第三個式子非常有趣，因為g(x)=0，如果要滿足這個等式，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來源，如支持向量的概念。二. 為什么拉格朗日乘子法（Lagrange Multiplier) 和KKT條件能夠得到最優(yōu)值？為什么要這么求能得到最優(yōu)值？先說拉格朗日乘子法，設(shè)想我們的目標(biāo)函數(shù)z = f(x), x是向量, z取不同的值，相當(dāng)于可以投影在x構(gòu)成的平面（曲面）上，即成為等高線，如下圖，目標(biāo)函數(shù)是f(x, y)，這里x是標(biāo)量，虛線是等高線，現(xiàn)在假設(shè)我們的約束g(x)=0，x是向量，在x構(gòu)成的平面或者曲面上是一條曲線，假設(shè)g(x)與等高線相交，交點就是同時滿足等式約束條件和目標(biāo)函數(shù)的可行域的值，但肯定不是最優(yōu)值，因為相交意味著肯定還存在其它的等高線在該條等高線的內(nèi)部或者外部，使得新的等高線與目標(biāo)函數(shù)的交點的值更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切的時候，可能取得最優(yōu)值，如下圖所示，即等高線和目標(biāo)函數(shù)的曲線在該點的法向量必須有相同方向，所以最優(yōu)值必須滿足：f(x)的梯度 = a* g(x)的梯度，a是常數(shù)，表示左右兩邊同向。這個等式就是L(a,x)對參數(shù)求導(dǎo)的結(jié)果。（上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當(dāng)面講好理解一些，注：下圖來自wiki）。而KKT條件是滿足強對偶條件的優(yōu)化問題的必要條件，可以這樣理解：我們要求min f(x), L(a, b, x) = f(x) + a*g(x) + b*h(x)，a=0，我們可以把f(x)寫為：max_{a,b} L(a,b,x)，為什么呢？因為h(x)=0, g(x)=0，現(xiàn)在是取L(a,b,x)的最大值，a*g(x)是=0，所以L(a,b,x)只有在a*g(x) = 0的情況下才能取得最大值，否則，就不滿足約束條件，因此max_{a,b} L(a,b,x)在滿足約束條件的情況下就是f(x)，因此我們的目標(biāo)函數(shù)可以寫為 min_x max_{a,b} L(a,b,x)。如果用對偶表達(dá)式：max_{a,b}min_x L(a,b,x)，由于我們的優(yōu)化是滿足強對偶的（強對偶就是說對偶式子的最優(yōu)值是等于原問題的最優(yōu)值的），所以在取得最優(yōu)值x0的條件下，它滿足 f(x0) =max_{a,b}min_x L(a,b,x) =min_x max_{a,b} L(a,b,x) =f(x0)，我們來看看中間兩個式子發(fā)生了什么事情：f(x0) =max_{a,b}min_x L(a,b,x) =max_{a,b}min_x f(x) + a*g(x) + b*h(x) =max_{a,b} f(x0)+a*g(x0)+b*h(x0) = f(x0)可以看到上述加黑的地方本質(zhì)上是說min_xf(x) + a*g(x) + b*h(x) 在x0取得了最小值，用fermat定理，即是說對于函數(shù)f(x) + a*g(x) + b*h(x)，求取導(dǎo)數(shù)要等于零，即f(x)的梯度+a*g(x)的梯度+ b*h(x)的梯度 = 0這就是kkt條件中第一個條件：L(a, b, x)對x求導(dǎo)為零。而之前說明過，a*g(x) = 0，這時kkt條件的第3個條件，當(dāng)然已知的條件h(x)=0必須被滿足，所有上述說明，滿足強對偶條件的優(yōu)化問題的最優(yōu)值都必須滿足KKT條件，即上述說明的三個條件?？梢园袺KT條件視為是拉格朗日乘子法的泛化。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1