支持向量機(jī)SVM（1）線性可分支持向量機(jī)、拉格朗日乘子法森瘪、KKT條件起趾、SMO

支持向量機(jī)（SVM，Support Vecor Machine）是一種二分類算法恋捆，在集成學(xué)習(xí)和深度學(xué)習(xí)火起來之前支持向量機(jī)的使用非常廣泛照皆，其分類效果好、適用性廣（線性沸停、非線性都可用）膜毁，功能真的是很棒棒，下來我們就來梳理一下支持向量機(jī)的原理愤钾。

1 支持向量機(jī)的原理

1）背景

回想一下之前講過的邏輯回歸和感知機(jī)瘟滨，他們的目標(biāo)都是找到一個(gè)將線性可分的數(shù)據(jù)一分為二的決策超平面：

如上圖所示，決策超平面的一側(cè)為正樣本能颁，另一側(cè)為負(fù)樣本室奏，但是我們可以發(fā)現(xiàn)妨蛹，滿足這個(gè)特性的決策超平面并不是唯一的窘行，在有限的線性可分樣本中简识，正負(fù)樣本點(diǎn)之間的間隔使得不同的決策超平面存在挪略，那么如果樣本點(diǎn)繼續(xù)增加病梢，這些決策超平面中那個(gè)分類效果最好呢傲须？也就是說誰的泛華效果最好呢造虎？——這就是支持向量機(jī)要解決的主要問題块攒，也是支持向量機(jī)與感知機(jī)的主要區(qū)別谦疾。

2）支持向量

就上面的圖來說南蹂，主觀上看哪個(gè)超平面的分類泛化能力最強(qiáng)呢？我們認(rèn)為紅色的那條可能會(huì)比較好念恍，這條線距離最近的紅點(diǎn)區(qū)域和最近的藍(lán)點(diǎn)區(qū)域都比較遠(yuǎn)六剥，無論是紅點(diǎn)還是藍(lán)點(diǎn)晚顷，再向靠近超平面的方向增加一些點(diǎn)都沒問題，還可以被這條超平面分的比較開疗疟，那兩條虛線就沒有這么好的效果该默，如下圖所示，我們新增幾個(gè)點(diǎn)策彤，可以看出其分類效果的差別：

似乎可以得出這樣的結(jié)論：超平面離直線兩邊的數(shù)據(jù)的間隔越大栓袖，對訓(xùn)練集的數(shù)據(jù)的局限性或噪聲有最大的容忍能力，也就是所謂的魯棒性店诗。

所以裹刮，如果所有的樣本點(diǎn)不只是可以被決策超平面分開，還和超平面保持一定的距離間隔庞瘸，那么這樣的分類超平面是更優(yōu)的捧弃，支持向量機(jī)就是要找到使這個(gè)間隔最大的決策超平面（即最大化下圖中的margin）。訓(xùn)練樣本中和這個(gè)超平面距離最近的樣本點(diǎn)被稱為支持向量擦囊，如下圖虛線所經(jīng)過的樣本點(diǎn)即為支持向量：

3）函數(shù)間隔违霞、幾何間隔

最大化間隔的思想我們大概了解了，不過要最大化這個(gè)間隔首先得量化霜第，怎么量化呢葛家？

支持向量是距離分類超平面最近的樣本點(diǎn)，那么樣本點(diǎn)距離超平面的距離不就是支持向量與分類超平面的距離嗎泌类？在前面的幾篇文章中我們也經(jīng)常提到樣本點(diǎn)到超平面的距離的度量癞谒，這里我們就稍微詳細(xì)點(diǎn)說下函數(shù)間隔和幾何間隔。

函數(shù)間隔

在決策超平面 $??^????+??=0$ 確定的情況下刃榨， $|??^????+??|$ 能夠表示點(diǎn) $x$ 到超平面的距離遠(yuǎn)近弹砚； $??^????+??$ 和 $y$ 是否同號能夠表示分類是否正確，所以可用 $y(??^????+??)$ 來表示分類的正確性及確定性枢希，我們在羅輯回歸和感知機(jī)中就有類似的用法桌吃，這就是函數(shù)間隔的概念，定義函數(shù)間隔 $??′$ 為：

$\gamma^{'} = y(w^Tx + b)$

幾何間隔

函數(shù)間隔雖然可以表示分類的正確性和確定性苞轿，但其缺點(diǎn)是只能在一個(gè)確定的超平面 $??^????+??=0$ 下比較樣本點(diǎn)到超平面的相對距離茅诱，不同參數(shù)的超平面條件下計(jì)算的距離是不能比較大小的，比如超平面 $2??^????+2??=0$ 與 $??^????+??=0$ 是同一個(gè)超平面搬卒，樣本點(diǎn)與其真實(shí)距離沒有變化瑟俭，但是函數(shù)距離卻翻了一倍，因此我們需要將參數(shù)加以約束契邀，使其具備可比性摆寄，我們定義幾何間隔：

$\gamma = \frac{y(w^Tx + b)}{||w||_2} = \frac{\gamma^{'}}{||w||_2}$

可見，幾何間隔才是點(diǎn)到超平面的真正距離，上一篇感知機(jī)中的損失函數(shù)正是幾何間隔的形式微饥，我們支持向量機(jī)也使用幾何間隔來表示支持向量到分類超平面的間隔逗扒，如上圖中的margin即為兩個(gè)支持向量與超平面的幾何間隔之和 $\frac{2}{||w||_2}$ 。

4）線性可分支持向量機(jī)模型

綜合上述內(nèi)容可知欠橘，線性可分支持向量機(jī)可以表示為：

$f(x)=sign(w^*x+b^*)$

式中矩肩， $w^*x+b^*=0$ 為與支持向量間隔最大化的分類超平面，可見與感知機(jī)是基本一樣的简软，就多了個(gè)間隔最大化的要求蛮拔。

2 支持向量機(jī)模型求解

1）目標(biāo)函數(shù)

通過上述已知述暂，支持向量機(jī)是要最大化支持向量與決策超平面之間的幾何間隔痹升，所以目標(biāo)函數(shù)為：

$\max_{w,b} \;\; \gamma = \frac{y(w^Tx + b)}{||w||_2} \;\; s.t \;\; \frac{y_i(w^Tx_i + b)}{||w||_2} \geq \gamma ,i =1,2,...m$

這個(gè)式子表示，最大化訓(xùn)練樣本與超平面的幾何間隔 $??$ 畦韭，同時(shí)要保證約束條件每個(gè)訓(xùn)練樣本與超平面的幾何距離不小于 $??$ 疼蛾，目標(biāo)函數(shù)可以改寫為：

$\max_{w,b} \;\; \gamma=\frac{??′}{||w||_2}\;\; s.t \;\; y_i(w^Tx_i + b) \geq ??′ ,i =1,2,...m$

一般我們都取函數(shù)間隔 $??′$ 為1，為什么呢艺配，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%F0%9D%9B%BE%E2%80%B2" alt="??′" mathimg="1">的取值不影響最優(yōu)化問題的解察郁，假設(shè) $??′$ 不為1，就相當(dāng)于 $w$ 和 $b$ 變?yōu)榱?img class="math-inline" src="https://math.jianshu.com/math?formula=%F0%9D%9B%BE%E2%80%B2w" alt="??′w" mathimg="1">和 $??′b$ 转唉，對目標(biāo)函數(shù)和約束不等式都沒有影響皮钠，都是可以約掉的，所以 $??′$ 為1完全沒問題赠法，此時(shí)最優(yōu)化問題變?yōu)椋?/p>

$\max_{w,b} \;\; \frac{1}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 ,i =1,2,...m$

可以轉(zhuǎn)變?yōu)椋?/p>

$\min_{w,b} \;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 ,i =1,2,...m$

（有的地方說要最大化margin同時(shí)保證兩類的支持向量到超平面的距離相等麦轰，所以有 $max\frac{2}{||w||_2}$ ，個(gè)人認(rèn)為這個(gè)解釋很牽強(qiáng)砖织，明明優(yōu)化 $\gamma$ 的過程中兩類就會(huì)互相博弈找到這個(gè)最優(yōu)的超平面）根據(jù)下面定義的描述發(fā)現(xiàn)款侵，這個(gè)凸最優(yōu)化問題是一個(gè)凸二次規(guī)劃問題（convex quadratic programming）。

目標(biāo)函數(shù)和約束條件都為變量的線性函數(shù)——線性規(guī)劃問題侧纯；
目標(biāo)函數(shù)為變量的二次函數(shù)和約束條件為變量的線性函數(shù)——二次規(guī)劃問題新锈；
目標(biāo)函數(shù)和約束條件都為非線性函數(shù)——非線性規(guī)劃問題。

2）對偶問題轉(zhuǎn)化及求解

在感知機(jī)中我們說過眶熬，利用對偶問題可以從不同角度看待同一個(gè)問題妹笆，可能會(huì)引入新的參數(shù)來幫助我們優(yōu)化，在約束最優(yōu)化問題中娜氏，常常利用拉格朗日對偶性(Lagrange duality)將原始問題轉(zhuǎn)換為對偶問題拳缠，通過解對偶問題得到原始問題的解。

首先我們的優(yōu)化目標(biāo)函數(shù)可以使用拉格朗日乘子法（詳細(xì)內(nèi)容見附錄）轉(zhuǎn)變成拉格朗日函數(shù)：

$L(w,b,\lambda)= \frac{1}{2}||w||_2^2 +\sum_i^m \lambda_i [1-y_i(w^Tx_i + b)], \; \lambda_i\geq0$

目標(biāo)函數(shù)的優(yōu)化轉(zhuǎn)變?yōu)椋?/p>

$\min_{w,b}\;\max_{\lambda}\; L(w,b,\lambda)$

這一步是什么意思呢牍白，因?yàn)榧s束不等式 $1-y_i(w^Tx_i + b)\leq 0,\lambda_i\geq 0$ 脊凰，所以加號后面整體小于等于0，只有當(dāng)其取最大值是為0，此時(shí) $\max_{\lambda}\; L(w,b,\lambda)= \frac{1}{2}||w||_2^2$ 狸涌，即為原目標(biāo)函數(shù)切省，這個(gè)變形稱為廣義拉格朗日函數(shù)的極小極大問題，它與原問題是完全等價(jià)的帕胆，在對偶性中朝捆，這個(gè)問題被稱為原始問題（Primal problem）。

這個(gè)優(yōu)化函數(shù)滿足KKT條件（詳細(xì)內(nèi)容見附錄）懒豹，可以實(shí)現(xiàn)強(qiáng)對偶芙盘，即可以通過拉格朗日對偶（Lagrange duality）將其轉(zhuǎn)化為等價(jià)的對偶問題：

$\max_{\lambda}\;\min_{w,b}\; L(w,b,\lambda)$

所以我們可以先求優(yōu)化函數(shù)極小值對應(yīng)的 $w$ 和 $b$ ，再求的極大值對應(yīng)的拉格朗日乘子系數(shù) $\lambda$ ：

$\frac{\partial L}{\partial w} = 0 \;\rightarrow w+\sum_i^m \lambda_iy_ix_i=0 \;\rightarrow w = \sum_{i=1}^{m}\lambda_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \;\rightarrow \sum_i^m \lambda_iy_i=0$

優(yōu)化函數(shù)取得極小值時(shí)脸秽， $w$ 可以用 $\lambda$ 儒老，而 $b$ 無所謂，取什么值都不影響優(yōu)化函數(shù)取得極小值记餐，所以可得：

$\begin{align} J(\lambda)&=\min_{w,b}\; L(w,b,\lambda)\\&= \frac{1}{2}||w||_2^2 +\sum_i^m \lambda_i [1-y_i(w^Tx_i + b)]\\ &= \frac{1}{2}w^Tw-\sum_{i=1}^{m}\lambda_iy_iw^Tx_i - \sum_{i=1}^{m}\lambda_iy_ib + \sum_{i=1}^{m}\lambda_i\\ &= \frac{1}{2}\sum_{i=1}^{m}(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i-(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i- \sum_{i=1}^{m}\lambda_iy_ib + \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1}^{m}(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i- b\sum_{i=1}^{m}\lambda_iy_i + \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1}^{m}\lambda_iy_ix_i^T\sum_{i=1}^{m}\lambda_iy_ix_i+ \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j+ \sum_{i=1}^{m}\lambda_i \end{align}$

$J(\lambda)$ 完全是關(guān)于參數(shù) $\lambda$ 的函數(shù)驮樊，因此：
$\max_{\lambda}\;\min_{w,b}\; L(w,b,\lambda)=\max_{\lambda}\;J(\lambda)=\max_{\lambda}\;-\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j+ \sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\lambda_i\geq0$

轉(zhuǎn)化為：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\lambda_i\geq0$

求出上式取得極小值時(shí)對應(yīng)的 $\lambda$ 向量就可以求出 $w$ 和 $b$ 了，這里一般需要用到SMO(Sequential Minimal Optimization片酝，序列最小優(yōu)化算法) 算法囚衔，還是比較復(fù)雜的，下面來看看怎么做雕沿。

3）序列最小優(yōu)化算法（SMO）

上述最優(yōu)化問題是要求解 $m$ 個(gè)參數(shù) $(λ_1,λ_2,λ_3,...,λ_m)$ 练湿，其他參數(shù)均為已知，有多種算法可以對上述問題求解审轮，比如之前介紹過的次梯度下降應(yīng)該就可以肥哎，但是算法復(fù)雜度均很大。序列最小最優(yōu)化算法(SMO)可以高效的求解上述SVM問題断国，它把原始求解N個(gè)參數(shù)二次規(guī)劃問題分解成很多個(gè)子二次規(guī)劃問題分別求解贤姆，每個(gè)子問題只需要求解兩個(gè)參數(shù)，方法類似于坐標(biāo)上升稳衬，節(jié)省時(shí)間成本和降低了內(nèi)存需求霞捡。每次啟發(fā)式選擇兩個(gè)變量進(jìn)行優(yōu)化，不斷循環(huán)薄疚，直到達(dá)到函數(shù)最優(yōu)值碧信。

為什么每次優(yōu)化兩個(gè)參數(shù)呢？像坐標(biāo)下降不是每次只優(yōu)化一個(gè)參數(shù)嗎街夭？因?yàn)槲覀冞@里有個(gè)約束砰碴， $\sum_i^m \lambda_iy_i=0$ ，如果認(rèn)為m-1個(gè)都是固定值板丽，那么剩下的那個(gè)也就確定了呈枉，所以選擇每次優(yōu)化兩個(gè)趁尼。因?yàn)镾MO比較復(fù)雜，本篇文章就不細(xì)說了猖辫，這里先這樣提一下SMO酥泞，大家知道上面的優(yōu)化是用SMO計(jì)算的就好。

使用SMO算法啃憎，我們得到了 $\max_{λ}\;J(λ)$ 對應(yīng)的 $λ^*$ 芝囤，所以：

$w = \sum_{i=1}^{m}λ_i^*y_ix_i$

因?yàn)閷χС窒蛄坑校?img class="math-inline" src="https://math.jianshu.com/math?formula=y_i(w%5ETx_i%2Bb)%3D1" alt="y_i(w^Tx_i+b)=1" mathimg="1">，所以要根據(jù)這個(gè)等式解出 $b$ 需要將支持向量樣本點(diǎn)代入辛萍，怎么獲得支持向量呢悯姊？KKT條件中的對偶互補(bǔ)條件 $λ_i(y_i(w^Tx_i+b)?1)=0$ ，我們已經(jīng)求出了 $λ^*$ 贩毕，如果 $λ_i>0$ 則有 $y_i(w^Tx_i+b)=1$ 悯许，即樣本點(diǎn)為支持向量，求解 $b$ ：

$y_i^2(w^Tx_i+b)=y_i$

$b=y_i-w^Tx_i= y_i-\sum_{i=1}^{m}λ_i^*y_ix_i^Tx_i$

顯然耳幢，支持向量大多不止一個(gè)岸晦，對線性可分支持向量機(jī)來說欧啤，可以證明分類超平面是存在且唯一的睛藻， $b$ 的解也就只有一個(gè)，此時(shí)用不同的支持向量求出來的 $b$ 都是相同的邢隧，如果數(shù)據(jù)有噪聲店印，并不是完全線性可分的，那么為了增加模型的魯棒性倒慧， $b$ 取所有值的平均值按摘，即假設(shè)有n個(gè)支持向量，則：

$b=\frac{1}{n}\sum_i^n (y_i-w^Tx_i)$

至此纫谅，線性可分支持向量機(jī)的模型參數(shù)就求出來了炫贤，模型也就確定了。

4）線性可分支持向量機(jī)算法流程

綜合以上全部內(nèi)容付秕，可以得到線性可分支持向量機(jī)的算法流程：

輸入：線性可分的樣本 $T=(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ 兰珍， $x$ 為 $n$ 維特征向量， $y\in[+1,-1]$ 询吴；

輸出： $w,b$ 掠河，支持向量機(jī)模型 $f(x)=sign(w^Tx+b)$ 。

確定目標(biāo)函數(shù)：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\lambda_i\geq0$

使用SMO優(yōu)化目標(biāo)函數(shù)猛计，得到對應(yīng)的 $λ^*$ 唠摹；

根據(jù) $λ^*$ 找到樣本中的共k=1個(gè)支持向量，計(jì)算參數(shù) $w,b$ ：

$w^* = \sum_{i=1}^{m}λ_i^*y_ix_i$

$b^*=\frac{1}{k}\sum_i^k (y_i-w^Tx_i)$

得到支持向量機(jī)模型 $f(x)=sign(w^{*T}x+b^*)$ 奉瘤。

3 線性可分支持向量機(jī)小結(jié)

線性可分支持向量機(jī)假設(shè)數(shù)據(jù)是線性可分的勾拉，這點(diǎn)跟感知機(jī)、邏輯回歸是一樣的，就是為了最大化間隔才使得線性可分SVM的理論復(fù)雜了這么多藕赞，不過對于非線性可分的數(shù)據(jù)還是沒法處理苛秕，怎么辦呢？我們接下來看一下基于軟間隔最大化的線性支持向量機(jī)（linear support vector machine）找默。

附錄

1）拉格朗日乘子法

拉格朗日乘子法是一種尋找多元函數(shù)在一組約束下的極值的方法艇劫，通過引入拉格朗日乘子，可將有d個(gè)變量與k個(gè)約束條件的優(yōu)化問題轉(zhuǎn)換為具有d+k個(gè)變量的無約束優(yōu)化問題惩激。這種方法引入了一種新的標(biāo)量未知數(shù)店煞，即拉格朗日乘子：它是約束方程的梯度的線性組合中，每個(gè)梯度向量的系數(shù)风钻。

（1）無約束條件
我們一般對函數(shù)變量求導(dǎo)顷蟀，令導(dǎo)數(shù)等于0的點(diǎn)認(rèn)為是極值點(diǎn)。

（2）等式約束條件
設(shè)目標(biāo)函數(shù)為 $f(x)$ 骡技，約束條件為 $h_i(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n$

對于這種形式的優(yōu)化問題我們一般使用拉格朗日乘子法（Lagrange multiplier）鸣个，當(dāng)然也能用消元法，不過太麻煩了布朦，先從幾何上理解拉格朗日乘子法（以二維為例）囤萤，假設(shè)要求f(x,y)極值，約束條件 $h(x,y)=0$ 是趴，函數(shù) $f(x,y)$ 相當(dāng)于其在三維坐標(biāo)系下 $f(x,y)$ 的等高線涛舍， $h(x,y)=0$ 是一條曲線，試想如果是等高線與曲線的相交點(diǎn)唆途，說明曲線還可以沿著等高線變大或變小的方向走下去富雅，必然不是極值點(diǎn)，所以約束曲線 $h(x,y)=0$ 與某一條等高線 $f(x,y)=a$ 相切時(shí)肛搬，函數(shù)取得極值：

在切點(diǎn)處 $h(x,y)=0$ 與 $f(x,y)$ 的法向量共線没佑，也就是函數(shù) $f(x,y)$ 與 $h(x,y)$ 在切點(diǎn)處的梯度平行，有：

$\nabla f=λ'\nabla h$

因此滿足：

$\begin{cases} \nabla f+λ\nabla h=0 \\ \\ h(x,y)=0 \end{cases}$

即為約束下目標(biāo)函數(shù)的極值點(diǎn)温赔，也可以寫成我們常見的：

$F(x,y)=f(x,y)+λh(x,y)$

因?yàn)閷ζ淝髮?dǎo)并令導(dǎo)數(shù)為0可得：

$\begin{cases} \frac{\partial F}{\partial (x,y)}=\nabla f+λ\nabla h =0 \\ \\ \frac{\partial F}{\partial λ}=h(x,y)=0 \end{cases}$

跟上面的方程組是一樣的蛤奢，這也是從代數(shù)上理解拉格朗日乘子法的方式，因此拉格朗日乘子法可以用來求多元函數(shù)在一組等式約束下的極值让腹。

（3）不等式約束條件
設(shè)目標(biāo)函數(shù) $f(x)$ 远剩，不等式約束為 $g(x)$ ，等式約束條件 $h(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n \\ \;\;g_j(x)\leq0,\;\;j=1,2,...,m$

在不等式約束下骇窍，極值點(diǎn)的位置可能有兩種情況瓜晤，一種是極值點(diǎn)被不等式約束包含，如下左圖所示腹纳；另一種是極值點(diǎn)沒有被不等式約束包含痢掠，如下右圖所示：

對于第一種情況來說驱犹，顯然滿足 $\nabla f=0$ 即可，對于第二種情況足画，依然是等高線與不等式的邊界相切的點(diǎn)為極值點(diǎn)雄驹，可知：

$\begin{cases} \nabla f+\mu\nabla h=0 \\ \\ h(x,y)=0 \end{cases}$

看起來似乎跟等式約束的一樣，其實(shí)是有一些區(qū)別的淹辞，我們知道医舆，等高線在切點(diǎn)處的梯度（也就是切線的法向量）的方向是向著等高線值增大的方向的，對于圖示的凸函數(shù)來說象缀，就是如圖所示向外的蔬将，而對于不等式 $g_j(x)\leq0$ ，其梯度方向必然是相反朝向的央星，因?yàn)樘荻纫赶蛟鲩L的方向霞怀，肯定會(huì)指向 $g_j(x)>0$ 的方向了：

因此，等式約束的拉格朗日乘子 $λ$ 沒有符號限制莉给，而不等式約束的拉格朗日乘子 $\mu\geq 0$ 毙石，所以將初始求極值問題轉(zhuǎn)化為：

$\begin{cases} \nabla f+\mu\nabla h=0 \\ \\ h(x,y)=0 \\ \\ \mu\geq 0 \end{cases}$

可以寫成我們常見的：

$F(x,y)=f(x,y)+\sum_i^nλ_ih_i(x,y)+\sum_j^m\mu_j g_j(x,y), \;\; \mu_j\geq 0$

2）KKT條件

仍然是設(shè)目標(biāo)函數(shù) $f(x)$ ，不等式約束為 $g(x)$ 颓遏，等式約束條件 $h(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n \\ \;\;g_j(x)\leq0,\;\;j=1,2,...,m$

通過拉格朗日乘子法我們可以將求有約束的函數(shù)極值的問題統(tǒng)一轉(zhuǎn)化為求解：

$\begin{cases} \nabla f+\sum_i^nλ_i\nabla h_i+\sum_j^m\mu_j \nabla g_j=0 \\ \\ h_i=0,i=1,2,...,n \\ \\ g_j\leq 0,j=1,2,...,m \\ \\ \mu_i\geq 0\\ \\ \mu_j g_j= 0 \end{cases}$

這個(gè)方程組也就是所謂的KKT條件徐矩，前面四項(xiàng)應(yīng)該都比較好理解，最后一個(gè) $\mu_j g_j= 0$ 是什么意思呢州泊？在上一節(jié)不等式約束中丧蘸，第一種情況不等式約束相當(dāng)于不影響極值點(diǎn)，所以 $\mu_j= 0 遥皂， g_j\leq 0$ ，在第二種情況中使用不等式的邊界刽漂，有 $\mu_j\geq 0 演训， g_j= 0$ 。