拉格朗日乘數(shù)法是我見(jiàn)過(guò)的最容易被低估的最優(yōu)化工具。它表面上是高等數(shù)學(xué)里的一個(gè)章節(jié)實(shí)際上是解決帶約束極值問(wèn)題的核心方法也是支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)正則化、經(jīng)濟(jì)學(xué)效用最大化等許多方向的數(shù)學(xué)基礎(chǔ)。這篇文章不打算把教材定理重新抄一遍而是從“為什么要引入它”開(kāi)始用一個(gè)小案例把幾何直覺(jué)、構(gòu)造步驟、乘子含義和KKT延伸一起講清楚。適合正在學(xué)高數(shù)、準(zhǔn)備考研、或者剛開(kāi)始接觸機(jī)器學(xué)習(xí)和最優(yōu)化理論的人看。1. 拉格朗日乘數(shù)法到底在解決什么問(wèn)題1.1 先看一個(gè)最簡(jiǎn)單的帶約束極值問(wèn)題一個(gè)長(zhǎng)方形周長(zhǎng)固定是20長(zhǎng)和寬分別是x和y面積最大是多少這個(gè)經(jīng)典問(wèn)題可以寫成最大化 f(x, y) xy約束條件 2x 2y 20也就是 x y 10。如果用中學(xué)方法把 y 10 - x 代入面積公式變成一個(gè)一元二次函數(shù)求頂點(diǎn)就能得到答案x 5y 5最大面積是25。這個(gè)方法很直接很多人在這一步會(huì)覺(jué)得“拉格朗日乘數(shù)法不是多此一舉嗎”。這里要區(qū)分一個(gè)概念。普通求極值問(wèn)題是在整個(gè)定義域里找最大最小值帶約束極值問(wèn)題是在一條線、一個(gè)面或者一個(gè)更小的集合里找最值。后者比前者復(fù)雜因?yàn)榭尚蟹秶辉偈恰八悬c(diǎn)”而是被約束切出來(lái)的一個(gè)子集。拉格朗日乘數(shù)法處理的正是約束優(yōu)化問(wèn)題尤其是等式約束下的極值問(wèn)題。1.2 代入法看起來(lái)夠用但適用范圍很窄為什么不能所有問(wèn)題都用代入法因?yàn)榇敕ㄒ蕾嚰s束條件能夠被解成某個(gè)變量的顯式表達(dá)式。如果約束是 x^2 y^2 1可以把 y 解成 ±sqrt(1 - x^2)但是要考慮正負(fù)號(hào)計(jì)算量已經(jīng)變大。如果約束是 x*y z 5同時(shí)還有一個(gè)約束 x^2 y^2 z^2 1再想通過(guò)代入消元計(jì)算會(huì)非常復(fù)雜甚至無(wú)法用初等函數(shù)寫出解析解。更現(xiàn)實(shí)的情況是變量可能不是3個(gè)而是幾十個(gè)、幾百個(gè)。工程里的優(yōu)化問(wèn)題變量維度很高約束條件也很多完全靠代入法手算基本不成立。拉格朗日乘數(shù)法不要求解出約束表達(dá)式而是把約束作為一個(gè)整體放進(jìn)一個(gè)新的函數(shù)里把有約束問(wèn)題轉(zhuǎn)化成“解一個(gè)方程組”的問(wèn)題。這個(gè)思路在機(jī)器學(xué)習(xí)和最優(yōu)化里非常關(guān)鍵也是它能夠成為通用工具的原因。2. 用一個(gè)二維小案例把幾何直覺(jué)建立起來(lái)2.1 等高線目標(biāo)函數(shù)在平面上的“地圖”先看目標(biāo)函數(shù) f(x, y) x^2 y^2。它像一個(gè)碗碗底在原點(diǎn)越往外高度越大。如果把相同高度 f c 的點(diǎn)畫出來(lái)就得到等高線。對(duì) x^2 y^2 來(lái)說(shuō)等高線是一圈一圈的圓半徑為1、2、3分別對(duì)應(yīng) f 1、4、9。約束條件 g(x, y) 0 也是一條曲線。比如 x y - 10 0 是一條直線x^2 y^2 - 1 0 是一個(gè)單位圓?，F(xiàn)在的問(wèn)題變成在約束曲線這條“路徑”上找一個(gè)點(diǎn)使得目標(biāo)函數(shù)在路徑上達(dá)到最大值或最小值。我建議學(xué)習(xí)這個(gè)方法的第一個(gè)動(dòng)作不是背公式而是畫圖。拿坐標(biāo)系紙把等高線的幾個(gè)圈畫出來(lái)再把約束曲線畫上去。你會(huì)看到在極值點(diǎn)附近目標(biāo)函數(shù)的等高線正好與約束曲線相切。切點(diǎn)就是候選極值點(diǎn)。2.2 極值點(diǎn)處的關(guān)鍵條件梯度與約束方向平行為什么極值點(diǎn)對(duì)應(yīng)“相切”因?yàn)樵诩s束曲線上移動(dòng)時(shí)如果目標(biāo)函數(shù)值還能繼續(xù)變大或變小那當(dāng)前位置就不是極值。只有在極值點(diǎn)上沿任意可行方向移動(dòng)目標(biāo)函數(shù)的一階變化量都等于0。對(duì)等式約束來(lái)說(shuō)可行方向是約束曲線的切線方向。要讓目標(biāo)函數(shù)在切線方向上的變化率為0目標(biāo)函數(shù)的梯度?f必須和切線方向垂直。而約束曲線的法向量是?g切線方向和法向量垂直所以?f必須和?g平行。于是得到必要條件存在一個(gè)實(shí)數(shù)λ使梯度條件成立。?f λ?g這個(gè)λ就是拉格朗日乘子。引入拉格朗日函數(shù) L f - λg 或者 L f λg分別對(duì)變量和乘子求偏導(dǎo)并令其等于0就可以得到一組方程。對(duì)乘子求偏導(dǎo)時(shí)得到的是原約束條件 g 0。這里有一個(gè)常見(jiàn)的符號(hào)困惑為什么有些教材用 L f - λg有些用 L f λg因?yàn)棣吮旧砜烧韶?fù)符號(hào)約定不同只會(huì)讓?duì)说娜≈底兲?hào)最終求出的極值點(diǎn)坐標(biāo)不會(huì)變。學(xué)習(xí)時(shí)固定一種寫法就行不用糾結(jié)。3. 拉格朗日函數(shù)和乘子從構(gòu)造到解釋3.1 構(gòu)造拉格朗日函數(shù)的兩個(gè)版本最常見(jiàn)的形式是L(x, y, λ) f(x, y) λ g(x, y)把三個(gè)變量分別求偏導(dǎo)?L/?x ?f/?x λ ?g/?x 0?L/?y ?f/?y λ ?g/?y 0?L/?λ g(x, y) 0如果采用減號(hào)形式L f - λg求偏導(dǎo)后變成?f/?x - λ ?g/?x 0?f/?y - λ ?g/?y 0g 0這兩個(gè)版本的極值點(diǎn)條件完全相同只是λ的符號(hào)相反。我一般建議新手統(tǒng)一用加號(hào)版本因?yàn)閷?duì)λ求導(dǎo)時(shí)約束項(xiàng)直接就是g(x, y)不容易出現(xiàn)負(fù)號(hào)錯(cuò)誤。還有一點(diǎn)值得注意約束條件寫成 g(x, y) 0 時(shí)L 中的約束項(xiàng)是 λ 乘以 g。如果原始約束寫成 x y 10那要先把右側(cè)移到左側(cè)寫成 x y - 10 0然后放入拉格朗日函數(shù)。這一步看起來(lái)簡(jiǎn)單實(shí)際上很容易忽略。約束不寫成標(biāo)準(zhǔn)形式后面求偏導(dǎo)就會(huì)出錯(cuò)。3.2 λ到底是什么意思邊際影響與符號(hào)判斷λ不是可有可無(wú)的中間變量。它有一個(gè)非常重要的解釋如果把約束條件的右側(cè)常數(shù)當(dāng)作一種資源約束那么λ表示資源每增加一個(gè)單位目標(biāo)函數(shù)最優(yōu)值的邊際變化量。在經(jīng)濟(jì)學(xué)里這被稱為“影子價(jià)格”。舉個(gè)例子。目標(biāo)函數(shù)是收益約束條件是總資源不能超過(guò)某個(gè)數(shù)量。算出來(lái)的λ2意味著資源上限每提高1個(gè)單位最大收益大約增加2個(gè)單位。這個(gè)近似在資源變化比較小時(shí)成立。如果λ是負(fù)數(shù)也不用慌。λ的符號(hào)和拉格朗日函數(shù)的寫法有關(guān)也和你定義的是“最大化”還是“最小化”有關(guān)。我見(jiàn)過(guò)不少同學(xué)為了λ正負(fù)討論很長(zhǎng)時(shí)間最后發(fā)現(xiàn)只是符號(hào)約定不同。更值得關(guān)注的是約束是否“緊”。如果約束處于激活狀態(tài)即 g 0λ才有經(jīng)濟(jì)解釋如果約束不激活那點(diǎn)的λ通常等于0對(duì)應(yīng)KKT里的互補(bǔ)松弛條件。4. 手算一個(gè)完整案例二次目標(biāo)加線性約束4.1 建模和求偏導(dǎo)用一個(gè)經(jīng)典例子來(lái)走完整流程。求 f(x, y) x^2 y^2 在約束 x y 10 條件下的最小值。從幾何上看x^2 y^2 是原點(diǎn)到點(diǎn) (x, y) 距離的平方約束 x y 10 是一條直線。問(wèn)題等價(jià)于找直線上離原點(diǎn)最近的點(diǎn)。先改寫成標(biāo)準(zhǔn)約束g(x, y) x y - 10 0。構(gòu)造拉格朗日函數(shù)L(x, y, λ) x^2 y^2 λ(x y - 10)求三個(gè)偏導(dǎo)?L/?x 2x λ 0?L/?y 2y λ 0?L/?λ x y - 10 0由前兩個(gè)方程得到 x -λ/2y -λ/2。代入第三個(gè)方程(-λ/2) (-λ/2) - 10 0得到 -λ 10所以 λ -10x 5y 5。此時(shí) f(5, 5) 50。這個(gè)點(diǎn)就是約束條件下原點(diǎn)到直線距離平方最小的點(diǎn)。4.2 解方程組并判斷極大還是極小求出候選點(diǎn)后還要判斷是極大值還是極小值。最簡(jiǎn)單的方法是幾何驗(yàn)證。原點(diǎn)到直線的最短距離就是垂線距離垂足正是 (5, 5)所以這是極小值。如果目標(biāo)函數(shù)換成 f(x, y) xy約束還是 x y 10那么 (5, 5) 對(duì)應(yīng)的是極大值因?yàn)槊娣e函數(shù)在這個(gè)點(diǎn)達(dá)到最大。不畫圖時(shí)可以用二階條件判斷。對(duì)于多元約束優(yōu)化需要看拉格朗日函數(shù)在約束流形上的二階導(dǎo)數(shù)或者直接借助凸性。如果目標(biāo)函數(shù)是凸函數(shù)約束是凸集那么拉格朗日方程求出的穩(wěn)定點(diǎn)通常就是全局最小值點(diǎn)。如果是凹函數(shù)求出的通常是最大值點(diǎn)。實(shí)際數(shù)值優(yōu)化中拉格朗日乘數(shù)法給出的是必要條件不是充分條件。也就是說(shuō)求出來(lái)的點(diǎn)可能是極值點(diǎn)也可能只是駐點(diǎn)。判斷最終屬性仍然要回到函數(shù)性質(zhì)、約束集合或者二階信息。4.3 換一個(gè)常見(jiàn)變形再驗(yàn)證再做一個(gè)稍有不同的例子。求 f(x, y) xy 在約束 x 2y 8 下的最大值。標(biāo)準(zhǔn)約束為 g(x, y) x 2y - 8 0。構(gòu)造L xy λ(x 2y - 8)求偏導(dǎo)y λ 0x 2λ 0x 2y - 8 0由前兩個(gè)方程得到 λ -yλ -x/2所以 y x/2。代入約束x 2(x/2) x x 8解得 x 4y 2f(4, 2) 8。這個(gè)例子做下來(lái)流程很清晰寫標(biāo)準(zhǔn)約束、構(gòu)造拉格朗日函數(shù)、求三個(gè)偏導(dǎo)、解方程組、代入驗(yàn)證。剛開(kāi)始學(xué)的時(shí)候每一步都要慢把符號(hào)和下標(biāo)寫清楚不要跳步。5. 從等式約束到不等式約束KKT條件是拉格朗日乘數(shù)法的自然延伸5.1 為什么工程里更常看到KKT現(xiàn)實(shí)生活中約束條件更多是不等式而不是等式。比如“預(yù)算不能超過(guò)10元”“使用時(shí)間不能少于5小時(shí)”“某個(gè)權(quán)重必須大于等于0”。這些約束寫出來(lái)都是g(x) ≤ 0或者g(x) ≥ 0處理這類問(wèn)題拉格朗日乘數(shù)法需要擴(kuò)展擴(kuò)展后的條件就是KKT條件。支持向量機(jī)、線性規(guī)劃、二次規(guī)劃、神經(jīng)網(wǎng)絡(luò)正則化等方向最終都會(huì)落到KKT條件上。很多人在機(jī)器學(xué)習(xí)公式里看到KKT覺(jué)得陌生其實(shí)它就是從拉格朗日乘數(shù)法長(zhǎng)出來(lái)的。5.2 KKT條件每一條在說(shuō)什么考慮一個(gè)帶不等式約束的優(yōu)化問(wèn)題最小化 f(x)約束 g_i(x) ≤ 0i 1, 2, ..., m約束 h_j(x) 0j 1, 2, ..., p對(duì)應(yīng)拉格朗日函數(shù)可以寫成L f(x) Σ μ_i g_i(x) Σ λ_j h_j(x)KKT條件大致可以分成幾條。第一條是可行性條件所有不等式約束和等式約束都必須滿足。這一點(diǎn)看起來(lái)是廢話但實(shí)際求解時(shí)經(jīng)常有人忽略。第二條是梯度條件L對(duì)所有變量的偏導(dǎo)等于0。等式約束的乘子λ沒(méi)有正負(fù)限制但不等式約束的乘子μ必須滿足 μ_i ≥ 0。第三條是互補(bǔ)松弛條件μ_i g_i(x) 0互補(bǔ)松弛的意思是如果一個(gè)不等式約束實(shí)際上沒(méi)有起到作用也就是 g_i(x) 0那么它的乘子 μ_i 必須等于0。如果約束被“激活”也就是 g_i(x) 0那么 μ_i 可以大于0。這個(gè)條件從經(jīng)濟(jì)解釋來(lái)看很合理沒(méi)被觸發(fā)的約束不會(huì)帶來(lái)邊際影響乘子為0被嚴(yán)格觸發(fā)的約束才像等式約束一樣有“價(jià)格”或“影子價(jià)格”。很多初學(xué)者第一次看到KKT條件覺(jué)得條件太多。其實(shí)只要把它理解成拉格朗日乘數(shù)法的一個(gè)補(bǔ)丁思路就順了。等式約束部分沿用原來(lái)的思路不等式約束部分增加了“對(duì)偶可行性”和“互補(bǔ)松弛”兩條規(guī)則。5.3 給新手的學(xué)習(xí)順序和常見(jiàn)誤區(qū)學(xué)完等式約束的拉格朗日乘數(shù)法再學(xué)KKT時(shí)要注意幾個(gè)容易踩的坑。第一個(gè)誤區(qū)是只求偏導(dǎo)不管可行性。拉格朗日乘數(shù)法求出的點(diǎn)必須回到約束條件里驗(yàn)證。如果連約束都沒(méi)滿足那再好的候選點(diǎn)也不能要。第二個(gè)誤區(qū)是不判斷極大極小。穩(wěn)定點(diǎn)只是候選點(diǎn)還需要結(jié)合凸性、邊界點(diǎn)或者實(shí)際問(wèn)題背景來(lái)確認(rèn)。工程里如果目標(biāo)函數(shù)不是凸函數(shù)還要警惕局部極值。第三個(gè)誤區(qū)是把λ和μ當(dāng)成沒(méi)有意義的運(yùn)算符號(hào)。理解乘子的邊際含義能幫助你在實(shí)際建模時(shí)判斷哪些約束重要哪些約束可以忽略。第四個(gè)誤區(qū)是跳步。有些教材直接講KKT導(dǎo)致沒(méi)有建立幾何直覺(jué)的人看不懂。我的建議是先畫等高線再手算三四個(gè)等式約束例子等拉格朗日條件熟練了再看不等式約束的互補(bǔ)松弛。如果是為了機(jī)器學(xué)習(xí)接觸拉格朗日乘數(shù)法可以把SVM目標(biāo)函數(shù)作為練習(xí)。在SVM推導(dǎo)中約束是 y_i(w·x_i b) ≥ 1屬于不等式約束。通過(guò)KKT條件可以看出只有支持向量對(duì)應(yīng)的約束乘子非零其他樣本的乘子都是0。這個(gè)例子把互補(bǔ)松弛的實(shí)際意義解釋得非常清楚。學(xué)習(xí)順序可以這樣排先理解約束優(yōu)化的幾何意義再練習(xí)等式約束的拉格朗日乘數(shù)法然后看KKT條件最后到具體應(yīng)用場(chǎng)景里驗(yàn)證。路徑不復(fù)雜但每一步都要?jiǎng)邮炙阋槐?。我也建議準(zhǔn)備一臺(tái)能畫函數(shù)圖像的設(shè)備無(wú)論用Python的matplotlib還是在線繪圖工具把前面例子里的等高線和約束曲線畫出來(lái)。畫過(guò)一次之后很多符號(hào)和條件就不再是死記硬背了。等到真正遇到帶幾十個(gè)約束的優(yōu)化問(wèn)題至少能知道方程組是怎么來(lái)的下一步該怎么排查。