当前位置：首页 > news >正文

python学智能算法（二十九）|SVM-拉格朗日函数求解中-KKT条件

news 2025/7/26 4:58:10

引言

前序学习进程中，对拉格朗日函数执行了初步求导，并获得了简化后的拉格朗日函数极值计算式：
$L(w,b,α)=∑i=1mαi−12∑i,j=1mαiαjyiyjxiTxjL(w,b,\alpha)=\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^Tx_{j}$
这个计算式遵循的约束是：
$∑i=1mαiyi=0\sum_{i=1}^{m}\alpha_{i}y_{i}=0$
上述结果其实还有一个专用名称：乌尔夫对偶。
不过我们就不对这个名称进行细说，因为还有大事要办：理解KKT条件。

KKT条件

对于寻找最佳分割超平面的拉格朗日函数： $L(w,b,α)=12∥w∥2−∑i=1mαi[yi(w⋅xi+b−1)]L(w,b,\alpha)=\frac{1}{2}{\left\|w\right\|}^2-\sum_{i=1}^{m}\alpha_{i}[y_{i}(w\cdot x_{i}+b-1)]$
首先我们证明它是个凸优化问题：
凸优化问题满足两个条件，第一个是目标函数为凸函数，第二个是约束条件是凸集。
凸函数，最经典的形式为抛物线函数 $y=x^2$ ，满足函数图像上任取两个点后连线，这两个点之间的所有函数取值都在这条线下方；
凸集，函数的取值范围内，取任意两个点连线后，这条线上的所有点依然在函数的取值范围内。
然后，回到拉格朗日函数，第一部分 $12∥w∥2\frac{1}{2}{\left\|w\right\|}^2$ 是典型的抛物线函数，是凸函数；
第二部分 $yi(w⋅xi+b−1)=w⋅(yixi)+byi−yiy_{i}(w\cdot x_{i}+b-1)=w\cdot(y_{i}x_{i})+by_{i}-y{i}$ ，因为变量是 $w$ 和 $b$ ，所以实际看下来这是一条关于 $w$ 和 $b$ 的线性函数（二维的时候理解为就是一根直线），线性函数既是凸函数也是非凸函数，而这一部分属于约束条件，所以约束条件是凸集。综合上述分析可知寻找最佳分割超平面的拉格朗日函数是个凸优化函数。
解决凸优化函数是在求解凸优化问题，找凸优化问题的极值要用到KKT条件。
平稳性条件：拉格朗日函数关于原始变量 $(w, b)$ 的梯度为0，
$∂L∂w==w−∑i=1mαiyixi=0\frac{\partial L}{\partial w}==w-\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i}=0$
$∂L∂b=−∑i=1mαiyi=0\frac{\partial L}{\partial b}=-\sum_{i=1}^{m}\alpha_{i}y_{i}=0$ 互补松弛条件：对于每个样本，拉格朗日乘子与约束的松弛量乘积为0,
$αi[yi(w⋅xi+b)−1]=0\alpha_{i}[y_{i}(w\cdot x_{i}+b)-1]=0$ 这表明，
当 $αi=0\alpha_{i}=0$ ，样本对超平面无影响；

当 $αi>0\alpha_{i}>0$ ，样本必须满足 $yi(w⋅xi+b)=1y_{i}(w\cdot x_{i}+b)=1$ ，样板刚好在超平面上；
原问题可行条件，样本必须满足分类约束：
$yi(w⋅xi+b≥1)(i=1,2,...,m)y_{i}(w\cdot x_{i}+b≥1)(i=1,2,...,m)$
对偶可行条件，拉格朗日橙子非负，
$αi≥0(i=1,2,...,m)\alpha_{i}≥0(i=1,2,...,m)$
KKT条件是判断拉格朗日函数存在最优解的核心准则，最优解一定满足KKT条件，满足KKT条件一定是最优解。