Lagrange 乘數法

本文的閱讀等級：中級

約束最佳化 (constrained optimization) 是指在一個或多個束縛條件下，尋找一個多變數函數的極值 (極大值或極小值)。舉例來說，我們希望得到 $f(x_1,x_2)$ 的極小值，但前提是 $x_1$ 與 $x_2$ 必須滿足束縛條件 $g(x_1,x_2)=0$ 。最直截了當的作法是解出束縛條件，如此 $x_2$ 可表示為 $x_1$ 的函數，譬如 $x_2=h(x_1)$ 。將上式代入 $f(x_1,x_2)$ 可得單變數函數 $f(x_1,h(x_1))$ ，求導並設為零即得極值的必要條件 $\frac{df}{dx_1}=0$ 。這個方法的主要缺點在於束縛條件未必存在代數解，也就是說 $x_2$ 無法寫成 $x_1$ 的函數。此外，當變數的數量增多或有多個束縛條件時，縱使能夠得到代數解，無約束目標函數的表達式也可能相當複雜。與上述作法比較，拉格朗日乘數法 (method of Lagrange multipliers) 或稱未定乘數法 (undetermined multipliers) 不須解出束縛條件，因而保留了變數之間的對稱性。由於兼具簡單與典雅兩個優點，Lagrange 乘數法是目前最常被使用的一種求解約束最佳化方法：令 Lagrangian 函數為

$L(x_1,x_2,\lambda)=f(x_1,x_2)+\lambda g(x_1,x_2)$ ，

其中 $\lambda$ 稱為 Lagrange 乘數。計算 $L$ 對所有變數的偏導數並設為零：

$\displaystyle \frac{\partial L}{\partial x_1}=0,~\frac{\partial L}{\partial x_2}=0,~\frac{\partial L}{\partial\lambda}=0$ ，

這個方程組即為最佳解的必要條件。本文採用較富直覺的幾何觀點解說 Lagrange 乘數法的基本原理，預備知識包括正交補餘和正交投影 (見“正交補餘與投影定理”)。

Joseph-Louis Lagrange (1736-1813) From http://www-history.mcs.st-and.ac.uk/BigPictures/Lagrange.jpeg

令目標函數 $f(x_1,\ldots,x_n)$ 為定義於 $\mathbb{R}^n$ 的連續可導實函數，收集所有變數組成一個 $n$ 維實向量 $\mathbf{x}=(x_1,\ldots,x_n)^T$ 。欲解析函數 $f$ 在點 $\mathbf{x}$ 附近的變化，設 $\boldsymbol{\epsilon}=(\epsilon_1,\ldots,\epsilon_n)^T$ 為一個微小向量，寫出 $f(\mathbf{x}+\boldsymbol{\epsilon})$ 於點 $\mathbf{x}$ 的泰勒展開式 (見“答張盛東──關於 Hessian 矩陣與多變量函數的泰勒展開式”)：

$f(\mathbf{x}+\boldsymbol{\epsilon})=f(\mathbf{x})+\displaystyle\sum_{i=1}^n\frac{\partial f}{\partial x_i}(\mathbf{x})\,\epsilon_i+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2f}{\partial x_i\partial x_j}(\mathbf{x})\,\epsilon_i\epsilon_j+\cdots$ 。

將偏導數 $\frac{\partial f}{\partial x_1},\ldots,\frac{\partial f}{\partial x_n}$ 組成一個 $n$ 維向量，稱為梯度 (gradient)，記作

$\displaystyle \nabla f=\frac{\partial f}{\partial\mathbf{x}}=\begin{bmatrix} \displaystyle\frac{\partial f}{\partial x_1}\\[0.5em] \vdots\\[0.5em] \displaystyle\frac{\partial f}{\partial x_n} \end{bmatrix}$ 。

令 $H=[h_{ij}]$ 為 $n\times n$ 階矩陣，稱作 Hessian，其中各元為 $h_{ij}=\frac{\partial^2f}{\partial x_i\partial x_j}$ 。明顯地， $H$ 是一個實對稱矩陣。多變量泰勒展開可表示成向量矩陣運算形式：

$\displaystyle f(\mathbf{x}+\boldsymbol{\epsilon})=f(\mathbf{x})+\nabla f(\mathbf{x})^T\boldsymbol{\epsilon}+\frac{1}{2}\boldsymbol{\epsilon}^TH(\mathbf{x})\boldsymbol{\epsilon}+O(\Vert\boldsymbol{\epsilon}\Vert^3)$ ，

其中 $O(\Vert\boldsymbol{\epsilon}\Vert^3)$ 代表誤差。因為 $\boldsymbol{\epsilon}$ 是微小向量，我們可以忽略二次以上所有項，就有 $f(\mathbf{x}+\boldsymbol{\epsilon})\approx f(\mathbf{x})+\nabla f(\mathbf{x})^T\boldsymbol{\epsilon}$ 。在固定 $\Vert\boldsymbol{\epsilon}\Vert$ 的情況下，若 $\boldsymbol{\epsilon}=k\nabla f(\mathbf{x})$ 且 $k>0$ ，則內積 $\nabla f(\mathbf{x})^T\boldsymbol{\epsilon}$ 具有最大值。換句話說，梯度 $\nabla f(\mathbf{x})$ 指出目標函數 $f$ 在點 $\mathbf{x}$ 的最陡上升方向。如果 $\nabla f(\mathbf{x}^\star)=\mathbf{0}$ ，我們稱 $\mathbf{x}^\star$ 是一個駐點 (stationary point)。明顯地，駐點即為 $f$ 的極值 (極大值或極小值) 存在的必要條件。若 $H(\mathbf{x}^\star)$ 是正定的，則 $\mathbf{x}^\star$ 為一個局部極小值；若 $H(\mathbf{x}^\star)$ 是負定的，則 $\mathbf{x}^\star$ 為一個局部極大值；若 $H(\mathbf{x}^\star)$ 是未定的，則 $\mathbf{x}^\star$ 為一個鞍點 (見“最佳化理論與正定矩陣”)。

接下來我們討論單一束縛條件的情況。考慮這個問題

$\displaystyle \begin{array}{ll} \hbox{minimize}&f(\mathbf{x})\\ \hbox{subject to}&g(\mathbf{x})=0, \end{array}$

其中 $\mathbf{x}\in\mathbb{R}^n$ 。束縛條件 $g(\mathbf{x})=0$ 描述在 $\mathbb{R}^n$ 的一個超曲面 (hypersurface)。假設 $g(\mathbf{x})$ 是連續可導函數，想像我們位於超曲面上一點 $\mathbf{x}$ ，考慮 $g(\mathbf{x}+\boldsymbol{\epsilon})$ 的泰勒展開式：

$\displaystyle g(\mathbf{x}+\boldsymbol{\epsilon})=g(\mathbf{x})+\nabla g(\mathbf{x})^T\boldsymbol{\epsilon}+O(\Vert\boldsymbol{\epsilon}\Vert^2)$ 。

如果 $\mathbf{x}+\boldsymbol{\epsilon}$ 也在超曲面上，即 $g(\mathbf{x}+\boldsymbol{\epsilon})=g(\mathbf{x})=0$ ，忽略微小誤差可得 $\nabla g(\mathbf{x})^T\boldsymbol{\epsilon}=0$ 。見下圖 (以 $\mathbb{R}^3$ 為例)， $\boldsymbol{\epsilon}$ 位於點 $\mathbf{x}$ 的切平面 (因為切平面是點 $\mathbf{x}$ 鄰近的活動區域)， $\nabla g(\mathbf{x})^T\boldsymbol{\epsilon}=0$ 表示 $\nabla g(\mathbf{x})$ 是超曲面 $g(\mathbf{x})=0$ 於點 $\mathbf{x}$ 的法向量，因此穿越點 $\mathbf{x}$ 的切平面即為法向量 $\nabla g(\mathbf{x})$ 的正交補餘 (orthogonal complement)，記為 $\mathrm{span}\{\nabla g(\mathbf{x})\}^{\perp}$ 。為了在超曲面上尋找極值，計算梯度 $\nabla f$ 於切平面 $\mathrm{span}\{\nabla g\}^{\perp}$ 的正交投影，記為 $\nabla\hat{f}$ ，也就是 $\nabla f$ 扣除至法向量所在的直線 (子空間) $\mathrm{span}\{\nabla g\}$ 的正交投影 (見“正交投影──威力強大的線代工具”)：

$\displaystyle \nabla\hat{f}=\nabla f-\left(\frac{\nabla f^T\nabla g}{\Vert\nabla g\Vert^2}\right)\nabla g$ 。

在滿足束縛條件的情況下， $f$ 的局部極小值發生於 $\nabla\hat{f}=\mathbf{0}$ ，或者說 $\nabla f\in \mathrm{span}\{\nabla g\}$ ，故存在一個純量 $\lambda$ 使得 $\nabla f=-\lambda \nabla g$ (正負號可任意選定)。為了方便，我們定義 Lagrangian 函數

$L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda g(\mathbf{x})$ ，

局部極小值的必要條件如下：

$\displaystyle\begin{aligned} \nabla_{\mathbf{x}}L&=\frac{\partial L}{\partial \mathbf{x}}=\nabla f+\lambda\nabla g=\mathbf{0},\\ \nabla_{\lambda}L&=\frac{\partial L}{\partial\lambda}=g(\mathbf{x})=0,\end{aligned}$

其中第一式為定常方程 (stationary equation)，第二式為束縛條件。解開上面 $n+1$ 個方程式可得到 Lagrangian 函數 $L(\mathbf{x},\lambda)$ 的駐點 $\mathbf{x}^\star$ 以及 $\lambda$ 的值。若 $\lambda=0$ ，則 $\nabla{f}(\mathbf{x}^\star)=\mathbf{0}$ ，這時候目標函數 $f$ 的駐點 $\mathbf{x}^\star$ 同時滿足束縛條件 $g(\mathbf{x}^\star)=0$ 。

Tangent plane and gradient

舉一個例子，考慮

$\displaystyle \begin{array}{ll} \hbox{minimize}&x_1^2+x_2^2\\ \hbox{subject to}&x_1+x_2=1, \end{array}$

其中 $(x_1,x_2)\in\mathbb{R}^2$ 。寫出 Lagrangian 函數

$\displaystyle L(x_1,x_2,\lambda)=x_1^2+x_2^2+\lambda(x_1+x_2-1)$ ，

其中 $\lambda$ 為 Lagrange 乘數。求導 $\frac{\partial L}{\partial x_1}, \frac{\partial L}{\partial x_2}, \frac{\partial L}{\partial \lambda}$ 並設為零，可得下列方程組：

$\displaystyle \begin{aligned} \frac{\partial L}{\partial x_1}&=2x_1+\lambda=0\\ \frac{\partial L}{\partial x_2}&=2x_2+\lambda=0\\ \frac{\partial L}{\partial \lambda}&=x_1+x_2-1=0. \end{aligned}$

解開得到一個駐點 $(x_1^\star,x_2^\star)=(\frac{1}{2},\frac{1}{2})$ ，此即為極小值，對應的 Lagrange 乘數是 $\lambda=-1$ 。

Lagrange 乘數法可推廣至包含多個束縛條件的約束最佳化問題：

$\displaystyle \begin{array}{lll} \hbox{minimize}&f(\mathbf{x})&\\ \hbox{subject to}&g_k(\mathbf{x})=0,&k=1,\ldots,m. \end{array}$

給定 $g_k(\mathbf{x})=0$ ， $k=1,\ldots,m$ ， $m<n$ ，駐點存在的條件為 $\nabla f\in \mathrm{span}\{\nabla g_1,\ldots,\nabla g_m\}$ 。若 $\{\nabla g_1,\ldots,\nabla g_m\}$ 構成一個線性獨立集，就有唯一組合係數 $\lambda_1,\ldots,\lambda_m$ 使得 $\nabla f=-\sum_{k=1}^m\lambda_k\nabla g_k$ 。定義 Lagrangian 函數

$\displaystyle L\left(\mathbf{x},\{\lambda_k\}\right)=f(\mathbf{x})+\sum_{k=1}^m\lambda_kg_k(\mathbf{x})$ ，

極值的必要條件如下：

$\displaystyle\begin{aligned} \nabla_{\mathbf{x}}L&=\nabla f+\sum_{k=1}^m\lambda_k\nabla g_k=\mathbf{0},\\ \nabla_{\lambda_k}L&=g_k(\mathbf{x})=0,~~~k=1,\ldots,m.\end{aligned}$

Lagrange 乘數法的應用：

7 Responses to Lagrange 乘數法

張盛東 says:

09/05/2013 at 10:49 am

老師，其實能否將Hessian矩陣看作gradient算子與自身的外積再乘以函數f？如果可以，是否可能將多變數函數的Taylor展開式前兩項之後的項都像這樣表示成gradient算子與自身的外積？

- ccjou says:
  
  09/05/2013 at 1:04 pm
  
  你說的外積可是指outer product？
  
  - 張盛東 says:
    
    09/05/2013 at 1:06 pm
    
    是的。
    
    - ccjou says:
      
      09/05/2013 at 1:20 pm
      
      我再另外發文解釋多變數函數的Taylor series裡面的gradient和Hessian是如何產生的(推導出來)，這樣應該就能回答你的問題。
      
Ethan says:

06/04/2015 at 11:38 am

教授您好，我是正在學大一微積分的同學，所以沒有看很懂這篇文章…不過還是想問個問題！我想知道拉格朗日乘數是否有不為零的限制？總覺得似乎是沒有的，是嗎？剛已有在 stackexchange 查過這問題（http://math.stackexchange.com/questions/41534/is-it-possible-for-the-lagrange-multiplier-to-be-equal-to-zero），但看得滿吃力的Orz…還沒有很清楚，希望教授能幫忙指點迷津，謝謝！

- ccjou says:
  
  06/04/2015 at 1:02 pm
  
  上文提到：在滿足限制的情況下，駐點發生於 $\nabla\hat{f}=\mathbf{0}$ ，此時 $\nabla f$ 屬於 $\mathrm{span}\{\nabla g\}$ ，故存在一純量 $\lambda$ 使得 $\nabla f=-\lambda \nabla g$ (正負號可任意選定)。
  
  若 $\lambda=0$ ，則 $\nabla{f}=\mathbf{0}$ ，意思是駐點的位置 $\mathbf{x}$ 恰好滿足限制式 $g(\mathbf{x})=0$ 。例如， $f(x,y)=x^2+y^2$ 在 $(x,y)=(0,0)$ 有極小值。倘若加入限制式 $g(x,y)=x^2-y=0$ ，則 Lagrangian 函數為
  $L(x,y,\lambda)=x^2+y^2+\lambda(x^2-y)$ 。
  計算偏導數並設為0，
  $\displaystyle\frac{\partial L}{\partial x}=2x+2\lambda x=0$
  $\displaystyle\frac{\partial L}{\partial y}=2y-\lambda=0$ ，
  也就有
  $(1+\lambda)x=0$ ， $\lambda=2y$ ， $y=x^2$ 。將後面兩式代入第一式，
  $(1+2x^2)x=0$ ，取實數解 $x=0$ ，故 $y=0$ ， $\lambda=0$ 。
  
  - Ethan says:
    
    06/04/2015 at 1:18 pm
    
    哇！非常感謝教授這麼快就回覆了！謝謝教授，我會再研究看看，有問題再進一步發問^^

	Mathematics in Machi… on Karush-Kuhn-Tucker (KKT) 條件
	Mathematics in Machi… on 矩陣導數
	文东柳 on 兩岸線性代數用詞參照
	Jr Fang Liou on 費布納西數列的表達式
	劉信傑 on 零空間的快捷算法
	Heqet on 線性代數的原罪？