在前面的幾講中肛搬，我們終于引出了支撐向量的概念饭豹，同時(shí)得到了求解最大間隔分類器的目標(biāo)規(guī)劃式鸵赖，接下來务漩，我們就要對(duì)該式進(jìn)行求解，但在正式求解之前它褪，我想介紹一下求解需要了解的兩個(gè)知識(shí)饵骨，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件。在求解最優(yōu)化問題中茫打，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法居触。在有等式約束時(shí)使用拉格朗日乘子法，在有不等約束時(shí)使用KKT條件老赤。這一節(jié)轮洋，我們先來介紹拉格朗日乘子法。
我們這里提到的最優(yōu)化問題通常是指對(duì)于給定的某一函數(shù)诗越，求其在指定作用域上的全局最小值(因?yàn)樽钚≈蹬c最大值可以很容易轉(zhuǎn)化砖瞧，即最大值問題可以轉(zhuǎn)化成最小值問題)息堂。 一般情況下嚷狞，最優(yōu)化問題會(huì)碰到一下三種情況：
1、無約束條件
這是最簡(jiǎn)單的情況荣堰，解決方法通常是函數(shù)對(duì)變量求導(dǎo)床未，令求導(dǎo)函數(shù)等于0的點(diǎn)可能是極值點(diǎn)。將結(jié)果帶回原函數(shù)進(jìn)行驗(yàn)證即可振坚。
2薇搁、等式約束條件
這里的等式約束條件一般形式如下：
則解決方法是消元法或者拉格朗日法。消元法比較簡(jiǎn)單不在贅述渡八，這里主要講拉格朗日法啃洋，因?yàn)楹竺嫣岬降腒KT條件是對(duì)拉格朗日乘子法的一種泛化。
我們先通過一個(gè)例子來直觀感受下拉格朗日乘子法屎鳍，至于為什么這么做是可行的宏娄，后面會(huì)進(jìn)一步介紹。
假設(shè)我們的目標(biāo)函數(shù)如下：
約束條件如下：
拉格朗日乘子法的一般做法是將約束條件加入到目標(biāo)函數(shù)中逮壁，將問題轉(zhuǎn)化為無約束條件的問題孵坚，隨后對(duì)參數(shù)進(jìn)行求導(dǎo)解得極值。
到我們的題目中窥淆，我們將有約束的最優(yōu)化問題轉(zhuǎn)換為無約束的最優(yōu)化問題如下：
可以看到卖宠，現(xiàn)在的問題中有四個(gè)參數(shù)瞧筛，我們分別對(duì)四個(gè)參數(shù)求偏導(dǎo)數(shù)：
對(duì)后聯(lián)立四個(gè)方程可以求解得到：
則最優(yōu)化問題的解是：
3镐捧、拉格朗日乘子法的解釋
為什么這么做是可行的呢媒怯？維基百科上的解釋很好厌衔，這里我拿來用一下底循。以一個(gè)最簡(jiǎn)單的二維優(yōu)化問題為例：
min f(x,y)
s.t. g(x,y) = c
這里畫出z=f(x,y)的等高線：
綠線標(biāo)出的是約束g(x,y)=c的點(diǎn)的軌跡寨昙。藍(lán)線是f(x,y)的等高線衅疙。箭頭表示斜率贝咙，和等高線的法線平行。從梯度的方向上來看作媚，顯然有d1>d2攘滩。綠色的線是約束，也就是說纸泡，只要正好落在這條綠線上的點(diǎn)才可能是滿足要求的點(diǎn)漂问。如果沒有這條約束，f(x,y)的最小值應(yīng)該會(huì)落在最小那圈等高線內(nèi)部的某一點(diǎn)上女揭。而現(xiàn)在加上了約束蚤假，最小值點(diǎn)應(yīng)該在哪里呢？顯然應(yīng)該是在f(x,y)的等高線正好和約束線相切的位置吧兔，因?yàn)槿绻皇窍嘟灰馕吨隙ㄟ€存在其它的等高線在該條等高線的內(nèi)部或者外部磷仰，使得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切的時(shí)候境蔼，可能取得最優(yōu)值灶平。
相切的時(shí)候滿足什么條件呢？從圖上的梯度方向箭頭可以很明顯的看出來箍土，相切的時(shí)候f(x,y)和g(x,y)的梯度一定是在同一個(gè)方向上的逢享，也就是說?f(x,y)=λ（?g(x,y)-C) ，這里?代表函數(shù)的梯度吴藻。
這時(shí)候再來看我們的之前例子的求解過程瞒爬，我們對(duì)所有參數(shù)求偏導(dǎo)數(shù)：
令上面式子中的前三個(gè)等于0，其實(shí)就是令?f(x,y)=λ（?g(x,y)-C)沟堡，
而第四個(gè)式子恰好是使求得的x,y,z滿足我們?cè)械募s束條件侧但。所以可以看到，拉格朗日乘子法在求解等式約束條件的最優(yōu)化問題時(shí)是可行的航罗！
之前我們說最優(yōu)化問題會(huì)碰到一下三種情況禀横，這一講只介紹了兩種，第三種我們將留到下一講中介紹伤哺！
