前沿拓展：

乘數(shù)

豎式計(jì)算49×82式，先用第二個(gè)乘數(shù)個(gè)位上的2數(shù)乘第一個(gè)乘數(shù)，得到98

再用第二個(gè)乘數(shù)十位上的8乘第一個(gè)乘數(shù)，得到3920

最后把兩個(gè)積加起來得到乘式的積：98+3920=4018

閱讀目錄

1. 拉格朗日乘數(shù)法的基本思想

2. 數(shù)學(xué)實(shí)例

3. 拉格朗日乘數(shù)法的基本形態(tài)

4. 拉格朗日乘數(shù)法與KKT條件

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

1. 拉格朗日乘數(shù)法的基本思想

作為一種優(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

2. 數(shù)學(xué)實(shí)例

首先，我們先以麻省理工學(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)行了簡(jiǎn)化，去掉了平方）

s.t. xy=3.

根據(jù)上式我們可以知道這是一個(gè)典型的約束優(yōu)化問題，其實(shí)我們?cè)诮膺@個(gè)問題時(shí)最簡(jiǎn)單的解法就是通過約束條件將其中的一個(gè)變量用另外一個(gè)變量進(jìn)行替換，然后代入優(yōu)化的函數(shù)就可以求出極值。我們?cè)谶@里為了引出拉格朗日乘數(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)化問題，如下所示：

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

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è)簡(jiǎn)單的例子就是為了體會(huì)拉格朗日乘數(shù)法的思想，即通過引入拉格朗日乘子(λ)將原來的約束優(yōu)化問題轉(zhuǎn)化為無約束的方程組問題。

3. 拉格朗日乘數(shù)法的基本形態(tài)

函數(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)接長(zhǎng)方體的最大體積。這個(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è)等式的微分，得到

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

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

4. 拉格朗日乘數(shù)法與KKT條件

我們上述討論的問題均為等式約束優(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?必須滿足下面的條件:

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

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

λ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?)梯度的線性組合。

拓展知識(shí)：