Lagrange Multiplier

序言：對 n 維變數 $ X = \begin{bmatrix} x_1 \\[0.5em] \vdots\\[0.5em] x_n \end{bmatrix}$
函數 f(X) 在 g(X)-c=0 的限制條件下 ( f(X) 為連續可導實函數 )
在相對極值處， Lagrange function $F(X, \lambda) = f(X) + \lambda (g(X)-c) $ 符合：
$\nabla F=\frac{\partial F}{\partial X}=\begin{bmatrix} \frac{\partial F}{\partial x_1}\\[0.5em] \vdots\\[0.5em] \frac{\partial F}{\partial x_n} \end{bmatrix}=\vec{0}$    和    $ {\partial F \over \partial \lambda} =0$

用途：F 的極值，即為符合限制條件的 f 極值。可以透過 設 F 對 $x_1, x_2, ..., x_n$ 與對 $\lambda$ 梯度 = 0 求解

1. g(X)-c 的梯度函式，如代入座標 A=[a1, a2, ..., an]^T，即為 hyperplane g(X)-c=0 位於該座標的法向量

sol. using Taylor Expansion: $ g(X+\epsilon)=g(X)+\nabla g(X)^T\epsilon+O(\Vert\epsilon\Vert^2)$

如果  $ g(X+\epsilon)=g(X)$，則$\nabla g(X)^T\epsilon = 0$

2. f(X) 的梯度函式，如代入座標 B=[b1, b2, ..., bn]^T，即為函數f(X) 在該座標的最大上升方向

sol. using Taylor Expansion: $ f(X+\epsilon)=f(X)+\nabla f(X)^T\epsilon+O(\Vert\epsilon\Vert^2)$

if $\Vert\epsilon\Vert$ is fixed, $\nabla f(X)^T\epsilon$ has maximum when $\epsilon = k \nabla f(X), k>0$

如果 $\nabla f(X) = 0$，則該點本身就是 f 即值的必要條件

3. 在相對極值處，f(X) 的梯度函式與 g(X) 的梯度函式 有比例關係 

sol. 假設在相對極值處的座標為 C=[c1, c2, ..., cn]^T，如果 $\nabla f(C)$ 在 "g(C)之切空間"($g(C+\epsilon)=g(C)$) 上 的投影 不為$\vec{0}$
則可以順著該投影方向以及反方向移動
g(C) 不變，但f(C) 可以變大及變小，矛盾

不會有往兩個方向都變大或都變小的狀況：如果如此，f 函數本身在C有極值，$\nabla f(C)$ 會等於 $\vec{0}$

故求解時，變數須滿足：$\nabla f(X) + \lambda \nabla g(X) =0$

4. Lagrange Multiplier (單一限制條件)

在f(X)為相對極值，且g(X)-c=0 的條件下：

$df(X) = {\partial f \over \partial x_1}dx_1 + ... +{\partial f \over \partial x_n}dx_n$
$dg(X) = {\partial g \over \partial x_1}dx_1 + ... +{\partial g \over \partial x_n}dx_n$
又
\begin{cases}
{\partial f \over \partial x_1}dx_1 + \lambda {\partial g \over \partial x_1} dx_1 = 0 \\
{\partial f \over \partial x_2}dx_2 + \lambda {\partial g \over \partial x_2} dx_2 = 0 \\
\vdots \\
{\partial f \over \partial x_n}dx_n + \lambda {\partial g \over \partial x_n} dx_n = 0 \\
\end{cases}

加總上式：
$df(X) + \lambda dg(X) = 0$
integrate:
$f(X) + \lambda g(X) = constant$
上式可改寫為：
$f(X) + \lambda (g(X)-c) = constant$

而式中$f(X) + \lambda (g(X)-c)$符合
1. $\nabla ( f(X) + \lambda (g(X)-c) ) = \vec{0}$
2. $ {\partial  ( f(X) + \lambda (g(X)-c) ) \over \partial \lambda} =0$

5. 當有多個限制條件

設有m個限制條件：$g_1(X)=c_1, g_2(X)=c_2, ..., g_m(X)=c_m$
設在相對極值的座標$D=[d1, d2, ..., dn]^T$，則在與 $\nabla g_1(D), \nabla g_2(D), ..., \nabla g_m(D)$共同垂直的空間中，$g_1(D+\epsilon)=g_1(D), g_2(D+\epsilon)=g_2(D), ..., g_m(D+\epsilon)=g_m(D),$

由3.推導過程同理可得 $\nabla f(D)$ 在其共同垂直的空間中，投影為$\vec{0}$
故求解時，變數須滿足：$\nabla f(X) + \sum^m_{k=1} \lambda_k \nabla g_k(X) =0$

由4.推導過程同理可得$F = f(X) + \sum^m_{k=1} \lambda_k ( g_k(X) - c_k)$
F的極值，即為符合限制條件的f極值。可以透過 設F對$x_1, x_2, ..., x_n$與對$\lambda_1, \lambda_2, ..., \lambda_m $偏微分=0求解