tags: ML數學分部

拉格朗日乘數 ( Lagrange Multiplie )

拉格朗日乘數是用來解最佳化的一種方法
簡單來說，當我今天有一函數

$f(x,y)$ 和一個限制條件

$g(x,y)=0$
要求滿足

$g$ 條件在

$f$ 的極值，也可以看成是求

$g$,

$f$ 相交面的極值，就可用拉格朗日乘數求解

1. 求解方法

要求出兩函數相交的極值，就必須先找出兩者之間的關係
假設兩函數在相交的切線上為以下函數

$$f(x,y)=c$$

$$g(x,y)=0$$

對兩式子做偏微分 ( 這邊假設用 x )

$$\frac{\partial f}{\partial x}=f_x+f_y\frac{\partial y}{\partial x}=0$$

$$\frac{\partial g}{\partial x}=g_x+g_y\frac{\partial y}{\partial x}=0$$

可以得出

$f_x,f_y$ 分別為

$g_x,g_y$ 的

$\lambda$ 倍 ( 未知 )
最後寫成下式

$$\mathrm{\nabla }f=\lambda \mathrm{\nabla }g$$

通常又會該寫成下式，

$\lambda$ 會因函數改寫而正負不同，但就是為一常數

$$\mathrm{\nabla }L(x,\lambda )=\mathrm{\nabla }f+\lambda \mathrm{\nabla }g=0$$

$$L(x,\lambda )=f+\lambda g$$

$$g(x,y)=0$$

利用以上兩式關係，就可求出在

$g(x,y)$ 限制下

$f(x,y)$ 的最小值
也可以很容易用幾何關係看出

之後進行求解步驟如下

1. 利用關係式求出
   $\lambda$
2. 代回
   $\lambda$ 求出函數極值

2. KKT ( Karush-Kuhn-Tucker )

如果將約束條件改為

$$g(x,y)\le 0$$

將範圍限制在

$g(x,y)$ 內部，而非

$g(x,y)$ 交點上
就會將原來的 Lagrange 乘數推廣到多個條件的約束

新增條件

$h(x,y)$ 和乘子

$\mu$

$$g(x,y)\le 0$$

$$\lambda >0$$

$$L(x,\lambda ,\mu )=f+\sum _{i=1}^m{\lambda }_i{g}_i+\sum _{j=1}^n{\mu }_j{h}_j$$

$$\mathrm{\nabla }L(x,\lambda ,\mu )=\mathrm{\nabla }f+{\lambda }_i\mathrm{\nabla }{g}_i+{\mu }_j\mathrm{\nabla }{h}_j=0$$

3. reference

Lagrange乘數 ( CUSTCourses )

線代啟示錄-Karush-Kuhn-Tucker (KKT) 條件

机器学习中的数学——拉格朗日乘子法（一）

机器学习中的数学——拉格朗日乘子法（二） KKT