拉格朗日乘數(shù)法

　　拉格朗日乘數(shù)法（Lagrange Multiplier Method）之前聽數(shù)學(xué)老師授課的時(shí)候就是一知半解，現(xiàn)在越發(fā)感覺拉格朗日乘數(shù)法應(yīng)用的廣泛性，所以特意抽時(shí)間學(xué)習(xí)了麻省理工學(xué)院的在線數(shù)學(xué)課程。新學(xué)到的知識(shí)一定要立刻記錄下來，希望對(duì)各位有些許幫助。

　　作為一種優(yōu)化算法，拉格朗日乘子法主要用于解決約束優(yōu)化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個(gè)變量和k個(gè)約束條件的約束優(yōu)化問題轉(zhuǎn)化為含有（n+k）個(gè)變量的無約束優(yōu)化問題。拉格朗日乘子背后的數(shù)學(xué)意義是其為約束方程梯度線性組合中每個(gè)向量的系數(shù)。

　　如何將一個(gè)含有n個(gè)變量和k個(gè)約束條件的約束優(yōu)化問題轉(zhuǎn)化為含有（n+k）個(gè)變量的無約束優(yōu)化問題？拉格朗日乘數(shù)法從數(shù)學(xué)意義入手，通過引入拉格朗日乘子建立極值條件，對(duì)n個(gè)變量分別求偏導(dǎo)對(duì)應(yīng)了n個(gè)方程，然后加上k個(gè)約束條件（對(duì)應(yīng)k個(gè)拉格朗日乘子）一起構(gòu)成包含了（n+k）變量的（n+k）個(gè)方程的方程組問題，這樣就能根據(jù)求方程組的方法對(duì)其進(jìn)行求解。

　　解決的問題模型為約束優(yōu)化問題：

　　min/max a function f(x,y,z), where x,y,z are not independent and g(x,y,z)=0.

　　即：min/max f(x,y,z)

　　　　s.t. g(x,y,z)=0

　　首先，我們先以麻省理工學(xué)院數(shù)學(xué)課程的一個(gè)實(shí)例來作為介紹拉格朗日乘數(shù)法的引子。

　　【麻省理工學(xué)院數(shù)學(xué)課程實(shí)例】求雙曲線xy=3上離遠(yuǎn)點(diǎn)最近的點(diǎn)。

　　解：

　　首先，我們根據(jù)問題的描述來提煉出問題對(duì)應(yīng)的數(shù)學(xué)模型，即：

　　min f(x,y)=x2+y2（兩點(diǎn)之間的歐氏距離應(yīng)該還要進(jìn)行開方，但是這并不影響最終的結(jié)果，所以進(jìn)行了簡化，去掉了平方）

　　s.t. xy=3.

　　根據(jù)上式我們可以知道這是一個(gè)典型的約束優(yōu)化問題，其實(shí)我們在解這個(gè)問題時(shí)最簡單的解法就是通過約束條件將其中的一個(gè)變量用另外一個(gè)變量進(jìn)行替換，然后代入優(yōu)化的函數(shù)就可以求出極值。我們在這里為了引出拉格朗日乘數(shù)法，所以我們采用拉格朗日乘數(shù)法的思想進(jìn)行求解。

　　我們將x2+y2=c的曲線族畫出來，如下圖所示，當(dāng)曲線族中的圓與xy=3曲線進(jìn)行相切時(shí)，切點(diǎn)到原點(diǎn)的距離最短。也就是說，當(dāng)f(x,y)=c的等高線和雙曲線g(x,y)相切時(shí)，我們可以得到上述優(yōu)化問題的一個(gè)極值（注意：如果不進(jìn)一步計(jì)算，在這里我們并不知道是極大值還是極小值）。

　　現(xiàn)在原問題可以轉(zhuǎn)化為求當(dāng)f(x,y)和g(x,y)相切時(shí)，x,y的值是多少？

　　如果兩個(gè)曲線相切，那么它們的切線相同，即法向量是相互平行的，▽f//▽g.

　　由▽f//▽g可以得到，▽f=λ*▽g。

　　這時(shí)，我們將原有的約束優(yōu)化問題轉(zhuǎn)化為了一種對(duì)偶的無約束的優(yōu)化問題，如下所示：

　　原問題：min f(x,y)=x2+y2 ? ? ? ?對(duì)偶問題：由▽f=λ*▽g得，

　　　　　　s.t. xy=3 ? ? ? ? ? ? ? ? ? ?fx=λ*gx，

　　 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?fy=λ*gy，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? xy=3.

? ? ? ? ? ? ? ? ? 約束優(yōu)化問題 ? ? ? ? ? 無約束方程組問題

　　通過求解右邊的方程組我們可以獲取原問題的解，即

　　2x=λ*y

　　2y=λ*x

　　xy=3

　　通過求解上式可得，λ=2或者是-2；當(dāng)λ=2時(shí)，(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3))，而當(dāng)λ=-2時(shí)，無解。所以原問題的解為(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3))。

　　通過舉上述這個(gè)簡單的例子就是為了體會(huì)拉格朗日乘數(shù)法的思想，即通過引入拉格朗日乘子(λ)將原來的約束優(yōu)化問題轉(zhuǎn)化為無約束的方程組問題。

?　　求函數(shù)在滿足下的條件極值，可以轉(zhuǎn)化為函數(shù)的無條件極值問題。

　　我們可以畫圖來輔助思考。

　　綠線標(biāo)出的是約束g(x,y)=c的點(diǎn)的軌跡。藍(lán)線是f(x,y)的等高線。箭頭表示斜率，和等高線的法線平行。

　　從圖上可以直觀地看到在最優(yōu)解處，f和g的斜率平行。

　　▽[f(x,y)+λ(g(x,y)?1)]=0, λ≠0

　　一旦求出λ的值，將其套入下式，易求在無約束極值和極值所對(duì)應(yīng)的點(diǎn)。

　　F(x,y)=f(x,y)+λ(g(x,y)?c)

　　新方程F(x,y)在達(dá)到極值時(shí)與f(x,y)相等，因?yàn)镕(x,y)達(dá)到極值時(shí)g(x,y)?c總等于零。

　　上述式子取得極小值時(shí)其導(dǎo)數(shù)為0，即▽f(x)+▽∑λigi(x)=0，也就是說f(x)和g(x)的梯度共線。

　　題目1：

　　給定橢球

?????

　　求這個(gè)橢球的內(nèi)接長方體的最大體積。這個(gè)問題實(shí)際上就是條件極值問題，即在條件? ?

? ??

　　下，求的最大值。

　　當(dāng)然這個(gè)問題實(shí)際可以先根據(jù)條件消去，然后帶入轉(zhuǎn)化為無條件極值問題來處理。但是有時(shí)候這樣做很困難，甚至是做不到的，這時(shí)候就需要用拉格朗日乘數(shù)法了。通過拉格朗日乘數(shù)法將問題轉(zhuǎn)化為

?????

　　對(duì)求偏導(dǎo)得到

?????

　　聯(lián)立前面三個(gè)方程得到和，帶入第四個(gè)方程解之

??????

　　帶入解得最大體積為

??????

　　拉格朗日乘數(shù)法對(duì)一般多元函數(shù)在多個(gè)附加條件下的條件極值問題也適用。

　　題目2：

　　題目：求離散分布的最大熵。

　　分析：因?yàn)殡x散分布的熵表示如下

?????

???? 而約束條件為

?????

???? 要求函數(shù)的最大值，根據(jù)拉格朗日乘數(shù)法，設(shè)

?????

?????對(duì)所有的求偏導(dǎo)數(shù)，得到

?????

???? 計(jì)算出這個(gè)等式的微分，得到

?????

???? 這說明所有的都相等，最終解得

?????

???? 因此，使用均勻分布可得到最大熵的值。

　　我們上述討論的問題均為等式約束優(yōu)化問題，但等式約束并不足以描述人們面臨的問題，不等式約束比等式約束更為常見，大部分實(shí)際問題的約束都是不超過多少時(shí)間，不超過多少人力，不超過多少成本等等。所以有幾個(gè)科學(xué)家拓展了拉格朗日乘數(shù)法，增加了KKT條件之后便可以用拉格朗日乘數(shù)法來求解不等式約束的優(yōu)化問題了。

　　首先，我們先介紹一下什么是KKT條件。

　　KKT條件是指在滿足一些有規(guī)則的條件下, 一個(gè)非線性規(guī)劃(Nonlinear Programming)問題能有最優(yōu)化解法的一個(gè)必要和充分條件.?這是一個(gè)廣義化拉格朗日乘數(shù)的成果. 一般地, 一個(gè)最優(yōu)化數(shù)學(xué)模型的列標(biāo)準(zhǔn)形式參考開頭的式子, 所謂 Karush-Kuhn-Tucker 最優(yōu)化條件，就是指上式的最優(yōu)點(diǎn)x?必須滿足下面的條件:

　　1). 約束條件滿足gi(x?)≤0,i=1,2,…,p, 以及,hj(x?)=0,j=1,2,…,q

　　2). ?f(x?)+∑i=1μi?gi(x?)+∑j=1λj?hj(x?)=0, 其中?為梯度算子;

　　3). λj≠0且不等式約束條件滿足μi≥0,μigi(x?)=0,i=1,2,…,p。

　　KKT條件第一項(xiàng)是說最優(yōu)點(diǎn)x?必須滿足所有等式及不等式限制條件, 也就是說最優(yōu)點(diǎn)必須是一個(gè)可行解, 這一點(diǎn)自然是毋庸置疑的. 第二項(xiàng)表明在最優(yōu)點(diǎn)x?, ?f必須是?gi和?hj的線性組合, μi和λj都叫作拉格朗日乘子. 所不同的是不等式限制條件有方向性, 所以每一個(gè)μi都必須大于或等于零, 而等式限制條件沒有方向性，所以λj沒有符號(hào)的限制, 其符號(hào)要視等式限制條件的寫法而定.

　　為了更容易理解，我們先舉一個(gè)例子來說明一下KKT條件的由來。

　　let?L(x,μ)=f(x)+∑k=1μkgk(x)，其中μk≥0,gk(x)≤0

　　∵μk≥0 gk(x)≤0 ?=> ?μg(x)≤0

　　∴maxμL(x,μ)=f(x) ? ? ? ? ? ? ? ? ?(2)

　　∴minxf(x)=minxmaxμL(x,μ) ? ? (3)

　　maxμminxL(x,μ)=maxμ[minxf(x)+minxμg(x)]=maxμminxf(x)+maxμminxμg(x)=minxf(x)+maxμminxμg(x)

　　又∵μk≥0, gk(x)≤0

　　∴maxμminxμg(x)=0, 此時(shí)μ=0 or g(x)=0.

　　∴maxμminxL(x,μ)=minxf(x)+maxμminxμg(x)=minxf(x) ? ? ?(4)

　　此時(shí)μ=0?or?g(x)=0.

　　聯(lián)合(3),(4)我們得到minxmaxμL(x,μ)=maxμminxL(x,μ),?亦即

?　　

　　minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)

　　我們把maxμminxL(x,μ)稱為原問題minxmaxμL(x,μ)的對(duì)偶問題，上式表明當(dāng)滿足一定條件時(shí)原問題、對(duì)偶的解、以及minxf(x)是相同的，且在最優(yōu)解x?處μ=0 or g(x?)=0。把x?代入(2)得maxμL(x?,μ)=f(x?)，由(4)得maxμminxL(x,μ)=f(x?)，所以L(x?,μ)=minxL(x,μ)，這說明x?也是L(x,μ)的極值點(diǎn)，即

　　最后總結(jié)一下：

　　KKT條件是拉格朗日乘子法的泛化，如果我們把等式約束和不等式約束一并納入進(jìn)來則表現(xiàn)為：

　　注：x,λ,μ都是向量。

　　表明f(x)在極值點(diǎn)x?處的梯度是各個(gè)hi(x?)和gk(x?)梯度的線性組合。

-- End --

更多精彩：

? 神經(jīng)網(wǎng)絡(luò)基礎(chǔ)

? 線性代數(shù)有什么用？

? 趣文：追MM的各種算法

? 泰勒展開，傅里葉變換，拉普拉斯變換和Z變換的意義

? 協(xié)同過濾（CF）算法詳解和實(shí)現(xiàn)

? 你應(yīng)該掌握的七種回歸技術(shù)