Lagrange 乘數法

Posted on 05/30/2012 by

本文的閱讀等級：中級

約束最佳化 (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 的函數。此外，當變數的數量增多或有多個束縛條件時，縱使能夠得到代數解，無約束目標函數的表達式也可能相當複雜。與上述作法比較，Lagrange 乘數法 (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}。多變量泰勒展開可表示成向量矩陣運算形式：

\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} 2x_1+\lambda&=0\\ 2x_2+\lambda&=0\\ 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 乘數法

  1. 張盛東 說道：
    09/05/2013 at 10:49 上午

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

    回應
  2. Ethan 說道：
    06/04/2015 at 11:38 上午

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

    回應
    • ccjou 說道：
      06/04/2015 at 1:02 下午

      上文提到：在滿足限制的情況下，駐點發生於 \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。

      回應

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入：

Gravatar
WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 ( 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 ( 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 ( 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 ( 登出 / 變更 )

取消

連結到 %s