【1】引言
前序学习阶段中,我们掌握了最佳分割超平面对应的构造拉格朗日函数极值为:
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}^{T}x_{j}L(w,b,α)=i=1∑mαi−21i,j=1∑mαiαjyiyjxiTxj
这个极值有一个天然的约束:
∑i=1mαiyi=0\sum_{i=1}^{m}\alpha_{i}y_{i}=0i=1∑mαiyi=0
如果对此还有些不理解,可以回顾之前的学些文章拉格朗日函数求解和KKT条件初步,写得比较缓慢而细碎,希望大家不要介意。
那KKT条件究竟是为何提出的,实际上KKT条件的作用是把约束融入优化条件,让我们能像处理无约束问题一样,用一套规则判断有约束时的最优解。
【2】理解
先明确KKT条件的应用场景。
加入我们要解决一个带约束的优化问题,比如最大化收益,最小化成本。当如果没有约束时,我们计算极大值或极小值往往很方便,然而一旦有了约束,目标函数的“最优方向”就有可能被约束条件挡住了。
KKT条件的作用就是,判断当前点是不是“既满足所有约束,又无法在不违反约束的前提条件下变得更好”的点,也就是找出局部最优价。
然后我们用“力的平衡”来理解KKT条件的核心思想。
想想我们站在约束条件形成的区域里,目标函数对我们有一个“拉力”,二每个约束条件都是一个“阻力”,最优解就位于拉力和阻力相平衡的地方。
具体来说,等式约束像绳子,绳子拉力与目标函数的拉力平衡;不等式约束像一堵墙,没碰到墙的时候没有力,一旦碰到了墙,墙的推力会与目标函数的拉力平衡,也就是给墙的力有多大,受到的反作用力就有多大。
然后来尝试把“力的平衡”拆解成KKT条件的5条规则:
梯度为零(力的平衡方程):目标函数的梯度=所有起作用的约束条件的梯度的加权和(权重是拉格朗日乘子)。
直观理解,目标函数的“拉力”被约束“推力”刚好抵消,合理为零,无法移动。不等式约束条件(不能越界),如果不满足,这个点违反约束,不可能是最优解。
拉格朗日乘子非负(推力方向正确),不等式约束的权重必须非负,因为代表约束的“推力”方向必须与目标函数的“拉力”方向相反。
互补松弛性,也就是没有碰到墙不算,没有触发反弹。
等式约束条件,理解为绳子刚好勒紧,此时约束严格成立。
【3】总结
最KKT条件进行了进一步解读。