Lagrange Multiplier - 01

在微積分課程裡我們有學到如何利用 Lagrange multiplier 來解 constraint optimization 問題. 這邊要介紹課本裡沒教的 Lagrangian function.

Goal: 我們想要解以下這個問題

$$ \min_{x} f(x), \quad \text{subject to } \quad g(x)=0. $$

Observation

微積分課本告訴我們一個相對好懂的直觀, 就是這個解會發生在兩個等高線相切的地方, 因此在這個問題的解那個點的位置, 兩個函數 $f$ 與 $g$ 等高線的法向量會平行, 因此可以列出以下兩個式子 $$ \partial_x f + \lambda \partial_x g = 0, \quad g(x)=0. $$ 這裡我們引進一個新的未知數 $\lambda$, 即稱為 Lagrange multiplier. 因為有兩個方程式, 因此我們可以解出兩個未知數 $x$ 以及 $\lambda$.

上列的這個方程組有另一種相對好記的方式, 就是引進所謂的 Lagrangian function $$ L(x, \lambda) = f(x) + \lambda g(x) $$ 這是一個雙變數方程式, 而原本問題的解會發生在這個方程的 critical point, 也就是會滿足 $\nabla L=0$.

要注意的是由於 $L$ 是個雙變數函數, 所以 $\nabla = (\partial_x, \partial_{\lambda})$. 根據這樣的定義我們將 $\nabla L=0$ 方程式列出來會得到跟上面一模一樣的兩個方程組.

Remark 1: $\partial_{x} L = \partial_x f + \lambda \partial_x g$

Remark 2: $\partial_{\lambda} L = g(x)$

引進 Lagrangian function 比較好記是因為假設我有更多的 constraints, 例如我想解以下這個問題: $$ \min_{x} f(x), \quad \text{subject to } \quad g_1(x)=0, \quad g_2(x)=0. $$ 要找一個函數最小值不過有兩個限制條件.

這樣的話我們照之前的步驟, 先引進 Lagrangian function $$ L(x, \lambda_1, \lambda_2) = f(x) + \lambda_1 g_1(x) + \lambda_2 g_2(x) $$ 然後原問題的最佳解會發生在 $\nabla L=0$.

要注意的是這次的 $L$ 是個三變數函數, 所以 $\nabla L = (\partial_x, \partial_{\lambda_1}, \partial_{\lambda_2})$. 然後將 $\nabla L=0$ 寫下來就是 $$ \partial_x f + \lambda_1 \partial_x g_1 + \lambda_2 \partial_x g_2 = 0, \quad g_1(x)=0, \quad g_2(x)=0. $$ 就得到我們需要解的方程組了!

接著我們試著將以上寫的更廣義一點, 考慮一個 $n$ 維度的最佳化問題有 $m$ 個限制式, 我們引進一些符號: $\pmb{x}\in \mathbb{R}^n$, $\pmb{g}(\pmb{x}):\mathbb{R}^n\to\mathbb{R}^m$, 這個有限制的最佳化問題即可寫成 $$ \min_{\pmb{x}\in\mathbb{R}^n}f(\pmb{x}), \quad \text{subject to } \quad \pmb{g}(\pmb{x})=\pmb{0}. $$

我們接著引進 Lagrangian function $$ L(\pmb{x}, \pmb{\lambda}) = f(\pmb{x}) + \pmb{\lambda}^T \pmb{g}(\pmb{x}), \quad \pmb{\lambda}\in\mathbb{R}^m $$

原問題的最佳解會發生在 $\nabla L=0$, 也就是 $(\nabla_{\pmb{x}} L, \nabla_{\pmb{\lambda}} L) = (0, 0)$, 也就是 $$ \nabla_{\pmb{x}} f(\pmb{x}) + \pmb{\lambda}^T \nabla_{\pmb{x}}\pmb{g}(\pmb{x}) = 0, \quad \pmb{g}(\pmb{x})=\pmb{0}. $$

所以為什麼要引進 Lagrange multiplier 或是 Lagrangian function?

• 引進 Lagrange multiplier 的好處是我們將一個最佳化問題改寫成一個求根問題. 理論上 $F(x)=0$ 這種問題不管線性或非線性我們都比較會解. 而最佳化問題就相對比較無從下手.

  BUT, 付出的代價是我們增加了維度! 原本 $n$ 維最小值問題變成 $n+m$ 維求根問題.

• 引進 Lagrangian function 最明顯的好處是比較好記, 不管是記在頭腦裡或是做筆記寫下來. 整個問題很輕易的就記成 $\nabla L=0$.

  當然還有其他更重要的好處, 就是可以推導出所謂的 dual optimization problem: Lagrange Multiplier - 02.

• Lagrange multiplier $\lambda$ 感覺起來很像一點用都沒有, 就是為了解出問題過程所引進的虛擬變數. 其實它還是有一點意義的, 可見: Lagrange Multiplier - 03