SVM系列第六讲--拉格朗日乘子法

在前面的几讲中，我们终于引出了支撑向量的概念，同时得到了求解最大间隔分类器的目标规划式，接下来，我们就要对该式进行求解，但在正式求解之前，我想介绍一下求解需要了解的两个知识，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件。在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。这一节，我们先来介绍拉格朗日乘子法。

我们这里提到的最优化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化，即最大值问题可以转化成最小值问题)。 一般情况下，最优化问题会碰到一下三种情况：

1、无约束条件

这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。

2、等式约束条件

这里的等式约束条件一般形式如下：

等式约束条件

则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，这里主要讲拉格朗日法，因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。

我们先通过一个例子来直观感受下拉格朗日乘子法，至于为什么这么做是可行的，后面会进一步介绍。
假设我们的目标函数如下：

目标函数

约束条件如下：

约束条件

拉格朗日乘子法的一般做法是将约束条件加入到目标函数中，将问题转化为无约束条件的问题，随后对参数进行求导解得极值。

问题转化

到我们的题目中，我们将有约束的最优化问题转换为无约束的最优化问题如下：

问题转化

可以看到，现在的问题中有四个参数，我们分别对四个参数求偏导数：

偏导

对后联立四个方程可以求解得到：

求解
则最优化问题的解是：
解

3、拉格朗日乘子法的解释

为什么这么做是可行的呢？维基百科上的解释很好，这里我拿来用一下。以一个最简单的二维优化问题为例：

 min f(x,y)    
 s.t. g(x,y) = c

这里画出z=f(x,y)的等高线：

等高线

绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率，和等高线的法线平行。从梯度的方向上来看，显然有d1>d2。绿色的线是约束，也就是说，只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束，f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束，最小值点应该在哪里呢？显然应该是在f(x,y)的等高线正好和约束线相切的位置，因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。

相切的时候满足什么条件呢？从图上的梯度方向箭头可以很明显的看出来，相切的时候f(x,y)和g(x,y)的梯度一定是在同一个方向上的，也就是说∇f(x,y)=λ（∇g(x,y)-C) ，这里∇代表函数的梯度。

这时候再来看我们的之前例子的求解过程，我们对所有参数求偏导数：

偏导数

令上面式子中的前三个等于0，其实就是令∇f(x,y)=λ（∇g(x,y)-C)，
而第四个式子恰好是使求得的x,y,z满足我们原有的约束条件。所以可以看到，拉格朗日乘子法在求解等式约束条件的最优化问题时是可行的！

之前我们说最优化问题会碰到一下三种情况，这一讲只介绍了两种，第三种我们将留到下一讲中介绍！