拉格朗日乘子法和KKT條件在求取有約束條件的優(yōu)化問題時，拉格朗日乘子法(LagrangeMultiplier)和KKT條件是非常重要的兩個求取方法，對于等式約束的優(yōu)化問題，可以應用拉格朗日乘子法去求取最優(yōu)值；如果含有不等式約束，可以應用KKT條件去求取。當然，這兩個方法求得的結果只是必要條件，只有當是凸函數的情況下，才能保證是充分必要條件。KKT條件是拉格朗日乘子法的泛化。一.拉格朗日乘子法(LagrangeMultiplier)和KKT條件通常我們需要求解的最優(yōu)化問題有如下幾類：無約束優(yōu)化問題，可以寫為：minf(x);有等式約束的優(yōu)化問題，可以寫為：minf(x),s.t.h_i(x)=0;i=1,...,n有不等式約束的優(yōu)化問題，可以寫為：minf(x),s.t.g_i(x)<=0;i=1,h_j(x)=0;j=1,...,m對于第(i)類的優(yōu)化問題，常常使用的方法就是Fermat定理，即使用求取f(x)的導數，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗證；如果是凸函數，可以保證是最優(yōu)解。對于第(ii)類的優(yōu)化問題，常常使用的方法就是拉格朗日乘子法(LagrangeMultiplier)，即把等式約束h_i(x)用一個系數與f(x)寫為一個式子，稱為拉格朗日函數，而系數稱為拉格朗日乘子。通過拉格朗日函數對各個變量求導，令其為零，可以求得候選值集合，然后驗證求得最優(yōu)值。對于第(iii)類的優(yōu)化問題，常常使用的方法就是KKT條件。同樣地，我們把所有的等式、不等式約束與f(x)寫為一個式子，也叫拉格朗日函數，系數也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個條件稱為KKT條件。(a)拉格朗日乘子法(LagrangeMultiplier)對于等式約束，我們可以通過一個拉格朗日系數a把等式約束和目標函數組合成為一個式子L(a,x)=f(x)+a*h(x),這里把a和h(x)視為向量形式，a是橫向量，h(x)為列向量，然后求取最優(yōu)值，可以通過對L(a,x)對各個參數求導取零，聯(lián)立等式進行求取，這個在高等數學里面有講，但是沒有講為什么這么做就可以，在后面，將簡要介紹其思想。對于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數全部寫為一個式子L(a,b,x)=f(x)+a*g(x)+b*h(x)KKT條件是說最優(yōu)值必須滿足以下條件：L(a,b,x)對x求導為零；h(x)=0;a*g(x)=0;求取這三個等式之后就能得到候選最優(yōu)值。其中第三個式子非常有趣，因為g(x)<=0，如果要滿足這個等式，必須a=0或者g(x)=0.這是SVM的很多重要性質的來源，如支持向量的概念。二.為什么拉格朗日乘子法(LagrangeMultiplier)和KKT條件能夠得到最優(yōu)值？為什么要這么求能得到最優(yōu)值？先說拉格朗日乘子法，設想我們的目標函數z=f(x),x是向量，z取不同的值，相當于可以投影在x構成的平面(曲面)上，即成為等高線，如下圖，目標函數是f(x,y)，這里x是標量，虛線是等高線，現(xiàn)在假設我們的約束g(x)=0，x是向量，在x構成的平面或者曲面上是一條曲線，假設g(x)與等高線相交，交點就是同時滿足等式約束條件和目標函數的可行域的值，但肯定不是最優(yōu)值，因為相交意味著肯定還存在其它的等高線在該條等高線的內部或者外部，使得新的等高線與目標函數的交點的值更大或者更小，只有到等高線與目標函數的曲線相切的時候，可能取得最優(yōu)值，如下圖所示，即等高線和目標函數的曲線在該點的法向量必須有相同方向，所以最優(yōu)值必須滿足：f(x)的梯度二a*g(x)的梯度，a是常數，表示左右兩邊同向。這個等式就是L(a,x)對參數求導的結果。(上述描述，我不知道描述清楚沒，如果與我物理位置很近的話，直接找我，我當面講好理解一些，注：下圖來自wiki)。而KKT條件是滿足強對偶條件的優(yōu)化問題的必要條件，可以這樣理解：我們要求minf(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),因此我們的目標函數可以寫為min_xmax_{a,b}L(a,b,x)。如果用對偶表達式：max_{a,b}min_xL(a,b,x),由于我們的優(yōu)化是滿足強對偶的(強對偶就是說對偶式子的最優(yōu)值是等于原問題的最優(yōu)值的)，所以在取得最優(yōu)值x0的條件下，它滿足f(x0)=max_{a,b}min_xL(a,b,x)=min_xmax_{a,b}L(a,b,x)=f(x0)，我們來看看中間兩個式子發(fā)生了什么事情：f(x0)=max_{a,b}min_xL(a,b,x)=max_{a,b}min_xf(x)+a*g(x)+b*h(x)=max_{a,b}f(x0)+a*g(x0)+b*h(x0)=f(x0)可以看到上述加黑的地方本質上是說min_xf(x)+a*g(x)+b*h(x)在x0取得了最小值，用fermat定理，即是說對于函數f(x)+a*g(x)+b*h(x)，求取導數要等于零，即f(x)的梯度+a*g(x)的梯度+b*h(x)的梯度=0這就是kkt條件中第一個條件：L(a,b,x)對x