SVM——直观理解拉格朗日乘子法

拉格朗日乘子法是一种多元函数在变量收到条件约束时，求极值的方法，这里用来解决SVM目标函数最优化问题。

1、可视化函数及其约束条件

以二元函数为例。

（被约束的）函数

假设$z=f(x,y)$z=f(x,y)，涉及x,y,z，可以再三维空间中画图图像：

（函数的）约束条件

函数$f(x,y)$f(x,y)的约束条件为$g(x,y)=0$g(x,y)=0，$g(x,y)=0$g(x,y)=0又可以写成：$y=h(x)$y=h(x)的形式，表达x与y两者之间的相互关系，在二维直角坐标系中是一条曲线。

约束条件对函数的约束

如何体现一个二维图形对一个三维图形的约束：

1. 在自己的头脑中建立一个三维直角坐标系，有 x轴、y 轴、z 轴， 它们互相垂直。
2. $f(x,y)$f(x,y)对应图形是三维坐标系里的一个曲面——一个（可能是奇形怪状）的体的外壳
3. 在z=0平面上，把$y=h(x)$y=h(x)的图形画出来（曲线）
4. 将第 3 步做出的那条曲线沿着平行 z 轴的方向平移，它平移过的轨迹也形成了一个曲面，这个曲面和$z=f(x,y)$z=f(x,y)形成的曲面相交，交叠部分是一条三维空间中的曲线；
5. 换个角度考虑，第4步形成的曲线，其实就是g(x,y)=0在z=0平面上形成的曲线，在$z=f(x,y)$z=f(x,y)形成的曲面上的投影。
   举例：
   
   如图可看出，$f(x,y)$f(x,y)是存在极大值的，同时因为约束条件是$g(x,y)=0$g(x,y)=0，所以我们如果取如下目标：
   
   对应点一定位于$g(x,y)=0$g(x,y)=0投影到$f(x,y)$f(x,y)上之后形成的那条曲线上，比如如图中B点，尽管它不一定是$z=f(x,y)$z=f(x,y)的最大值，但却是符合约束条件$g(x,y)=0$g(x,y)=0的极大值

2、拉格朗日乘子法

目标函数

其中的自变量为w和b，也是一个二元函数（$x_i$xi​和$y_i$yi​都是样本值，已知数值，$\frac{||w||^2}{2}$2∣∣w∣∣2​虽然只包含w，但我们可以想象它也是一个二元函数，只不过变量b的系数为0）。

进一步抽象为：

这个约束条件其实可以写作：

不等式约束条件难度稍大，先从等式约束条件开始。

等式约束条件

假设我们的目标函数是：

在一张图中做出$f(x,y)$f(x,y)和$g(x,y)$g(x,y)的等高线（三维图形投影到二维平面后的结果）：

绿线是$g(x,y)$g(x,y)的等高线，因为约束条件是$g(x,y)=0$g(x,y)=0,因此，只有一条$g(x,y)$g(x,y)的等高线（$g(x,y)=0$g(x,y)=0）对我们有意义，因此只画它即可。

蓝线是$f(x,y)$f(x,y)的等高线，图中两条蓝线具体对应的函数分别是$f(x,y)=d_1$f(x,y)=d1​和$f(x,y)=d_2$f(x,y)=d2​，其中$d_1$d1​和$d_2$d2​是两个常数，对应上图中两个蓝圈对应的z轴坐标，此处$d_2&lt;d_1$d2​<d1​。

图中的红点，映射到f(x,y)上，就是取得$f(x,y)$f(x,y)符合$g(x,y)=0$g(x,y)=0的约束的极小值的点。设红点的自变量值为$(x^*,y^*)$(x∗,y∗)。

此处需要用到一个概念，函数的梯度：表示该函数在某点处的方向导数，方向导数是某个多维函数上的点沿每个维度分别求导后，再组合而成的向量。记作：

一个函数的梯度是与它等高线垂直的。因此，在红点处，$f(x^*,y^*)$f(x∗,y∗)的梯度与$f(x,y)=d_2$f(x,y)=d2​在$(x^* ,y^*)$(x∗,y∗)处的切线垂直，$g(x^*,y^*)$g(x∗,y∗)的梯度与$g(x,y)=0$g(x,y)=0在$(x^*, y^*)$(x∗,y∗)处的切线垂直。

又因为$f(x,y)=d_2$f(x,y)=d2​对应的蓝线与$g(x,y)=0$g(x,y)=0对应的绿线在$(x^*, y^*)$(x∗,y∗)处是相切的。

解释一下为何一定相切：如果不想切，要么不相交，约束条件$g(x,y)=0$g(x,y)=0不能约束$f(x,y)$f(x,y)；如果相交，会产生两个交点，这样就可以重新做一条$f(x,y)$f(x,y)的等高线，让新等高线和$g(x,y)=0$g(x,y)=0相切。

在$(x^*,y^*)$(x∗,y∗)点处$f(x,y)$f(x,y)与$g(x,y)$g(x,y)的梯度，要么方向相同，要么方向相反。所以一定存在$\lambda=\not 0$λ≠​0使得：

这时，$\lambda$λ成为拉格朗日乘子。

拉格朗日乘子和拉格朗日函数

定义拉格朗日函数：$L(x,y, \lambda)=f(x,y)+\lambda g(x,y)$L(x,y,λ)=f(x,y)+λg(x,y)

拉格朗日函数对x,y求偏导：

令偏导数为0：

$f(x,y)$f(x,y)符合$g(x,y)=0$g(x,y)=0约束的极小值的点$(x^*,y^*)$(x∗,y∗)满足：

导函数形式：

即我们要求的极小值点正好满足拉格朗日函数对x,y求导后，令其结果为0形成的导函数。既然如此，当然可以引入一个新变量：$\lambda$λ，和目标函数、约束条件一起，先构造出拉格朗日函数$L(x,y,\lambda)$L(x,y,λ)，再令$L^{&#x27;}_{x,y}(x,y,\lambda)=0$Lx,y′​(x,y,λ)=0，之后通过最优化$L^{&#x27;}_{x,y}(x,y,\lambda)=0$Lx,y′​(x,y,λ)=0，求取$(x^*,y^*)$(x∗,y∗)的值。

另外，令拉格朗日函数对$\lambda$λ求偏导的结果为0：$L^{&#x27;}_\lambda(x,y,\lambda)=0$Lλ′​(x,y,λ)=0,就得到了约束条件：$g(x,y)=0$g(x,y)=0。拉格朗日函数也可以通过求导变化成约束条件本身。

不等式约束条件

前面条件分：$g(x,y)&lt;=0$g(x,y)<=0，可以拆为：$g(x,y)=0 or g(x,y)&lt;0$g(x,y)=0org(x,y)<0这两种情况，这两种情况下可以先取一个极小值，然后在与极小值比较。

拆分后的严格不等式约束条件：$g(x,y)&lt;0$g(x,y)<0，而对于$g(x,y)&lt;0$g(x,y)<0情况，条件处于一个区间，而不能在三维坐标系中表示成某个固定的曲面。这种情况下，如果$f(x,y)$f(x,y)的极小值就在这个区间里，然后直接对$f(x,y)$f(x,y)求无约束的极小值即可，对应到拉格朗日函数就是：令$\lambda=0$λ=0，直接通过令$f(x,y)$f(x,y)的梯度为0求$f(x,y)$f(x,y)的极小值。求出极小值$f(x^*,y^*)=0$f(x∗,y∗)=0之后，再判断$(x^*,y^*)$(x∗,y∗)是否符合约束条件。

拆分后的等式约束条件：$g(x,y)=0$g(x,y)=0（参照上一节内容），需要注意的是，在仅有等式约束条件时，我们设

只要常数KaTeX parse error: Expected 'EOF', got '\labmda' at position 1: \̲l̲a̲b̲m̲d̲a̲=\not=0就可以了。
但是在以从$g(x,y)&lt;=0$g(x,y)<=0中拆分出来的等式为约束条件时，我们要求：存在常数$\lambda&gt;0$λ>0，使得
可视化表示，下图为不等式约束的两种情况：

图中黑点表示最终满足约束条件的函数极小值。

如果是左图的情况，限制条件就又变成了$g(x,y)&lt;0$g(x,y)<0，且直接求$f(x,y)$f(x,y)极小值就行。

如果是右图情况，不等式约束条件才又变成了等式。这种情况，才是我们在拆分不等式条件后有意义的情况。

在这种情况下，最终找到的符合约束条件的极小值$f(x^*,y^*)$f(x∗,y∗)肯定不算$f(x,y)$f(x,y)的极小值。

函数梯度的物理意义：一个函数在某一点的梯度方向（向量方向）指明了该函数的函数值相对于当前函数值增量的方向，也就上说，在$g(x^*,y^*)$g(x∗,y∗)的梯度方向上前进一个长度a（很小），到达$g(x^{**},y^{**})$g(x∗∗,y∗∗)，因为$g(x^*,y^*)=0$g(x∗,y∗)=0，又根据梯度的物理意义，则$(x^*,y^*)$(x∗,y∗)点处g()函数的梯度方向指向的是$g(x,y)&gt;0$g(x,y)>0的区域。

可是偏偏我们的约束条件是$g(x,y)&lt;0$g(x,y)<0，即不等式约束条件对应的区域与$(x^*,y^*)$(x∗,y∗)点处$g()$g()函数的梯度方向是相反的。

现在来看图中右图的情况，此时$f()$f()函数带约束条件的极小值点$(x^*,y^*)$(x∗,y∗)就位于$g(x,y)=0$g(x,y)=0对应的曲线上，而$(x^*,y^*)$(x∗,y∗)点处$f()$f()函数的梯度方向正是$f()$f()函数本身的增量方向，因此在$g(x,y)&lt;0$g(x,y)<0所在的区域对应的应该是$f(x,y)$f(x,y)的递增方向，如若不然，就是左图的情况。

只有当$f(x,y)$f(x,y)梯度方向和$g(x,y)&lt;0$g(x,y)<0区域所在方向相同，也就是和$(x^*,y^*)$(x∗,y∗)点处$g()$g()函数梯度方向相反，那么$f(x,y)$f(x,y)的约束条件极小值才会出现在$g(x,y)=0$g(x,y)=0的曲线上，所以，在这种情况下，存在常数$\lambda &gt;0$λ>0，使得：

进而导出：

KKT约束条件

将上面拆分开的严格不等式和等式两种情况整合起来：

1. 如果严格不等式成立时得到$f()$f()函数的极小值，则有$\lambda=0$λ=0，这样才能将拉格朗日函数直接转换为原始函数，则有$\lambda g(x,y)=0$λg(x,y)=0
2. 如果等式成立得到$f()$f()函数的约束条件极小值，则必然存在$\lambda&gt;0$λ>0，且同时$g(x,y)=0$g(x,y)=0，因此也有$\lambda g(x,y)=0$λg(x,y)=0
   于是，对于不等式约束条件$g(x,y)&lt;=0$g(x,y)<=0，最终的约束条件变成了：
   
   这样由1变3的约束条件，叫做KKT约束条件。

目标函数转化为拉格朗日函数

KKT条件不是单独成立的，它是拉格朗日乘子法的一部分，当我们在约束条件下求解函数最优化问题，且约束条件为不等式时：

我们针对目标函数生成拉格朗日函数为：

同时有KKT条件：

假设最优化结果对应点为$(x^*,y^*)$(x∗,y∗)，则当目标函数为：

若存在$\lambda=\not0$λ≠​0，使得$f^{&#x27;}_{x,y}(x^*,y^*)+\lambda g^{&#x27;}_{x,y}(x^*,y^*)=0$fx,y′​(x∗,y∗)+λgx,y′​(x∗,y∗)=0，则$\lambda&gt;0$λ>0。

而当目标函数为：

若存在$\lambda=\not0$λ≠​0，使得$f^{&#x27;}_{x,y}(x^*,y^*)+\lambda g^{&#x27;}_{x,y}(x^*,y^*)=0$fx,y′​(x∗,y∗)+λgx,y′​(x∗,y∗)=0，则$\lambda&lt;0$λ<0。

注意：

1. KaTeX parse error: Expected 'EOF', got '\lambdag' at position 23: …lambda)=f(x,y)+\̲l̲a̲m̲b̲d̲a̲g̲(x,y)是拉格朗日函数的定义；
2. $\lambda&gt;=0$λ>=0是之前我们推导出来的KKT条件；
3. 存在常数$\lambda&gt;0$λ>0，使得$f^{&#x27;}_{x,y}(x^*,y^*)+\lambda g^{&#x27;}_{x,y}(x^*,y^*)=0$fx,y′​(x∗,y∗)+λgx,y′​(x∗,y∗)=0或者$f^{&#x27;}_{x,y}(x^*,y^*)-\lambda g^{&#x27;}_{x,y}(x^*,y^*)=0$fx,y′​(x∗,y∗)−λgx,y′​(x∗,y∗)=0是推导KKT条件过程中经历的一个步骤——这个步骤中设计到的是在$(x^*,y^*)$(x∗,y∗)这个确定点处$f$f函数和$g$g函数的梯度。

思考：求极大值时为什么 λ 符号不同，就需要自己去推导

.