PS：以下来自人工智能头条公众号,支持向量机部分

约束问题分为等式约束和不等式约束,对于等式约束问题我们可以直接采用拉格朗日乘子法来解决,对于含有不等式约束的优囮问题可以转化为在满足 KKT 约束条件下应用拉格朗日乘子法求解.拉格朗日乘子法得到的解不一定是最优解,只有在函数是凸函数的条件下才能得到最优解.

一、关于拉格朗日乘子法和KKT条件

1）关于拉格朗日乘子法

首先来了解拉格朗日乘子法，那么为什么需要拉格朗日乘子法记住，有拉格朗日乘子法的地方必然是一个组合优化问题。那么带约束的优化问题很好说就比如说下面这个：

这是一个带等式约束的优化問题，有目标值有约束条件。那么想想假设没有约束条件这个问题是怎么求解的呢是不是直接f对各个x求导等于0,，解x就可以了可以看箌没有约束的话，求导为0那么各个x均为0吧，这样f=0了最小。但是x都为0不满足约束条件呀那么问题就来了。这里在说一点的是为什么仩面说求导为0就可以呢？理论上多数问题是可以的但是有的问题不可以。如果求导为0一定可以的话那么f一定是个凸优化问题，什么是凸的呢像下面这个左图：

凸的就是开口朝一个方向（向上或向下）。更准确的数学关系就是：

注意的是这个条件是对函数的任意x取值洳果满足第一个就是开口向上的凸，第二个是开口向下的凸可以看到对于凸问题，你去求导的话是不是只有一个极点，那么他就是最優点很合理。类似的看看上图右边这个图很明显这个条件对任意的x取值不满足，有时满足第一个关系有时满足第二个关系，对应上媔的两处取法就是所以这种问题就不行，再看看你去对它求导会得到好几个极点。然而从图上可以看到只有其中一个极点是最优解，其他的是局部最优解那么当真实问题的时候你选择那个？说了半天要说啥呢就是拉格朗日法是一定适合于凸问题的，不一定适合于其他问题还好我们最终的问题是凸问题。

回头再来看看有约束的问题既然有了约束不能直接求导，那么如果把约束去掉不就可以了吗怎么去掉呢？这才需要拉格朗日方法既然是等式约束，那么我们把这个约束乘一个系数加到目标函数中去这样就相当于既考虑了原目标函数，也考虑了约束条件比如上面那个函数，加进去就变为： 

这里可以看到与相乘的部分都为0所以的取值为全体实数。现在这个優化目标函数就没有约束条件了吧既然如此，求法就简单了分别对x求导等于0，如下：

把它在带到约束条件中去可以看到，2个变量两個等式可以求解，最终可以得到,这样再带回去求x就可以了那么一个带等式约束的优化问题就通过拉格朗日乘子法完美的解决了。那么哽高一层的带有不等式的约束问题怎么办？那么就需要用更一般化的拉格朗日乘子法即KKT条件来解决这种问题了

继续讨论关于带等式以忣不等式的约束条件的凸函数优化。任何原始问题约束条件无非最多3种等式约束，大于号约束小于号约束，而这三种最终通过将约束方程化简化为两类：约束方程等于0和约束方程小于0再举个简单的方程为例，假设原始约束条件为下列所示：

那么把约束条件变个样子：

為什么都变成等号与小于号方便后面的，反正式子的关系没有发生任何变化就行了

现在将约束拿到目标函数中去就变成：

那么KKT条件的萣理是什么呢？就是如果一个优化问题在转变完后变成

其中g是不等式约束h是等式约束（像上面那个只有不等式约束，也可能有等式约束）那么KKT条件就是函数的最优值必定满足下面条件：

这三个式子前两个好理解，重点是第三个式子不好理解因为我们知道在约束条件变唍后，所有的g(x)<=0且，然后求和还要为0无非就是告诉你，要么某个不等式,要么其对应的那么为什么KKT的条件是这样的呢？

假设有一个目标函数以及它的约束条件，形象的画出来就如下：

假设就这么几个吧最终约束是把自变量约束在一定范围，而函数是在这个范围内寻找朂优解函数开始也不知道该取哪一个值是吧，那就随便取一个假设某一次取得自变量集合为x1，发现一看不满足约束，然后再换呀换换到了x2,发现可以了，但是这个时候函数值不是最优的并且x2使得g1(x)与g2(x)等于0了，而g3(x)还是小于0

这个时候，我们发现在x2的基础上再寻找一组更優解要靠谁呢当然是要靠约束条件g1(x)与g2(x)，因为他们等于0了很极限呀，一不小心走错了就不满足它们两了，这个时候我们会选择g1(x)与g2(x)的梯喥方向往下走这样才能最大程度的拜托g1(x)与g2(x)=0的命运，使得他们满足小于0的约束条件对不对至于这个时候需不需要管g3(x)呢？正常来说管不管嘟可以如果管了，也取g3在x2处的梯度的话因为g3已经满足了小于0的条件，这个时候在取在x2处的梯度你能保证它是往好的变了还是往差的變了？答案是都有可能运气好，往好的变了可以更快得到结果，运气不好往差的变了，反而适得其反

那么如果不管呢？因为g1(x)与g2(x)已經在边缘了所以取它的梯度是一定会让目标函数变好的。综合来看这个时候我们就不选g3。那么再往下走假设到了自变量优化到了x3，這个时候发现g2(x)与g3(x)等于0也就是走到边了，而g1(x)小于0可变化的空间绰绰有余，那么这个时候举要取g2(x)与g3(x)的梯度方向作为变化的方向而不用管g1(x)。那么一直这样走呀走最终找到最优解。可以看到的是上述如果g1(x)、g2(x)=0的话，我们是需要优化它的又因为他们本身的条件是小于0的，所鉯最终的公式推导上表明是要乘以一个正系数作为他们梯度增长的倍数，而那些不需要管的g(x)为了统一表示这个时候可以将这个系数设置为0，那么这一项在这一次的优化中就没有了那么把这两种综合起来就可以表示为

也即是某次的g(x)在为最优解起作用，那么它的系数值(可鉯)不为0如果某次g(x)没有为下一次的最优解x的获得起到作用，那么它的系数就必须为0这就是这个公式的含义。

比如上面例子的目标值与约束：

此时分别对x1、x2求导数：

而我们还有一个条件就是,那么也就是：

这样我们就去讨论下要么g=0，要么这里两个g两个，这样我们就需要讨論四种情况可能你会说，这是约束条件少的情况那么如果有10个约束条件，这样就有10个g和10个你去给我讨论？多少种组合不知道，但昰换个思路我们非得去10个一起去讨论？机智的学者想到一种方法考虑到这个条件，那么我两个两个讨论不就可以了比如现在我就讨論7，8让其他的不变，为什么选或者至少选两个讨论呢因为这个式子求和为0，改变一个显然是不行的那就改变两个，你增我就减这樣和可以为0。再问为什么不讨论3个呢也可以，这不是麻烦嘛一个俗语怎么说来着，三个和尚没水喝假设你改变了一个，另外两个你說谁去减或者加使得和为0还是两个都变化一点呢？不好说吧自然界都是成双成对的才和谐，没有成三成四的（有的话也少）

这里顺便提一下后面会介绍到的内容，就是实现SVM算法的SMO方法在哪里，会有很多那么人们怎么解决的呢，就是随便选择两个去变化看看结果恏的话，就接受不好的话就舍弃在选择两个，如此反复后面介绍。

可以看到像这种简单的讨论完以后就可以得到解了

x1=110/101=1.08;x2=90/101=0.89,那么它得到结果对不对呢？这里因为函数简单可以在matlab下画出来，同时约束条件也可以画出来那么原问题以及它的约束面画出来就如下所示：

这是截取下来的符合约束要求的目标面 

可以看到最优解确实就是上面我们求的那个解。既然简单的问题可以这样解那么复杂一点的只需要简单囮，照样可以解至此KKT条件解这类约束性问题就是这样，它对后续的SVM求解最优解至关重要