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)),求出導數即得極值的必要條件 df/dx_1=0。這個方法的主要缺點是條件方程未必存在分析解,也就是說 x_2 無法寫成 x_1 的函數。此外,當變數數目增多且有多個條件方程時,縱使能夠得到分析解,最後產生的無約束目標函數也可能相當複雜。與上述作法比較,Lagrange 乘數法 (Lagrange multiplier) 不須解出條件方程,因而保留了變數之間的對稱性。由於兼具簡單與典雅兩個優點,Lagrange 乘數法是目前最常被使用的一種求解約束最佳化方法:令 Lagrangian 函數為

L(x_1,x_2,\lambda)\equiv 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}\epsilon_i+\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\frac{\partial^2f}{\partial x_i\partial x_j}\epsilon_i\epsilon_j+\cdots

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

\displaystyle \nabla f\overset{\underset{\mathrm{def}}{}}{=}\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^T\boldsymbol{\epsilon}+\frac{1}{2}\boldsymbol{\epsilon}^TH\boldsymbol{\epsilon}+\cdots

因為 \boldsymbol{\epsilon} 是微小向量,我們可以忽略二次以上所有項,就有 f(\mathbf{x}+\boldsymbol{\epsilon})\approx f(\mathbf{x})+\nabla f^T\boldsymbol{\epsilon}。在固定 \Vert\boldsymbol{\epsilon}\Vert 的前提下,當 \boldsymbol{\epsilon}=k\nabla f,其中 k 為正數,\nabla f^T\boldsymbol{\epsilon} 具有最大值。換句話說,梯度 \nabla f 指出函數 f 在點 \mathbf{x} 的最陡上升方向。若 \nabla f(\mathbf{x})=\mathbf{0},我們稱 \mathbf{x} 是一個駐點 (stationary point)。明顯地,駐點即為 f 的極值 (極大或極小) 存在的必要條件 (見“最佳化理論與正定矩陣”)。

 
接下來我們討論單一限制條件的情況。給定 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^T\boldsymbol{\epsilon}+o(\Vert\boldsymbol{\epsilon}\Vert^2)

其中 o(\Vert\boldsymbol{\epsilon}\Vert^2) 代表誤差。如果 \mathbf{x}+\boldsymbol{\epsilon} 也在超曲面上,即 g(\mathbf{x}+\boldsymbol{\epsilon})=g(\mathbf{x})=0,忽略微小誤差可得 \nabla g^T\boldsymbol{\epsilon}=0。見下圖 (以 \mathbb{R}^3 為例),\boldsymbol{\epsilon} 屬於點 \mathbf{x} 的切平面 (因為切平面是點 \mathbf{x} 的鄰近限制活動區域),\nabla g^T\boldsymbol{\epsilon}=0 表示 \nabla g 是超曲面 g(\mathbf{x})=0 於點 \mathbf{x} 的法向量,所以穿越點 \mathbf{x} 的切平面即為法向量 \nabla g 的正交補餘 (orthogonal complement),記為 \mathrm{span}\{\nabla g\}^{\perp}。為了在超曲面上尋找駐點,我們可以計算梯度 \nabla f 於切平面的正交投影,設為 \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

在滿足限制的情況下,駐點發生於 \nabla\hat{f}=\mathbf{0},此時 \nabla f 屬於 \mathrm{span}\{\nabla g\},故存在一個純量 \lambda 使得 \nabla f=-\lambda \nabla g (正負號可任意選定)。為了方便,我們定義 Lagrangian 函數

L(\mathbf{x},\lambda)\equiv 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}

其中第一式是駐點成立的條件,第二式是限制方程。

Tangent plane and gradient

 
Lagrange 乘數法可推廣至包含多個限制條件的約束最佳化問題。考慮 g_k(\mathbf{x})=0k=1,\ldots,mm<n,駐點存在的條件為 \nabla f 屬於子空間 \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(\mathbf{x},\lambda_1,\ldots,\lambda_m)\equiv 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 乘數法的應用:

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