本文的閱讀等級:中級
約束最佳化 (constrained optimization) 是指在一個或多個束縛條件下,尋找一個多變數函數的極值 (極大值或極小值)。舉例來說,我們希望得到 的極小值,但前提是
與
必須滿足束縛條件
。最直截了當的作法是解出束縛條件,如此
可表示為
的函數,譬如
。將上式代入
可得單變數無約束目標函數
,求導並設為零即得極值的必要條件
。這個方法的主要缺點在於束縛條件未必存在代數解,也就是說
無法寫成
的函數。此外,當變數的數量增多或有多個束縛條件時,縱使能夠得到代數解,無約束目標函數的表達式也可能相當複雜。與上述作法比較,拉格朗日乘數法 (method of Lagrange multipliers) 或稱未定乘數法 (undetermined multipliers) 不須解出束縛條件,因而保留了變數之間的對稱性。由於兼具簡單與典雅兩個優點,Lagrange 乘數法是目前最常被使用的一種求解約束最佳化方法:令 Lagrangian 函數為
,
其中 稱為 Lagrange 乘數。計算
對所有變數的偏導數並設為零:
,
這個方程組即為最佳解的必要條件。本文採用較富直覺的幾何觀點解說 Lagrange 乘數法的基本原理,預備知識包括正交補餘和正交投影 (見“正交補餘與投影定理”)。

Joseph-Louis Lagrange (1736-1813) From http://www-history.mcs.st-and.ac.uk/BigPictures/Lagrange.jpeg
令目標函數 為定義於
的連續可導實函數,收集所有變數組成一個
維實向量
。欲解析函數
在點
附近的變化,設
為一個微小向量,寫出
於點
的泰勒展開式 (見“答張盛東──關於 Hessian 矩陣與多變量函數的泰勒展開式”):
。
將偏導數 組成一個
維向量,稱為梯度 (gradient),記作
。
令 為
階矩陣,稱作 Hessian,其中各元為
。明顯地,
是一個實對稱矩陣。多變量泰勒展開可表示成向量矩陣運算形式:
,
其中 代表誤差。因為
是微小向量,我們可以忽略二次以上所有項,就有
。在固定
的情況下,若
且
,則內積
具有最大值。換句話說,梯度
指出目標函數
在點
的最陡上升方向。如果
,我們稱
是一個駐點 (stationary point)。明顯地,駐點即為
的極值 (極大值或極小值) 存在的必要條件。若
是正定的,則
為一個局部極小值;若
是負定的,則
為一個局部極大值;若
是未定的,則
為一個鞍點 (見“最佳化理論與正定矩陣”)。
接下來我們討論單一束縛條件的情況。考慮這個問題
其中 。束縛條件
描述在
的一個超曲面 (hypersurface)。假設
是連續可導函數,想像我們位於超曲面上一點
,考慮
的泰勒展開式:
。
如果 也在超曲面上,即
,忽略微小誤差可得
。見下圖 (以
為例),
位於點
的切平面 (因為切平面是點
鄰近的活動區域),
表示
是超曲面
於點
的法向量,因此穿越點
的切平面即為法向量
的正交補餘 (orthogonal complement),記為
。為了在超曲面上尋找極值,計算梯度
於切平面
的正交投影,記為
,也就是
扣除至法向量所在的直線 (子空間)
的正交投影 (見“正交投影──威力強大的線代工具”):
。
在滿足束縛條件的情況下, 的局部極小值發生於
,或者說
,故存在一個純量
使得
(正負號可任意選定)。為了方便,我們定義 Lagrangian 函數
,
局部極小值的必要條件如下:
其中第一式為定常方程 (stationary equation),第二式為束縛條件。解開上面 個方程式可得到 Lagrangian 函數
的駐點
以及
的值。若
,則
,這時候目標函數
的駐點
同時滿足束縛條件
。
舉一個例子,考慮
其中 。寫出 Lagrangian 函數
,
其中 為 Lagrange 乘數。求導
並設為零,可得下列方程組:
解開得到一個駐點 ,此即為極小值,對應的 Lagrange 乘數是
。
Lagrange 乘數法可推廣至包含多個束縛條件的約束最佳化問題:
給定 ,
,
,駐點存在的條件為
。若
構成一個線性獨立集,就有唯一組合係數
使得
。定義 Lagrangian 函數
,
極值的必要條件如下:
Lagrange 乘數法的應用:
老師,其實能否將Hessian矩陣看作gradient算子與自身的外積再乘以函數f?如果可以,是否可能將多變數函數的Taylor展開式前兩項之後的項都像這樣表示成gradient算子與自身的外積?
你說的外積可是指outer product?
是的。
我再另外發文解釋多變數函數的Taylor series裡面的gradient和Hessian是如何產生的(推導出來),這樣應該就能回答你的問題。
教授您好,我是正在學大一微積分的同學,所以沒有看很懂這篇文章…不過還是想問個問題!我想知道拉格朗日乘數是否有不為零的限制?總覺得似乎是沒有的,是嗎?剛已有在 stackexchange 查過這問題(http://math.stackexchange.com/questions/41534/is-it-possible-for-the-lagrange-multiplier-to-be-equal-to-zero),但看得滿吃力的Orz…還沒有很清楚,希望教授能幫忙指點迷津,謝謝!
上文提到:在滿足限制的情況下,駐點發生於
,此時
屬於
,故存在一純量
使得
(正負號可任意選定)。
若
,則
,意思是駐點的位置
恰好滿足限制式
。例如,
在
有極小值。倘若加入限制式
,則 Lagrangian 函數為
。

,
,
,
。將後面兩式代入第一式,
,取實數解
,故
,
。
計算偏導數並設為0,
也就有
哇!非常感謝教授這麼快就回覆了!謝謝教授,我會再研究看看,有問題再進一步發問^^
用 \nabla f=-\lambda \nabla g 就可以算出答案,為什麼還要多寫Lagrangian 函數?
老師我想請問 為何“ 在滿足束縛條件的情況下,f 的局部極小值發生於 \nabla\hat{f}=\mathbf{0}“?