【1】引言
前序學習階段中,我們掌握了最佳分割超平面對應的構造拉格朗日函數極值為:
L(w,b,α)=∑i=1mαi?12∑i,j=1mαiαjyiyjxiTxjL(w,b,\alpha)=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}L(w,b,α)=i=1∑m?αi??21?i,j=1∑m?αi?αj?yi?yj?xiT?xj?
這個極值有一個天然的約束:
∑i=1mαiyi=0\sum_{i=1}^{m}\alpha_{i}y_{i}=0i=1∑m?αi?yi?=0
如果對此還有些不理解,可以回顧之前的學些文章拉格朗日函數求解和KKT條件初步,寫得比較緩慢而細碎,希望大家不要介意。
那KKT條件究竟是為何提出的,實際上KKT條件的作用是把約束融入優化條件,讓我們能像處理無約束問題一樣,用一套規則判斷有約束時的最優解。
【2】理解
先明確KKT條件的應用場景。
加入我們要解決一個帶約束的優化問題,比如最大化收益,最小化成本。當如果沒有約束時,我們計算極大值或極小值往往很方便,然而一旦有了約束,目標函數的“最優方向”就有可能被約束條件擋住了。
KKT條件的作用就是,判斷當前點是不是“既滿足所有約束,又無法在不違反約束的前提條件下變得更好”的點,也就是找出局部最優價。
然后我們用“力的平衡”來理解KKT條件的核心思想。
想想我們站在約束條件形成的區域里,目標函數對我們有一個“拉力”,二每個約束條件都是一個“阻力”,最優解就位于拉力和阻力相平衡的地方。
具體來說,等式約束像繩子,繩子拉力與目標函數的拉力平衡;不等式約束像一堵墻,沒碰到墻的時候沒有力,一旦碰到了墻,墻的推力會與目標函數的拉力平衡,也就是給墻的力有多大,受到的反作用力就有多大。
然后來嘗試把“力的平衡”拆解成KKT條件的5條規則:
梯度為零(力的平衡方程):目標函數的梯度=所有起作用的約束條件的梯度的加權和(權重是拉格朗日乘子)。
直觀理解,目標函數的“拉力”被約束“推力”剛好抵消,合理為零,無法移動。不等式約束條件(不能越界),如果不滿足,這個點違反約束,不可能是最優解。
拉格朗日乘子非負(推力方向正確),不等式約束的權重必須非負,因為代表約束的“推力”方向必須與目標函數的“拉力”方向相反。
互補松弛性,也就是沒有碰到墻不算,沒有觸發反彈。
等式約束條件,理解為繩子剛好勒緊,此時約束嚴格成立。
【3】總結
最KKT條件進行了進一步解讀。