SVM（二）：KKT条件最直白的解释

冷不防 2023-01-07 14:25 165阅读 0赞

### 目录 ###

*  约束有否有效的问题
 *  求解
 *  KKT条件

# 约束有否有效的问题 #

*  在KKT条件的诸多大佬的解释中，都有一个关于约束是否有效的讨论，然而大多数人都没有讲清楚，什么是所谓的约束是否有效，下面我想先针对这个问题进行一个解释。
 *  首先给出不等式约束条件，以及目标。  
    ![在这里插入图片描述][20210118102829807.png]
 *  我们称符合g(x)<=0的区域为**约束域**，称f(x)的取值区域为**目标域**。
 *  然后下图中，左图是约束无效，右图是约束有效的两种情况，**红色的是约束域，蓝色等高线是目标域**：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70]  
    先看左图，当**目标域最小值点（即某点使得f(x)取到最小值，注意，不是极小值，而是局部最小值）落到红色约束域中的时候就意味着红色约束域的约束效果是无效的。** 为什么，因为即便不存在你这个红色约束域的约束条件，我仅仅对f(x)函数求最小也同样是得到左图中蓝色的**目标域最小值点** 且天然地符合了约束条件，那你的约束条件还有什么用呢？那请问，当什么时候约束条件有用呢？
 *  举个例子，  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 1]  
    请看上图，一个人拉着一只狗，假设人不动，**人站的位置就是上图红色约束域的中心位置**。而你就是那条被拴着的狗，你被一根狗绳约束着，你只能取得半径假设为5米内的食物，而食物的坐标位置就是**目标域局部最小值点（切记！是最小值，不是极小值）**。**倘若食物距离你5米以内，你觉得这个绳子还有约束力嘛？** 显然没有，这种情况就是左图的情况。那假如食物距离你10米，这条狗也就是你肯定会沿着直线方向去尽可能的接近食物，但即便如此，也够不到食物，只能使得自己与食物的距离尽可能的小，而f(x)代表是就是你这条狗与食物的距离，你想啊，本来没有狗绳的话，你就能直接吃到食物了（即到达目标域局部最小值点，此时f(x)很完美，达到了最小值0），然而有了狗绳，你只能望食兴叹（此时，你到达目标域某点，此点是f(x)尽可能小的位置，称为f(x)在这个约束下取到的最小值点，是另一种意义上的极小值点，想象一下你被约束的样子，使劲狗刨也无法接近目标半步，是这种意义上的极小值点），这种情况对应右图。
 *  上面的解释足够清楚了吧！现在你发现什么问题呢？当约束无效的时候，你没有被狗绳约束到，你在半径5m的约束域的**内部**，而约束无有效的时候，你尽力挣扎，不停狗刨，所以你在半径5m的约束域的**边界**。见下图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 2]  
    换句话说，取到f(x)的局部最小值时若g(x)<0，则表示约束无效，反之若g(x)=0，则约束有效，正是因为这两种情况同时存在，所以才有了KKT条件。

# 求解 #

*  现在我们不妨将问题进一步拓展，同时包含等式约束和不等式约束：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 3]
 *  然后是对应的拉格朗日：  
    ![在这里插入图片描述][2021011810551946.png]  
    **解释公式：**  
    前半部分是等式约束的拉格朗日公式，不用解释，我们重点看一下后面那个 β ∗ g ( x ) β\*g(x) β∗g(x)，看到上面后半部分公式同时联系我上一篇文章对于拉格朗日乘数法的解释的话，你应该能得到下面的公式：  
     ▽ ( f ( x ) + α h ( x ) ) = 0 ▽(f(x)+αh(x))=0 ▽(f(x)\+αh(x))=0和 ▽ ( f ( x ) + β g ( x ) ) = 0 ▽(f(x)+βg(x))=0 ▽(f(x)\+βg(x))=0，其中α取非负数，因为等式约束下，梯度的方向可以同向可以反向，只要在一条直线上就好，只要平行就好。所以α仅仅是一个伸缩量。  
    **β就不同了！**，请看下图！  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 4]  
    你能标出**约束域和目标域在目标函数f(x)取到局部最小值的那个点的梯度方向**嘛，如果不能，赶紧去补一补梯度的知识！！！！附上链接：https://blog.csdn.net/whu\_student/article/details/77918020  
    我给你标出来吧！  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 5]  
    如图，黑色点是**目标函数f(x)取到局部最小值的那个点，也就是你被狗绳拴住的时候尽可能靠近深蓝色食物的地方**，红色箭头是**约束函数g(x)在该点的梯度**，蓝色箭头则是**目标函数f(x)在该点的梯度**，不懂梯度方向怎么标记的要看上面的链接哦~。  
    由此我们得出 − ▽ f ( x ) = β ▽ g ( x ) 且 β > 0 -▽f(x)=β▽g(x)且β>0 −▽f(x)=β▽g(x)且β>0，对吧！此时是g(x)=0的时候，狗吃不到食物哦，β肯定是>=0的，否则梯度方向就不对了！~  
    那有人可能会说了，β此时取0可以吗，我感觉也可以，但是，这种情况不是上面的任何一种情况，因为倘若此时β取0，则意味着▽f(x)=0，也就是说，是对应这么一种情况，我手绘一下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 6]  
    这种情况也是存在的，不过你想啊，上面这种情况对应β=0，同时你感觉一下， 是不是还是约束无效的情况？是的！所以其实可以和左图的情况认为是一种情况，只不过这是一种特殊的左图情况。我们不把这种情况纳入讨论，所以依然认为在右图的情况下β>0，不过我们要清楚有这么一种情况，这是对于数学严谨性的尊重。  
    同时，我还想解释一下▽f(x)=0的情况，限于个人绘图能力，请大家想象一下一个xyz坐标系，f(x)是纵轴，x和y是变量，然后f(x)的形状是一个平底锅，而g(x)假如就是一个倒三角锥吧，然后最底部最尖端正好与平底锅中间某点重合，这个点的▽f(x)是0，而且满足在g(x)边界，即g(x)=0。这就是上面的情况。  
    好了这不是重点（g(x)=0时β=0的情况不是重点讲解的内容，我上面忍不住提了一嘴），我们继续往下进行，既然有了 − ▽ f ( x ) = β ▽ g ( x ) 且 β > 0 -▽f(x)=β▽g(x)且β>0 −▽f(x)=β▽g(x)且β>0这个式子，我们就合并公式吧。其实你也可以看出来，当g(x)=0的时候，其实就变成了等式约束的情况，所以为何不能和h(x)一起用拉格朗日乘数法呢？所以合并公式！  
    将它们合并到一起，就是 ▽ ( 2 ∗ f ( x ) + α h ( x ) + β g ( x ) ) = 0 ▽(2\*f(x)+αh(x)+βg(x))=0 ▽(2∗f(x)\+αh(x)\+βg(x))=0，方程两边同除以2，不会影响α和β的符号。所以得到下面公式：  
     ▽ ( f ( x ) + α h ( x ) + β g ( x ) ) = 0 ▽(f(x)+αh(x)+βg(x))=0 ▽(f(x)\+αh(x)\+βg(x))=0，所以得到：  
    ![在这里插入图片描述][20210118112129200.png]

# KKT条件 #

*  下面是KKT条件，我先列出来，然后一一解释：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 7]  
    （1）不用解释了吧，偏导数=0，这是拉格朗日乘数法的标准操作，这个例子中只有x一个变量，如果有多个变量的话也要一起偏导数=0哦！  
    （3、4）原始约束条件，不用多说。  
    （2、5）这两个我要放到一起解释，记得嘛，g(x)=0的时候，由于梯度方向的约束以及f(x)的梯度此时不=0，所以β>0，此时2、5条件同时满足；那假如是约束无效的情况，即g(x)<0呢，此时，由于约束彻底无效了，就不要管这个g(x)了，它不配在拉格朗日乘数法对应的公式中占有一席之地了，所以此时对应β=0！此时你发现，2、5条件依然同时满足。这就是其精妙之处！因为你不知道问题的g(x)约束到底有没有效果，所以你要包含两种情况，而2、5公式就将其巧妙的包含在了一起。  
    太妙了，又是被数学折服的一天~

[20210118102829807.png]: /images/20221119/87e29dc87a7b4512a0cca7e28c1589f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70]: /images/20221119/34ba59bc82ee4476b369c9d1593c7825.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210118103938403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210118105045175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210118105504552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[2021011810551946.png]: https://img-blog.csdnimg.cn/2021011810551946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210118110837903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210118111224920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210118114730375.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70
[20210118112129200.png]: https://img-blog.csdnimg.cn/20210118112129200.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210118105547717.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3,size_16,color_FFFFFF,t_70