Lagrange Multiplier - 03

這裡我們討論一下 Lagrange multiplier.

我們知道, 如果想要解以下這個有限制式的最佳化問題 $$ \min_{x} f(x), \quad \text{subject to } \quad g(x)=k, $$ 一個方式是引進 Lagrange multiplier, $\lambda$, 然後可以列出以下兩個式子 $$ \partial_x f + \lambda \partial_x g = 0, \quad g(x)=k. $$

Question:

解出聯立方程後我們得到 $x^+$, $\lambda^+$, 帶入原函數得到 $f^+=f(x^+)$. 我們知道 $f^+$ 是最佳值, 而 $x^+$ 是最佳解. 那 $\lambda^+$ 是做什麼用的? 看起來只是為了解出原問題所引進的虛擬變數. 它有什麼作用嗎?

先說結論, $\lambda^+ = -\frac{df^+}{dk}$. 也就是告訴我們如果稍微改變限制式中的 $k$ 值, 那原題的最佳值會有怎樣的變化.

我們先引進 Lagrangian function $$ L(x, \lambda) = f(x) + \lambda (g(x) - k) $$ 並且知道原問題的解發生在 $\nabla L=0$ 的地方, 意即, $\nabla L(x^+, \lambda^+)=0$. 然後我們有 $$ L^+ = L(x^+, \lambda^+) = f(x^+) + \lambda^+(g(x^+)-k) = f^+. $$

在這裡我們要稍微小心一點. 固定一個 $k$ 值, 我們就有一個最佳化問題, 然後就可以解出 $x^+$ 跟 $\lambda^+$. 而當 $k$ 值改變時, $x^+$, $\lambda^+$, 甚至 $f^+$ 以及 $L^+$ 也都會跟著改變, 所以我們想像這四個值都是 $k$ 的函數: $$ x^+ = x^+(k), \ \lambda^+ = \lambda^+(k), \ f^+ = f^+(k), \ L^+ = L^+(k). $$ 再寫清楚一點就是 $$ L^+(k) = \left.L(x, \lambda,k)\right|_{x=x^+(k), \lambda=\lambda^+(k),k=k} $$

其中 $$ L(x, \lambda,k) = f(x) + \lambda (g(x) - k). $$

Remark: 讀到這邊也許會覺得有個奇怪的地方, 就是為什麼要把 $L$ 從雙變數變成三變數函數. 原因是當寫成 $L(x, \lambda)$ 時 $k$ 是個常數, 是不能變的. 想要改變 $k$ 值需要把它也當成一個變數比較合理.

接著我們就可以微分 $$ \frac{d L^+}{dk} = \left.\frac{\partial L}{\partial x}\frac{d x}{dk} + \frac{\partial L}{\partial \lambda}\frac{d \lambda}{dk} + \frac{\partial L}{\partial k}\right|_{x=x^+(k), \lambda=\lambda^+(k),k=k} = -\lambda^+. $$

Remark: $$ \left.\frac{\partial L}{\partial x}\right|_{x=x^+(k), \lambda=\lambda^+(k),k=k}= \left.\frac{\partial L}{\partial \lambda}\right|_{x=x^+(k), \lambda=\lambda^+(k),k=k}=0. $$

由於 $f^+ =L^+$, 所以我們也可以得到 $\frac{d f^+}{dk} = -\lambda^+$.

舉個例子

以下單位皆為元 or 萬元 or 千萬元, 請自行依喜好帶入!

• 假設我如果花費 $x$ 買進某一股票在一定時間後賣出可獲得 $2x$.

• 假設我如果花費 $y$ 買進某一貴金屬在一定時間後賣出可獲得 $10y-y^2$.

• 假設我總共可運用的財產只有 $10$.

那我應該花多少錢買股票花多少錢買貴金屬, 才能有最佳獲利呢?

我們可以列出以下限制最佳化問題

$$ \max_{x,y} f(x,y)=2x+(10y-y^2), \quad \text{subject to } \quad x+y=10, $$

1. 先引進 Lagrangian funtion $$ L(x,y,\lambda) = 2x+(10y-y^2)+\lambda(x+y-10) $$

2. 列出方程式 $\nabla L=0$: $$ \frac{\partial L}{\partial x} = 2 + \lambda =0, \quad \frac{\partial L}{\partial y} = 10-2y + \lambda =0, \quad \frac{\partial L}{\partial \lambda} = x+y-10 =0. $$

3. 解出得到 $$ x^+ = 6, \quad y^+=4, \quad \lambda^+=-2. $$ 也就是我們若以 $6$ 單位買進股票, $4$ 單位買進貴金屬, 一定時間賣出後可獲利 $f^+ = 36$ 單位.

4. 所以 $\lambda^+=-2$ 告訴我們 $\frac{d f^+}{dk}=-\lambda^+=2$, 意思就是如果我們增加一點 $k$ 值, 那獲利會是所增加數目的兩倍.

5. 將原題改成我目前可運用的財產有 $11$ (也就是多增加了 $1$), 那會發現最佳解是 $x^+=7$, $y^+=4$, $f^+=38$, 獲利真的增加 $2$ 單位了!

   • 如果這是真實情形, 那就告訴我們說如果去借 $1$ 單位的錢, 可以賺到 $2$ 單位. 如果借的錢加上利息會小於 $2$ 單位, 那就是個很好的投資, 應該去借.
   • 這例子比較特殊 $\lambda^+$ 恆等於 $2$, 所以才會那麼巧資金增加一單位獲利就增加兩單位. 一般而言這應該只是 linear appxoimation, 只有 $k$ 增加一點點時才會大約兩倍. 增加太多就不知道了.

References:

• Youtube: Meaning of the Lagrange multiplier

• Youtube: Proof for the meaning of Lagrange multipliers