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 乘數法的應用：

8 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
    
    哇！非常感謝教授這麼快就回覆了！謝謝教授，我會再研究看看，有問題再進一步發問^^
    
小鎮馬 says:

07/03/2019 at 11:59 pm

用 \nabla f=-\lambda \nabla g 就可以算出答案，為什麼還要多寫Lagrangian 函數？

	ctimmy on 每週問題 January 25, 2016
	cellcetion on 每週問題 January 25, 2016
	ctimmy on 每週問題 January 25, 2016
	cellcetion on 每週問題 January 25, 2016
	Chen on 矩陣運算的基本技巧
	ctimmy on 矩陣運算的基本技巧