通俗易懂 | 拉格朗日乘子法

站长亦新
站长亦新
站长亦新
81
文章
0
评论
2020年7月19日02:52:19 评论 125 1437字阅读4分47秒

在SVM中,将约束问题转化成非约束问题采用到了拉格朗日乘子法。这个文章就讲一下拉格朗日乘子法与KKT约束是怎么回事。本人不是数学科班出身,但是也只能硬着头皮讲一讲了。

从零理解

现在我们要解决这样一个问题:
x^2y=3
这个函数距离原点最近的距离是多少。

先画出函数图像:
通俗易懂 | 拉格朗日乘子法

然后想求出最短距离:
通俗易懂 | 拉格朗日乘子法

这里的思路就是,做一个以原点为中心的圆形:
通俗易懂 | 拉格朗日乘子法

不断扩大圆形的半径,直到圆与蓝色的曲线相切:
通俗易懂 | 拉格朗日乘子法

现在。第一次与x^2y=3相交的点就是距离原点最近的那个点:
通俗易懂 | 拉格朗日乘子法

这个,圆形与曲线相切,且切线既是圆形的切线,也是曲线的相切。
通俗易懂 | 拉格朗日乘子法

这时候,这个切线的垂线其实也就是我们所说的梯度,也叫做等高线的法线,看下面两个图可能会好理解一些:
通俗易懂 | 拉格朗日乘子法
通俗易懂 | 拉格朗日乘子法

那么这个梯度怎么计算呢?先看圆形f(x,y)=x^2+y^2的梯度:
通俗易懂 | 拉格朗日乘子法

再看曲线的梯度计算g(x,y)=x^2y的梯度:
通俗易懂 | 拉格朗日乘子法

在相切的时候,两者的梯度方向都在同一条直线上,可以称之为,成比例,这里用比例系数\lambda来表示:
通俗易懂 | 拉格朗日乘子法

所以我们汇总一下所有的已知信息,得到下面的方程组:
通俗易懂 | 拉格朗日乘子法

可以求解得到:
通俗易懂 | 拉格朗日乘子法

这个就是拉格朗日乘子法的直观理解。

抽象成数学的形式

我们要解决的问题:
\min {x^2+y^2}
s.t. x^2y=3

我们会将约束问题通过拉格朗日乘子法转换成非约束问题:
\min F(x,y)={x^2+y^2+\lambda(x^2y-3)}

【为什么可以这样呢?】
如果求极值,偏导数为0。先对上面的公式进行求偏导数:
\frac{\partial F(x,y)}{\partial x}=2x+\lambda 2xy=0
\frac{\partial F(x,y)}{\partial y}=2y+\lambda x^2=0

这两个等式与这个等价,唯一的不同就是\lambda一个是正数一个是负数:
通俗易懂 | 拉格朗日乘子法

当然,对于x^2y-3=0这个条件,我们也可以写成\frac{\partial F(x,y,\lambda)}{\partial \lambda},所以,可以得到这样的一个方程组:
通俗易懂 | 拉格朗日乘子法

KKT条件

  • KKT的英文全称:Karush-Kuhn-Tucker

之前的拉格朗日的约束条件是等值的,现在可以通过KKT条件推广到不等式。因为限制条件往往是不大于,小于这样的不等式,所以KKT才是拉格朗日化约束问题为非约束问题的关键。

对于不等式问题,就是有两种情况:
- 可行解在g(x)<0;
- 可行解在g(x)=0。

可行解在g(x)<0,就表示这个约束条件并没有起到约束效果,有根没有事一个效果(下图中的左图);可行解g(x)=0,就表示这个约束条件起到作用了,这就表示g(x)与f(x)相切,也就是下图中右边的图。

通俗易懂 | 拉格朗日乘子法

【g(x)<0的情况】
这种情况下,就是没有限制条件下的情况,其实就是没有约束条件的限制,也就是\lambda=0的情况,所以我们的等式就是直接求解:
\Delta f(x)=0

【g(x)=0的情况】
如果是g(x)=0的情况,那也就是约束条件起到作用了,也就意味着\lambda>0。在这种情况下,存在着:
\Delta f(x) = -\lambda \Delta g(x)
并且两个函数的扩张的方向相反,所以表明两个g(x)和f(x)的梯度一个是正数,一个是负数。所以这个表示\lambda>0

所以综上所述,在这种情况下,我们所有的条件综合起来可以得到,其中x^*就是最优解:
- \lambda >=0
- $\lambda g(x^)=0- g(x^) <= 0$

这三个就是KKT条件。


通俗易懂 | 拉格朗日乘子法
通俗易懂 | 拉格朗日乘子法

weinxin
我的微信
微信扫一扫
站长亦新
  • 本文由 发表于 2020年7月19日02:52:19
  • 转载请务必保留本文链接:http://helloworld2020.net/628/
工程能力大UP | 《炼丹大法》 公告

工程能力大UP | 《炼丹大法》

xavier、He和随机初始化都要尝试。使用一般的随机均值初始化CNN的参数,acc只能到70%,仅仅改成xavier,acc可以到98%。另外一次,使用xavier初始化效果不好,使用随机初始化效果...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: