Lagrange 乘數法

本文的閱讀等級:中級

約束最佳化 (constrained optimization) 是指在一個或多個束縛條件下,尋找一個多變數函數的極值 (極大值或極小值)。舉例來說,我們希望得到 f(x_1,x_2) 的極小值,但前提是 x_1x_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 乘數法的基本原理,預備知識包括正交補餘和正交投影 (見“正交補餘與投影定理”)。

 
令目標函數 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})=0k=1,\ldots,mm<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 乘數法的應用:

Advertisements
This entry was posted in 特別主題 and tagged , , , , , . Bookmark the permalink.

7 則回應給 Lagrange 乘數法

  1. 張盛東 說:

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

  2. Ethan 說:

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

    • ccjou 說:

      上文提到:在滿足限制的情況下,駐點發生於 \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=2yy=x^2。將後面兩式代入第一式,
      (1+2x^2)x=0,取實數解 x=0,故 y=0\lambda=0

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s