函數 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 即值的必要條件
如果 $\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$
$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$
設在相對極值的座標$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求解
則可以順著該投影方向以及反方向移動
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求解
沒有留言:
張貼留言