拉格朗日乘子法如何理解?


謝邀。

拉格朗日乘數法(Lagrange multiplier)有很直觀的幾何意義。

舉個2維的例子來說明:

假設有自變數x和y,給定約束條件g(x,y)=c,要求f(x,y)在約束g下的極值。

我們可以畫出f的等高線圖,如下圖。此時,約束g=c由於只有一個自由度,因此也是圖中的一條曲線(紅色曲線所示)。顯然地,當約束曲線g=c與某一條等高線f=d1相切時,函數f取得極值。

兩曲線相切等價於兩曲線在切點處擁有共線的法向量。因此可得函數f(x,y)與g(x,y)在切點處的梯度(gradient)成正比。

於是我們便可以列出方程組求解切點的坐標(x,y),進而得到函數f的極值。


想法就是:

能夠碰到極大極小值點的必要條件是:

梯度場與切空間垂直,也就是梯度場不能夠有任何流形切空間上的分量,否則在切空間方向有分量,在流形上沿分量方向走,函數值會增加,沿反方向走,函數值會減少,不可能為局部極小或者極大值點。

一.

一個基本的例子:

假設你生活在三維歐氏空間中,z方向的坐標數值上代表海拔高度。

f(x,y,z)=z

如果你會飛,那麼anyway,你想飛多高飛多高,所以你的海拔可以任意高也可以任意小,根本就沒有最大值。

假定你是一個普通人類,你在一座山M上,你的目標是爬到山頂,也就是說你希望自己的海拔足夠高:

當你真正到達山腰時,很容易「只緣身在此山中,不識此山真面目」,這時候如何判斷是真的在往上爬呢,還是在往下走呢?

在肉眼所能看見的小範圍內,你可以通過周邊的局部地形來判斷,假設它大概是這樣:

你就知道應該往高處(大概為紅箭頭方向)走,而不是綠箭頭方向。

當然不一定一直沿這個方向直線式上升,可能還需要走到某個地方,再次做一下這種局部的考察,調整一下方向,保證自己能向高處走。

不過,什麼是「高」的一邊?這個概念究竟是如何形成的?

我們知道,海拔f(x,y,z)=z,我們希望能夠找到山面上的海拔最高點(山頂)。

梯度
abla f=(0,0,1)

關於梯度一個很自然的結論就是:

沿梯度方向是f增長最快的方向,反方向是下降最快的方向。

所以直觀上沿與梯度方向成銳角的方向移動,那麼f的值應該會增加。

而在山面上,我們可以通過天空來確定梯度方向(
abla f=(0,0,1)當然指向高高的天空啦)

與垂直向上方向成銳角的方向的地形,也就是「高」的一邊。

(可以見到,紅色的角是銳角,所以沿此方向海拔上升,綠色的角是鈍角,所以沿此方向海拔下降)

所有我們可以移動的方向,叫做這一點的切空間

那麼,什麼時候才能知道我們到達了山頂呢?

P點為山頂,那麼在這一點,切空間上任何一個方向與梯度方向(紅色箭頭)的夾角都不可以是銳角,

否則我們沿那個方向爬,就會上升到更高點。

所以切空間只能夠與梯度方向垂直。

利用流形本身的信息,我們可以得到切空間的方程,從而確定與切空間垂直的所有方向(這種方向叫做法向)。

利用函數本身的信息,我們可以得到梯度場的方向

梯度場方向與切空間垂直,所以梯度場可以表成一些的特定的法向 的線性組合,

係數記為lambda_1,hdots,lambda_k


abla f in (T_pM)^{ot },這就是Laplace乘子法的思想

二.一般形式

給一組約束條件F(x)=0,F=(F_1,hdots,F_k)

(經常加一些好的條件比如說F的jacobi矩陣滿秩,這些條件都是為了讓M確實是一個流形,見正則值定理)

那麼流形(約束條件下的所有點)為

M={ xin mathbb R^n |F(x)=0 }

p如果為f的局部極大值或者局部極小值,

那麼
abla f in (T_pM)^{ot }

M={ xin mathbb R^n |F(x)=0 },故法向量由
abla F_1 ,
abla F_2,hdots張成

所以存在一組係數lambda_1,hdots,lambda_k

使得


abla f =lambda_1 
abla F_1+hdots

這就是乘子方程。

所以本質上就是最開始說的:

能夠碰到極大極小值點的必要條件是:

梯度場與切空間垂直,也就是梯度場不能夠有任何流形切空間上的分量,否則在切空間方向有分量,在流形上沿分量方向走,函數值會增加,沿反方向走,函數值會減少,不可能為局部極小或者極大值點。

利用流形本身的信息,我們可以得到切空間的方程,從而確定法向。

利用函數本身的信息,我們可以得到梯度場的方向

梯度場方向與切空間垂直,所以梯度場可以表成一些的特定的法向(比如說一組基法向)的線性組合

用這兩個信息把上面那句話用方程的形式寫出來就好了

後記:

1.這種乘子法只考慮了第一變分(梯度),事實上極大極小值還可以用Hessian矩陣進行二階刻畫,所謂第二變分

2.這種找法只能夠找局部極值點,如果要尋找鞍點,就是這樣的點:

這種方法完全失效,不過一般情況下我們只關心極大極小值點。

對於鞍點的尋找,我們有Moutain Pass Lemma,或者更一般的,我們可以採用min-max原理的推理,能夠從極值點出發找到可能鞍點。

3.

我們只考慮假定流形M上比較好的函數,所有上述方法都可以內蘊地在流形上建立起來。

對於一般的關於臨界點即
abla f =0的點的理論,可以反饋流形自身的拓撲信息。

比如說著名的Reeb定理是在說:

考慮一個緊無邊光滑流形M,如果M上存在一個光滑函數,它只有最大值和最小值兩個極值點,並且這兩點的Hessian矩陣均可逆,那麼M就會拓撲同胚於單位球面

(微分同胚是不一定的,見Minlor的7維怪球)

所有臨界點均不退化(即Hessian矩陣非退化)的光滑函數f叫做Morse函數,對於Morse函數f,

我們有

  • sum_{}^{}{(-1)^{ind(p)}} =chi (M),M是一個光滑緊無邊流形,右邊是M的歐拉示性數,左邊跑遍f的所有臨界點,ind表示臨界點的指標。

  • c_i geq b_i,即f的指標為i的臨界點至少有b_i個,b_i是M的第i階De rham上同調群的維數。

作為一個應用,可以得到

環面上任何一個Morse函數,至少有四個臨界點。


這個可以比較直觀的解釋。

想像一下,目標函數f(x,y)是一座山的高度,約束g(x,y)=C是鑲嵌在山上的一條曲線如下圖。(渣畫技看看就好了)

你為了找到曲線上的最低點,就從最低的等高線(0那條)開始網上數。數到第三條,等高線終於和曲線有交點了(如上圖所示)。因為比這條等高線低的地方都不在約束範圍內,所以這肯定是這條約束曲線的最低點了。

而且約束曲線在這裡不可能和等高線相交,一定是相切。因為如果是相交的話,如下圖所示,那麼曲線一定會有一部分在B區域,但是B區域比等高線低,這是不可能的。

兩條曲線相切,意味著他們在這點的法線平行,也就是法向量只差一個任意的常數乘子(取為-lambda):
abla f(x,y)=-lambda 
abla g(x,y), 我們把這個式子的右邊移到左邊,並把常數移進微分運算元,就得到
abla (f(x,y)+lambda g(x,y))=0

把這個式子重新解釋一下,這個就是函數f(x,y)+lambda g(x,y)無約束情況下極值點的充分條件。


為什麼出現拉格朗日乘子法?

  • 最短路徑問題

  • 從幾何意義中獲得靈感:

  • 從數學公式中獲得靈感

  • 推廣到高維空間

------------------------------------------------------

一個最短路徑問題

假設你在M點,需要先到河邊(上圖右側曲線 )再回到C點,如何規劃路線最短?

假設:

河流曲線滿足方程 g(x,y) = 0 (例如 如果它是一個圓: g(x,y) = x2 + y2 - r2 = 0

用P表示河邊上的任意P(x,y)點,

用d(M,P)表示M,P之間距離,

那麼問題可以描述為:max , f(P) = d(M,P) + d(P, C) , 約束於 g(P) = 0.

如何求解問題?

1. 從幾何意義中獲得靈感:

首先,f(P)是一個標量(只有大小沒有方向),那麼在上圖的二維空間中必然存在了一個標量場f(P),即對於每一個點P都對應著一個f(P)值,它代表經過該點的路徑總和是多少。

如果我們畫出它的等值線(場線),就會發現它呈橢圓向外輻射:

顯然,f(P)的等值線與河邊曲線的交點P即為我們想求的點。

那麼問題來了: 這樣的點滿足何種性質? (如果沒有性質也就無法列出關係式進行求解,但是這麼特殊的點極有可能存在良好某種特性)

最直觀的性質: 等值線(橢圓)在P點的法向量n與河邊曲線的法向量m平行:

m{n} = lambda , m{m}

而在多元微積分中,一個函數h在某一點P的梯度是點P所在等值線(二維)或等值面(三維)的法向量,即m{n} = 
abla h( m{P} ),所以對於函數 f , g : (注意 梯度是一個向量,準備在另一個問題中對梯度的概念做詳細闡述)

m{n} = lambda , m{m}  
Rightarrow 
abla f( m{P} ) = lambda , 
abla g( m{P} ) 
Rightarrow 
egin{pmatrix}
  f_{x}\ 
  f_{y}
 end{pmatrix} 
= lambda
egin{pmatrix}
  g_{x}\ 
  g_{y}
 end{pmatrix} 
 Rightarrow 
f_{x} = lambda g_{x} ; (1)  \  f_{y} = lambda g_{y} ; (2)

即由相交點的性質我們得到了2個關係式(因為是二維平面,對於三維則可以得到三個關係式,以此類推),

再加上我們的約束條件:g(m P) = g(x,y) = 0 ; (3)

一共3個關係式,由線性代數中知識可知 3個關係式,3個未知量(x,y, lambda)極有可能有唯一解,當然也不排除會出現多個解甚至無窮多解 (例如 下圖 河邊是一條直線,且M,C就在河邊時)。(關於這個知識點稍後在其它答案中給出解釋)。

2. 從數學公式中獲得靈感

仍人是問題: max , f(P) = d(M,P) + d(P, C) \ subject , to , : ,  g(P) = 0.

我們知道在多元微積分中如果想求一個函數的極值一般的做法是把 
abla f( m P) = 0,如何把這個公式和我們的約束條件 
abla g( m P) = 0 統一在一起呢?

答案是: 引入 lambda 
並且定義一個新的函數: F( m P, lambda ) = f( m P) - lambda g( m P)

令:  
abla F( m P, lambda)  
=  
abla F(x,y, lambda)
= 
egin{pmatrix}
F_{x} \
F_{y} \
F_{lambda}
end{pmatrix}
= m 0 與我們要求解的優化問題是 等價的:

因為:F_{lambda} = g(m P) = g(x,y) =0 與約束條件等價,而且此時 F(m P, lambda ) = f( m P) - lambda 0 = f(m P) 即拉格朗日函數F(m P)與我們的目標函數f(m P) 取相同值。 用拉格朗日函數把目標函數和約束條件統一在了一起。

實際上這種方法與上面的幾何方法是完全等價的:

F_{x} = 0  Rightarrow
f_{x} - lambda g_{x}  = 0 Rightarrow f_{x} = lambda g_{x}  ; (1) \
F_{y} = 0  Rightarrow
f_{y} - lambda g_{y}  = 0 Rightarrow f_{y} = lambda g_{y}  ; (2)
\
g(x,y) = 0 ; (3)

3. 推廣到高維空間

以上我們一直在討論 二維的情形,下面讓我們看看這個問題的高維情況: 以幾何觀點為例:

假設約束條件變成 g(m P) =0 \
h(m P) = 0 ,其中 h是紫色橢球面, g是平面。它們相交於黑色的環,且在相交線上(黑色環)各自的方向向量(m n_{h} , m n_{g} ) 與相交線垂直。

對於我們的目標函數 f(m P) ,下圖中紅色橢球是它的等值面。它與黑色環的交點 m P
,此處的向量

 m n_{f} = lambda m n_{h} + mu m n_{g} Rightarrow 
abla f(m P) =  lambda 
abla h(m P) + mu 
abla g(m P)

更高維度同理。

參考:

- An Introduction to Lagrange Multipliers


拉格朗日乘子法是一種應用廣泛的約束問題最優化方法。對於其理解可以多個角度來解釋,比如說鞍點(saddle),代價解釋(cost),線性逼近(linear approximate)等等,下面就以等式約束為例,從線性逼近的角度來簡單的分析一下其原理,希望可以拋磚引玉。

對於無約束的問題我們可以通過線搜索方法(line search)或信賴域(turst region)方法來解決。而一個帶有等式約束問題,我們並不好優化,怎麼辦呢,我們要想辦法將其轉化成一個無約束的問題——拉格朗日函數。

我們知道拉格朗日乘子法在保留原函數的基礎上引入了一個線性項,那麼這個線性項有什麼作用呢?它保證了在獲得最優乘子的情況下,原目標函數的解和拉格朗日函數的解是一致的。具體是怎麼做的呢?我們假設當前點偏離了等式約束,並且我們已知偏離等式約束的這個點對應的原函數的值要比滿足等式約束值的原函數的最優值要小。那麼拉格朗日引入了這個線性項之後,兩者相加,大於那個最優值。那麼這樣實際上最優值還是在等式約束滿足的情況下得到。因此拉格朗日函數就起到了對偏離等式約束的懲罰作用,保證了原目標函數和拉格朗日函數解的一致性。

雖然說拉格朗日乘子法的線性項只是對原目標函數的一個線性逼近,也就是說兩者之間不是等價的,但是拉格朗日乘子法,能夠保證在取得最優乘子的情況下兩者解的一致性,那麼很顯然通過求解拉格朗日函數的最優解來求得原目標函數的最優解是一種更實際,更方便的做法。

以上是我的一些看法,希望可以幫到你,具體的樓主可以參考S.Boyd的 convex optimization.


由於連續可導函數取極值的時候,每個自變數的偏導數都為0(否則微調這個自變數就可以得到更大的值),因此拉格朗日函數取極值的時候,λ的偏導數也為0,而λ的偏導數恰好為引入的條件約束,而當條件約束等於0時,拉格朗日函數的值也恰好等於原函數的值,我們就可以很容易證明原函數在條件約束下取極值,與拉格朗日函數取極值是等價的。


看了各位前輩從幾何方面的理解。忽然豁然開朗,從代數方面講一下自己的心得。

求一個多元函數 f(x,y,z,...) 在條件 g(x,y,z,...)=a 下的極值,實際上是求前者在後者定義域下的極值。

而求函數 L(r,x,y,z,...)=f(x,y,z,...)+r*(g(x,y,z,...)-a) 的無條件極值,極值存在的條 件為L 的所有偏導數等於0。

關鍵的一點來了,由於 r 也是 L 的變數,所以 Lr 的偏導數為0相當於要求 g(x,y,z,...)-a=0

這恰好使 L(r,x,y,z,...) 的除 r 外的所有變數被限制在 g(x,y,z,...) 的定義域內。

而在這個定義域內,顯然 g-a 恆等於0,於是有 L=f ,求 f 的有條件極值問題被轉化為求 L 的無條件極值問題。


拉格朗日乘子法用一個例子說明可能會更容易懂一些。這裡推薦一下王琥老師的ppt:

汽車優化設計 第二章:優化方法的數學基礎 王琥 湖南大學 機械與運載工程學院

以下內容摘自王老師的ppt。

先大體描述一下拉格朗日乘子法:

問題:對於函數 f(x1,x2,…,xn),以及限制條件:s.t. hk(x1,x2,…,xn)=0 其中(k=1,2,…,l),求函數f的極值。

解法:重新定義一個函數:

待定係數λk稱為拉格朗日乘子。

在極值點處,有

從而可以通過解線性方程組的方式求解。

舉個栗子:

限制條件為:

求函數

的極值點坐標。

改造後的函數為:

求偏導以後可以得到如下:

很容易得出x1和x2的值。

變數多於2個的情形也是類似的解法。


這樣看也許簡單一些

g大小寫沒注意,不要在意這些細節啦~


前面答案已經講很多了。補充一下針對多個等式約束下,對問題的直觀理解。

簡單講,拉格朗日乘子法就是,把目標函數和等式約束統一到一個拉格朗日函數中。

原因是,局部最優的必要條件是,目標函數的梯度等於所有約束函數的梯度的線性組合。

只有一個約束條件時,很好理解。如圖,利用反證法,如果目標函數梯度和約束函數梯度方向不同,則沿約束條件運動,能繼續優化目標函數。

如果有多個約束條件,這些約束函數肯定是相交的,否則無解。如果約束函數相交到一個點,那麼就只有一個解。

一般情況下,多個約束函數會把變數約束到一個低維子空間里,借用下已有回答的圖例,兩個三維曲面(黃紫)相交得到一個二維曲線。這個二維曲線在某點的法空間(cotangent space),由各約束函數在該點的法向量張成,所以,只要目標函數(紅)的梯度處於該法空間即可。


大家解釋了一下拉格朗日乘子法,那我來說一下拉格朗日乘子的意義吧

實際上拉格朗日乘子lambda就是邊際成本,數學一點解釋就是sensitivity to a small change of the corresponding constraints。可以類比一下線性和非線性,在線性優化中,考慮約束mathbf{Ax}=mathbf{b},此時的最優解是mathbf{x}=mathbf{B}^{-1}mathbf{b},如果有一個約束變為了b_i+delta,假設delta很小使得mathbf{B}^{-1}(mathbf{b}+delta mathbf{e}_i)仍然可取,則它是新的最優解,最優值產生了deltamathbf{c^T}mathbf B^{-1}mathbf{e_i}的變化,在這裡frac{deltamathbf{c^T}mathbf B^{-1}mathbf{e_i}}{delta}=mathbf{c^T}mathbf B^{-1}mathbf{e_i}可以理解成b_i的邊際成本,而對應的在非線性中,假設一個約束從g(mathbf x_i)=0變成了g(mathbf x_i)+mathbf d_i=0,令hat{g_i}(mathbf x;mathbf d)=g_i(mathbf x)+d_i,最優值變為f(mathbf{x^*(d)}),實際上可證得frac{partial f(mathbf x^*(mathbf d))}{partial d_i}=lambda^*_i(mathbf d)lambda^*_i(mathbf 0)=lambda^*_i,即由於約束變化導致目標函數值變化的速率。


如圖,空間內有函數 z=phi(x,y) (紅)和 z=f(x,y) (藍),我們的目的是求在 z=phi (x,y)=0 時, f 如何取得極值。


這裡需要引入隱函數存在定理

如圖所示, F(x_0,y_0)=0

而我們知道, M_0(x_0,y_0,f(x_0,y_0)) 點的偏導數 f_x(x_0,y_0) ,就是這曲線在點 M_0 處對 x 軸的斜率。同樣,偏導數 f_y(x_0,y_0) 的幾何意義是曲面被平面 x=x_0 所截得的曲線在點 M_0 處的切線 M_0T_yy 軸的斜率。

於是,上式的 f_x(x_0,y_0) 就是黑色向量

上式中的 f_y(x_0,y_0) 則是

設在該處有 dxdy

frac{dy}{dx}=-frac{frac{dz}{f_y}}{frac{dz}{f_x}}=-frac{f_x}{f_y}


回到原圖上來,

既然我們已經知道偏導數就是切線斜率,也就是說,凡是 z=phi(x,y) 上的 z=0 這條線上,都可以找到相應的偏導數,且 frac{dy}{dx}=-frac{phi_x}{phi_y}

那麼從 phi(x,y)=0 的地方上溯到 f(x,y) 上面去,同樣的位置上, f 肯定也具有偏導數,而且 f 在這個點的 xy 之間滿足 frac{dy}{dx}=-frac{phi_x}{phi_y}

而我們知道, f 取極值時, f_xdx+f_ydy=0

於是 frac{f_x}{f_y}=frac{phi_x}{phi_y}


拉格朗日乘子法的由來:http://blog.csdn.net/fourierfeng/article/details/77929297


更新:這個答案是錯誤的,錯誤原因在最後,原答案我就不編輯掉了。關於錯誤的答案,可能思路上還是有一定參考價值的

或者你也可以這樣理解,把lambda先當作一個常數,以二維為例,當滿足約束條件g(x,y)=c時,無論lambda取多少,f(x,y)與F(x,y) = f(x,y)+lambda*(g(x,y)-c)都顯然有著相同的最值(注意這裡將lambda當作常數,所以不寫成F(x,y,lambda)),所以你需要找到一個可以幫助里輕鬆計算出來這個極值的lambda,即當滿足約束條件的g(x,y)=c的同時還能使得F(x,y)的梯度為(0,0),找到了這個lambda,你就可以很直接的算出F(x,y)的最值,也即f(x,y)的最值

或者你直接從三元函數(仍然以二維為例)F(x,y,lambda)的角度理解也一樣,如果該函數為凸函數(正常情況下肯定是凸優化問題)的話則其梯度為(0,0,0)處是最小值點,且在該點處g(x,y)-c=0,也即意味著在g(x,y)-c=0時,f(x,y)的最小值就是在該點的x,y處取得(假如在g(x,y)-c=0時,f(x,y)有更小的值就說明F(x,y,lambda)梯度為0時不是最小值點,矛盾)

如果你想問的是直觀上的理解的話我想這樣解釋是比較合適的,不需要你知道凸優化的內容,甚至不需要你學過數學分析或者微積分,拋開那些定理和結論,只從中學時期就接觸到的導數理解(可以推廣到梯度)

更正:

時隔半年回來看到自己之前寫的答案,發現其中一部分是錯誤的,關於二元函數部分的解釋沒有問題,但是關於三元函數部分的解釋是錯誤的,實際上該三元函數是非凸的(不過回想起來多年前看過的微積分教材上似乎是直接從三元函數求梯度得到的,所以關於這一點我還是有些疑惑的,其實關鍵在於能否證明使得F(x,y,lambda)梯度為0的lambda帶回去得到的二元函數為凸函數,或者取負後為凸函數)

再更正:

原回答中關於二元函數角度的解釋也有問題,我所說的找到一個lambda使得二元凸函數梯度為0時滿足約束條件,這個要求太嚴格了,是充分不必要的,事實上我們並不要求將lambda帶進去之後的函數為凸函數

綜上,其實我覺得最直觀的一種理解方式還是從相切出發最好


線性逼近,可以看看凸優化


對於受約束的動力學系統,拉格朗日乘子的大小就是相應的約束反力的值。


如果遇到的是形如這種簡單函數 z = x^2 + y^2 並且約束條件x+y=1的情形,我們直接把y = 1 - x 代入函數z,即可求得最值,這種情況下我們看不出拉格朗日乘子法的厲害。

但是若約束條件是一個複雜的函數約束,無法使用x表示出y。例如如下約束

x^3 + x * y^2 + y = 1 (此例未經驗證,寫在這裡只是為了表述這個事情)

此時常規方法解不出來,拉格朗日乘子法就可以發揮作用了。


引自,最優化與建模,清華大學出版社

約束函數gj(X)&>=0,目標函數f(X),X是n維向量。

條件一:gj(X)的導都大於0,因為gj(X)大於0。這裡有問題我覺得,但是書里這麼寫的。

約束函數有兩種情況,1是=0,那麼此時它與f(X)相交。如果x0是極小值,遵守條件一,所以f(X)的導應和所有gj(X)的導都是銳角。所以f(X)的導應減去rj*gj(X)的導=0,rj是大等於0。rj等於0說明第j個約束函數不和目標函數相交,ri&>0說明第i個約束函數gi(X)和f(X)相交於點X。於是就得到那個公式了。

f"(X)-累加符號rj*gj"(X)=0。

懂了么?


手機黨畫不了圖,想像一下,你有一個二維的函數,和一條約束曲線,在曲線上隨便選幾個點記錄下來二維函數f在這些點的梯度方向,(主要是看看有沒有梯度分量在曲線切線方向上)。然後想像拿著條約束曲線兩頭拉直它,這時候就變成一維的函數了,這時候極值點就是當初記錄下來梯度方向跟曲線方向垂直的點。因為在這點上沒有梯度分量,也即導數為零。

所以在二維上看也即是約束曲線跟等高線的交點處,這時候曲線上梯度分量為零。


推薦閱讀:

怎樣看待摩拜推出摩拜紅包車?
參加2016年美賽是一種怎樣的體驗?
ATM交易狀態的特徵參數有哪些?
在數學中一個非凸的最優化問題是什麼意思?
如果存在四維空間,在其中看物體會不會不真實?

TAG:數學 | 數學建模 |