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