Try   HackMD
tags: ML數學分部

拉格朗日乘數 ( Lagrange Multiplie )

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

f(x,y) 和一個限制條件
g(x,y)=0

要求滿足
g
條件在
f
的極值,也可以看成是求
g
,
f
相交面的極值
,就可用拉格朗日乘數求解

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →


1. 求解方法

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

f(x,y)=c

g(x,y)=0

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

fx=fx+fyyx=0

gx=gx+gyyx=0

可以得出

fx,fy 分別為
gx,gy
λ
倍 ( 未知 )
最後寫成下式

f=λg

通常又會該寫成下式,

λ 會因函數改寫而正負不同,但就是為一常數

L(x,λ)=f+λg=0

L(x,λ)=f+λg

g(x,y)=0

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

之後進行求解步驟如下

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

2. KKT ( Karush-Kuhn-Tucker )

如果將約束條件改為

g(x,y)0

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

將範圍限制在

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

新增條件

h(x,y) 和乘子
μ

g(x,y)0

λ>0

L(x,λ,μ)=f+i=1mλigi+j=1nμjhj

L(x,λ,μ)=f+λigi+μjhj=0


3. reference

Lagrange乘數 ( CUSTCourses )

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

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

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